A viewpoint-based approach for interaction graph analysis

ABSTRACT

Recent innovations have resulted in a plethora of social applications on the Web, such as blogs, social networks, and community photo and video sharing applications. Such applications can typically be represented as evolving interaction graphs with nodes denoting entities and edges representing their interactions. The study of entities and communities and how they evolve in such large dynamic graphs is both important and challenging.

While much of the past work in this area has focused on static analysis, more recently researchers have investigated dynamic analysis. In this paper, in a departure from recent efforts, we consider the problem of analyzing patterns and critical events that affect the dynamic graph from the viewpoint of a single node, or a selected subset of nodes. Defining and extracting a relevant viewpoint neighborhood efficiently, while also quantifying the key relationships among nodes involved are the key challenges we address. We also examine the evolution of viewpoint neighborhoods for different entities over time to identify key structural and behavioral transformations that occur.

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. Amer-Yahia, M. Benedikt, and P. Bohannon. Challenges in searching online communities. IEEE Data Eng. Bull., 30(2):23--31, 2007.
• 3: S. Asur and S. Parthasarathy. On the use of viewpoint neighborhoods for dynamic graphanalysis. Technical Report Sept 2008 OSU-CISRC-9/08-TR50, 2008.
• 4: Sitaram Asur , Srinivasan Parthasarathy , Duygu Ucar, An event-based framework for characterizing the evolutionary behavior of interaction graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281290]
• 5: 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]
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 7: Gregory Buehrer , Srinivasan Parthasarathy , Yen-Kuang Chen, Adaptive Parallel Graph Mining for CMP Architectures, Proceedings of the Sixth International Conference on Data Mining, p.97-106, December 18-22, 2006 [doi>10.1109/ICDM.2006.15]
• 8: R. Cowan and N. Jonard. Network structure and the diffusion of knowledge. Journal of Economic Dynamics and Control, 28:1557--1575,2004.
• 9: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 10: C. L. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35--41, 1977.
• 11: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 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. ICALP, 2005.
• 14: Yehuda Koren , Stephen C. North , Chris Volinsky, Measuring and extracting proximity in networks, 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.1150432]
• 15: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, 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.1150476]
• 16: P. Resnik. Semantic similarity in a taxonomy: An information-based measureand its application to problems of ambiguity in natural language. Journal of Artifical Intelligence Research, 11:95--130, 1999.
• 17: Jimeng Sun , Christos Faloutsos , Spiros Papadimitriou , Philip S. Yu, GraphScope: parameter-free mining of large time-evolving graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281266]
• 18: Chayant Tantipathananandh , Tanya Berger-Wolf , David Kempe, A framework for community identification in dynamic social networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281269]
• 19: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, 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.1150448]
• 20: Haixuan Yang , Irwin King , Michael R. Lyu, DiffusionRank: a possible penicillin for web spamming, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277815]

INDEX TERMS

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

General Terms:
Algorithms, Measurement

Keywords:
activation functions, interaction networks, neighborhood analysis