Learning and Predicting the Evolution of Social Networks
Authors:
- 19 August 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Intelligent Systems
- Vol. 25 (4) , 26-35
Abstract
With the increasing availability of large social network data, there is also an increasing interest in analyzing how those networks evolve over time. 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, have a small diameter, and exhibit small-world structure and community structure. Attempts to explain the properties of social networks have led to dynamic models inspired by the preferential attachment models which assumes that new network nodes have a higher probability of forming links with high-degree nodes, creating a rich-get-richer effect. 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, 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, we developed the Graph Evolution Rule Miner (GERM) software to extract such rules and applied these rules to predict future network evolution.Keywords
This publication has 11 references indexed in Scilit:
- Toward Predicting Collective Behavior via Social Dimension ExtractionIEEE Intelligent Systems, 2010
- Mining Graph Evolution Rules2009
- What Is Frequent in a Single Graph?2008
- Social Computing: From Social Informatics to Social IntelligenceIEEE Intelligent Systems, 2007
- Graphs over time2005
- The link prediction problem for social networks2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Emergence of Scaling in Random NetworksScience, 1999
- On power-law relationships of the Internet topologyACM SIGCOMM Computer Communication Review, 1999
- Collective dynamics of ‘small-world’ networksNature, 1998