Local Pattern Detection in Attributed Graphs
We propose to mine the topology of a large attributed graph by finding regularities among vertex descriptors. Such descriptors are of two types: (1) the vertex attributes that convey the information of the vertices themselves and (2) some topological prop
- PDF / 701,273 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 217 Views
Universit´e de Lyon, CNRS, INSA de Lyon, LIRIS UMR5205, 69621 Villeurbanne, France {jean-francois.boulicaut,celine.robardet}@insa-lyon.fr 2 Universit´e de Lyon, CNRS, Univ. Lyon1, LIRIS UMR5205, 69622 Villeurbanne, France [email protected]
Abstract. We propose to mine the topology of a large attributed graph by finding regularities among vertex descriptors. Such descriptors are of two types: (1) the vertex attributes that convey the information of the vertices themselves and (2) some topological properties used to describe the connectivity of the vertices. These descriptors are mostly of numerical or ordinal types and their similarity can be captured by quantifying their co-variation. Mining topological patterns relies on frequent pattern mining and graph topology analysis to reveal the links that exist between the relation encoded by the graph and the vertex attributes. In this paper, we study the network of authors who have cooperated at some time with Katharina Morik according to the data available in DBLP database. This is a nice occasion for formalizing different questions that can be considered when an attributed graph describes both a type of interaction and node descriptors. Keywords: Attributed graph mining
1
· Katharina Morik co-authorship
Introduction
A timely challenge concerns enriched graph mining to support knowledge discovery. We recently proposed the topological pattern domain [25], a kind of gradual pattern that extends the rank-correlated sets from [6] to support attributed graph analysis. In such graphs, the binary relation encoded by the graph is enriched by vertex numerical attributes. However, 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 attributes (cliques [21], quasi-cliques [20,29]), or compute frequent relationships between vertex attribute values (frequent subgraphs in a collection of graphs [16] or in a single graph [5]), while ignoring the topological status of the vertices within the whole graph, e.g., the vertex connectivity or centrality. The same limitation holds for the methods proposed in [18,24,27,28], which identify sets of vertices that have similar attribute values 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. c Springer International Publishing Switzerland 2016 S. Michaelis et al. (Eds.): Morik Festschrift, LNAI 9580, pp. 168–183, 2016. DOI: 10.1007/978-3-319-41706-6 8
Local Pattern Detection in Attributed Graphs
169
To investigate the relations that may exist between the position of the vertices within the graph and their attribute values, we proposed to extract topological patterns that are sets made of vertex attributes and topological measures. Such measures quantify the topological status of each vertex within the graph. Some of these measures are based on the close neighborhood of the verti
Data Loading...
