An event-based framework for characterizing the evolutionary behavior of interaction graphs

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 non-overlapping 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 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.

REFERENCES

• 1: Floortje Alkemade , Carolina Castaldi, Strategies for the Diffusion of Innovations on Social Networks, Computational Economics, v.25 n.1-2, p.3-23, February 2005 [doi>10.1007/s10614-005-6245-1]
• 2: S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionf interaction graphs. Technical Report Oct 2006, Updated Jun 2007, OSU-CISRC-2/07-TR16., 2007.
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 4: A. L. Barabasi and E. Bonabeau. Scale-free networks. Scientific American, 288:60--69, 2003.
• 5: A. L. Barabasi, H. Jeong, R. Ravasz, Z. Nda, T. Vicsek, and A. Schubert. On the topology of the scientific collaboration networks. Physica A, 311:590--614, 2002.
• 6: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150467]
• 7: A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70, 2004.
• 8: R. Cowan and N. Jonard. Network structure and the diffusion of knowledge. Journal of Economic Dynamics and Control, 28:1557--1575, 2004.
• 9: Tanja Falkowski , Jorg Bartelheimer , Myra Spiliopoulou, Mining and Visualizing the Evolution of Subgroups in Social Networks, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.52-58, December 18-22, 2006 [doi>10.1109/WI.2006.118]
• 10: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 11: M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proc. National Academy of Sciences of the United States of America, 99(12):7821--7826, 2002.
• 12: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 13: D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. Proc. Intl. Colloquium on Automata, Languages and Programming (ICALP), 2005.
• 14: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 15: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 16: J. Lin, M. Vlachos, E. Keogh, and D. Gunopulos. Iterative incremental clustering of time series. EDBT, pages 106--122, 2004.
• 17: M. E. J. Newman. Modularity and community structure in networks. Proc. National Academy of Sciences of the United States of America, 103(23):8577--8582, 2006.
• 18: J. Reichardt and S. Bornholdt. Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters, 93, 2004.
• 19: Ravi Samtaney , Deborah Silver , Norman Zabusky , Jim Cao, Visualizing Features and Tracking Their Evolution, Computer, v.27 n.7, p.20-27, July 1994 [doi>10.1109/2.299407]
• 20: Myra Spiliopoulou , Irene Ntoutsi , Yannis Theodoridis , Rene Schult, MONIC: modeling and monitoring cluster transitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150491]
• 21: Stijn Dongen, A cluster algorithm for graphs, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 22: S. Wasserman and K. Faust. Social network analysis. Cambridge University Press, 1994.
• 23: H. Yang, S. Parthasarathy, and S. Mehta. Mining spatial object patterns in scientific data. Proc. 9th Intl. Joint Conf. on Artificial Intelligence, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Measurement

Keywords:
diffusion of innovations, evolutionary analysis, interaction networks