Learning and predicting the evolution of social networks

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 introd