<task>
Arrange the paragraphs of the Introduction in the correct order.
</task>
<paper name>
Mining graph topological patterns: finding co-variations
among vertex descriptors
</paper name>
<paragraphs>
1
Such topological properties and vertex attributes are mostly of
numerical or ordinal types and their similarity can be captured by
quantifying their co-variation. Such co-variation indicates how a set
of vertex descriptors tend to monotonically increase or decrease all
together. Therefore, following the way paved by [5], we propose
to mine rank-correlated sets over graph descriptors by extracting
topological patterns defined as a set of vertex properties and
attributes that strongly со-vary over the vertices of the graph.
2
We propose in this article an algorithm, called TopGraph-Miner,
which discovers topological patterns. It has as input an attributed
graph, such as the one in Figure 1.
3
The same limitation holds for methods [18], [24], [29], [30] that
identify sets of vertices that share local attributes and that are close
neighbors. Such approaches only focus on a local neighborhood of
the vertices and do not consider the connectivity of the vertex in the
whole graph. In this paper, we propose to extract meaningful patterns
that integrate information about the connectivity of the vertices and
their attribute values.
4
We propose several interesting measures of topological patterns
that are different from the pairs of vertices considered while
evaluating up and down co-variations between properties and
attributes: (1) considering all the vertex pairs enables to find patterns
that are true all over the graph; (2) taking into account only the vertex
pairs that are in a specific order with respect to a selected numerical
or ordinal attribute reveals the topological patterns that emerge
with respect to this attribute; (3) examining the vertex pairs that are
connected in the graph makes it possible to identify patterns that are
structurally correlated to the relationship encoded by the graph.
5
Given such a graph, we first compute a set of topological
properties for every of the graph vertices. TopGraph-Miner then
integrates searching and pruning strategies in the identification of the
most relevant topological patterns.
6
Real-world phenomena are often depicted by graphs where vertices
represent entities and edges represent their relationships or interactions.
Entities are also described by one or more attributes that constitute the
attribute vectors associated with the vertices of the attributed graph.
7
We also propose an operator that identifies the top к
representative vertices of a topological pattern. Let us illustrate
our proposal on a co-authorship graph depicted in Figure 1, where
vertices (from A to P) denote authors, edges encode co-authorship
relations, and three attributes describe the author.
8
This article is structured as follows: Section 2 presents topological
vertex properties. Sections 3 and 4 introduce our new model for
mining topological patterns. Our algorithm is defined in Section 5. Its
efficiency and its effectiveness are shown in Sections 6 and 7. Section
8 discusses the related work and Section 9 concludes the article.
9
Our contribution is therefore threefold. First, we propose a
new kind of graph analysis that exploits attributes and topological
properties of vertices.
10
Existing methods that support the discovery of local patterns in
graphs mainly focus on the topological structure of the patterns, by
extracting specific subgraphs while ignoring the vertex properties
(cliques [22], quasi-cliques [21], [32]), or compute frequent
relationships between vertex attribute values (frequent subgraphs in
a collection of graphs [16] or in a single graph [4]), while ignoring
the topological status of the vertices within the whole graph, e.g. the
vertex connectivity or centrality.
11
Second, to produce such analysis, we provide new insights
into co-variation pattern mining by considering up and down covariations, defining new upper bounds on the support of such
co-variations, proposing several interestingness measures of
topological pattern, and giving to the user the ability to visualize
the patterns on the original graph thanks to the identification of the
top к representative vertices. Third, to validate our approach, we
conducted an empirical study.
12
Combining such microscopic and macroscopic properties
precisely characterizes the connectivity of the nodes and constitutes
information that may explain why some vertices have similar
attribute values. Depending on the link between vertex attributes
and the relationship encoded by the graph, one of these topological
properties may co-vary with vertex attributes.
13
Finally, it gives to the user the ability to visualize every pattern
on the input graph by identifying the top к representative vertices.
</paragraphs>