2009 AViewpointbasedApproachforInter

• (Asur et al., 2009) ⇒ Sitaram Asur, and Srinivasan Parthasarathy. (2009). “A Viewpoint-based Approach for Interaction Graph Analysis.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557035

Subject Headings:

Notes

• Categories and Subject Descriptors: H.2.8 Database Management: Database Applications - Data Mining.
• General Terms: Algorithms, Measurement

Cited By

• http://scholar.google.com/scholar?q=%22A+viewpoint-based+approach+for+interaction+graph+analysis%22+2009
• http://portal.acm.org/citation.cfm?doid=1557019.1557035&preflayout=flat#citedby

Quotes

Author Keywords

Interaction Networks, Neighborhood Analysis, Activation Functions

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 doi:10.1016/S0169-7552(98)00110-X
• 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,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 AViewpointbasedApproachforInter	Sitaram Asur Srinivasan Parthasarathy			A Viewpoint-based Approach for Interaction Graph Analysis		KDD-2009 Proceedings		10.1145/1557019.1557035		2009