Istituto di Scienza e Tecnologie dell'Informazione     
Bringmann B., Berlingerio M., Bonchi F., Gionis A. Learning and predicting the evolution of social networks. In: Ieee Intelligent Systems, vol. 25 (4) pp. 26 - 35. IEEE, 2010.
With the increasing availability of large social network data, there is also an increasing interest in analyzing how those networks evolve over time.1 Traditionally, the analysis of social networks has focused only on a single snapshot of a network. Researchers have already verified that social networks follow power-law degree distribution, 2 have a small diameter, and exhibit small-world structure3 and community structure.4 Attempts to explain the properties of social networks have led to dynamic models inspired by the preferential attachment model,5 which assumes that new network nodes have a higher probability of forming links with high-degree nodes, creating a "rich-get-richer" effect. Recently several researchers have turned their attention to the evolution of social networks at a global scale. For example, Jure Leskovec and his colleagues empirically observed that networks become denser over time, in the sense that the number of edges grows superlinearly with the number of nodes.6 Moreover, this densification follows a power-law pattern. They reported that the network diameter often shrinks over time, in contrast to the conventional wisdom that such distance measures should increase slowly as a function of the number of nodes. Although some effort has been devoted to analyzing global properties of social network evolution, not much has been done to study graph evolution at a microscopic level. A first step in this direction investigated a variety of network formation strategies,7 showing that edge locality plays a critical role in network evolution. We propose a different approach. Following the paradigm of association rules and frequent-pattern mining, our work searches for typical patterns of structural changes in dynamic networks. Mining for such local patterns is a computationally challenging task that can provide further insight into the increasing amount of evolving network data. Beyond the notion of graph evolution rules (GERs), a concept that we introduced in an earlier work,8 we developed the Graph Evolution Rule Miner (GERM) software to extract such rules and applied these rules to predict future network evolution.9,10 The merits of our approach go beyond descriptive analysis. In many cases, frequent patterns are used as basic blocks to build more complex data-mining solutions. Our framework can help predict edges among old and new nodes and predict when a new edge is expected to appear. Even when comparing directly with the classic link-prediction problem,9 we show that simple scores based on our evolution rules represent important features providing good prediction performances.
URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5552587
DOI: 10.1109/MIS.2010.91
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