Istituto di Scienza e Tecnologie dell'Informazione     
Berlingerio M., Bringmann B., Bonchi F., Gionis A. Mining graph evolution rules. In: ECML PKDD 2009 - Machine Learning and Knowledge Discovery in Databases European Conference (Bled, slovenia, 7-11 September 2009). Proceedings, vol. I pp. 115 - 130. (Lecture Notes in Computer Science, vol. 5781). Springer, 2009.
In this paper we introduce graph-evolution rules, a novel type of frequency-based pattern that describe the evolution of large networks over time, at a local level. Given a sequence of snapshots of an evolving graph, we aim at discovering rules describing the local changes occurring in it. Adopting a definition of support based on minimum image we study the problem of extracting patterns whose frequency is larger than a minimum support threshold. Then, similar to the classical association rules framework, we derive graph-evolution rules from frequent patterns that satisfy a given minimum confidence constraint. We discuss merits and limits of alternative definitions of support and confidence, justifying the chosen framework. To evaluate our approach we devise GERM (Graph Evolution Rule Miner), an algorithm to mine all graph-evolution rules whose support and confidence are greater than given thresholds. The algorithm is applied to analyze four large real-world networks (i.e., two social networks, and two co-authorship networks from bibliographic data), using different time granularities. Our extensive experimentation confirms the feasibility and utility of the presented approach. It further shows that different kinds of networks exhibit different evolution rules, suggesting the usage of these local patterns to globally discriminate different kind of networks.
URL: http://www.springerlink.com/content/wj77051rk6t702k9/
DOI: 10.1007/978-3-642-04180-8_25
Subject Graph mining
Data mining,
Social network analysis
H.2.8 Database Management

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional