An event-based framework for characterizing the evolutionary behavior of interaction graphs
Authors:
Open Access
- 1 November 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 3 (4) , 1-36
Abstract
Interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs from a static point of view. The study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. In this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. We use nonoverlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. We use these events to characterize complex behavioral patterns of individuals and communities over time. We show how semantic information can be incorporated to reason about community-behavior events. We also demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. Finally, we present a diffusion model for evolving networks, based on our framework.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-0742999, IIS-0347662)
- U.S. Department of Energy (DE-FG02-04ER25611)
This publication has 29 references indexed in Scilit:
- An ensemble framework for clustering protein–protein interaction networksBioinformatics, 2007
- Quantifying social group evolutionNature, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Finding community structure in very large networksPhysical Review E, 2004
- Scale-Free NetworksScientific American, 2003
- Exploiting hierarchical domain structure to compute similarityACM Transactions on Information Systems, 2003
- Self-organization and identification of Web communitiesComputer, 2002
- Evolution of the social network of scientific collaborationsPhysica A: Statistical Mechanics and its Applications, 2002
- Clustering and preferential attachment in growing networksPhysical Review E, 2001
- 10.1162/153244303321897735Applied Physics Letters, 2000