2009 ConstantFactorApproximationAlgo

(Tantipathananandh & Berger-Wolf, 2009) ⇒ Chayant Tantipathananandh, and Tanya Berger-Wolf. (2009). “Constant-factor Approximation Algorithms for Identifying Dynamic Communities.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557110

Subject Headings: Maximum Weighted Bipartite Matching.

Notes

Categories and Subject Descriptors: F.2.0 Analysis of Algorithms and Problem Complexity: General.
General Terms: Algorithms.

Cited By

Quotes

Author Keywords

Approximation Algorithms, Community Identification, Dynamic Social Networks.

Abstract

We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as unusually densely knit subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Recently, we have proposed an optimization-based framework for modeling dynamic community structure. Also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. In this paper, we analyze its performance guarantee for a special case where all actors can be observed at all times. In such instances, we show that the algorithm is a small constant factor approximation of the optimum. We use a similar idea to design an approximation algorithm for the general case where some individuals are possibly unobserved at times, and to show that the approximation factor increases twofold but remains a constant regardless of the input size. This is the first algorithm for inferring communities in dynamic networks with a provable approximation guarantee. We demonstrate the general algorithm on real data sets. The results confirm the efficiency and effectiveness of the algorithm in identifying dynamic communities.

References

1. J. Aizen, D. Huttenlocher, J. Kleinberg, and A. Novak. Traffic-based Feedback on the Web. Proceedings of National Academy of Sciences, 101(Suppl.1):5254--5260, 2004.
2. 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
3. J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace. Discovering Hidden Groups in Communication Networks. In: Proceedings. 2nd NSF/NIJ Symposium on Intelligence and Security Informatics, 2004.
4. Tanya Y. Berger-Wolf, Jared Saia, A Framework for Analysis of Dynamic 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.1150462
5. Kathleen M. Carley, Michael J. Prietula, Computational Organization Theory, L. Erlbaum Associates Inc., Hillsdale, NJ, 1994
6. Thomas T. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990
7. D. P. Croft, R. James, P. Thomas, C. Hathaway, D. Mawdsley, K. Laland, and J. Krause. Social Structure and Co-operative Interactions in a Wild Population of Guppies (Poecilia Reticulata). Behavioural Ecology and Sociobiology, In Press.
8. P. C. Cross, J. O. Lloyd-Smith, and W. M. Getz. Disentangling Association Patterns in Fission-fusion Societies Using African Buffalo As An Example. Animal Behaviour, 69:499--506, 2005.
9. A. Davis, B. B. Gardner, and M. R. Gardner. Deep South. The University of Chicago Press, Chicago, IL, 1941.
10. R. Diestel. Graph Theory (Graduate Texts in Mathematics). Springer, August 2005.
11. Nathan Eagle, Alex (Sandy) Pentland, Reality Mining: Sensing Complex Social Systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 doi:10.1007/s00779-005-0046-3
12. I. R. Fischhoff, S. R. Sundaresan, J. Cordingley, H. M. Larkin, M.-J. Sellier, and D. I. Rubenstein. Social Relationships and Reproductive State Influence Leadership Roles in Movements of Plains Zebra (Equus Burchellii). Animal Behaviour, 73: 825--831, 2007.
13. I. R. Fischhoff, S. R. Sundaresan, J. Cordingley, and D. I. Rubenstein. Habitat Use and Movements of Plains Zebra (Equus Burchelli) in Response to Predation Danger from Lions. Behavioral Ecology, 18(4): 725--729, 2007.
14. 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
15. D. Franzblau and A. Raychaudhuri. Optimal Hamiltonian Completions and Path Covers for Trees, and a Reduction to Maximum Flow. Anziam Journal, 44(2):193--204, 2002.
16. L. Freeman. Finding Social Groups: A Meta-analysis of the Southern Women Data. In R. Breiger, K. Carley, and P. Pattison, Editors, Dynamic Social Network Modeling and Analysis. The National Academies Press, Washington, D.C., 2003.
17. L. C. Freeman. On the Sociological Concept of "group": A Empirical Test of Two Models. American Journal of Sociology, 98:152--166, 1993.
18. Lise Getoor, Christopher P. Diehl, Link Mining: A Survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 doi:10.1145/1117454.1117456
19. David Gibson, Jon Kleinberg, Prabhakar Raghavan, Inferring Web Communities from Link Topology, Proceedings of the Ninth ACM Conference on Hypertext and Hypermedia : Links, Objects, Time and Space---structure in Hypermedia Systems: Links, Objects, Time and Space---structure in Hypermedia Systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States doi:10.1145/276627.276652
20. M. Girvan and M. E. J. Newman. Community Structure in Social and Biological Networks. Proceedings of Natl. Acad. Sci., 99:8271--8276, 2002.
21. Daniel Gruhl, R. Guha, David Liben-Nowell, Andrew Tomkins, Information Diffusion through Blogspace, Proceedings of the 13th International Conference on World Wide Web, May 17-20, 2004, New York, NY, USA doi:10.1145/988672.988739
22. John Hopcroft, Omar Khan, Brian Kulis, Bart Selman, Natural Communities in Large Linked Networks, 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.956816
23. 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
24. Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
25. M. Kretzschmar and M. Morris. Measures of Concurrency in Networks and the Spread of Infectious Disease. Math. Biosci., 133:165--195, 1996.
26. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, Trawling the Web for Emerging Cyber-communities, Proceedings of the Eighth International Conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
27. M. Magdon-Ismail, M. Goldberg, W. Wallace, and D. Siebecker. Locating Hidden Groups in Communication Networks Using Hidden Markov Models. In: Proceedings. Intl. Conference on Intelligence and Security Informatics (ISI 2003), Tucson, AZ, 2003.
28. B. Malin. Data and Collocation Surveillance through Location Access Patterns. In: Proceedings. North American Association for Computational Social and Organizational Science Conf., Pittsburgh, PA, June 2004.
29. L. A. Meyers, M. Newman, and B. Pourbohloul. Predicting Epidemics on Directed Contact Networks. Journal of Theoretical Biology, 240:400--418, 2006.
30. Mark Newman, Albert-Laszlo Barabasi, Duncan J. Watts, The Structure and Dynamics of Networks: (Princeton Studies in Complexity), Princeton University Press, Princeton, NJ, 2006
31. J. M. Read and M. J. Keeling. Disease Evolution on Networks: The Role of Contact Structure. Proceedings of R. Soc. Lond. B, 270:699--708, 2003.
32. E. M. Rogers. Diffusion of Innovations. Simon&Shuster, Inc., 5th Edition, 2003.
33. D. I. Rubenstein, S. Sundaresan, I. Fischhoff, and D. Saltz. Social Networks in Wild Asses: Comparing Patterns and Processes Among Populations. In A. Stubbe, P. Kaczensky, R. Samjaa, K. Wesche, and M. Stubbe, Editors, Exploration Into the Biological Resources of Mongolia, Volume 10. Martin-Luther-University Halle-Wittenberg, 2007. In Press.
34. J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A. Chaintreau. CRAWDAD Trace Cambridge/ Haggle/ Imote/ Infocom (v. 2006-01-31). Downloaded from Http://crawdad.cs.dartmouth.edu/cambridge/haggle/imote/infocom.
35. 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
36. S. R. Sundaresan, I. R. Fischhoff, J. Dushoff, and D. I. Rubenstein. Network Metrics Reveal Differences in Social Organization Between Two Fission-fusion Species, Grevy's Zebra and Onager. Oecologia, 2006.
37. 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
38. S. Wasserman and F. K. Social Network Analysis. Cambridge University Press, Cambridge, MA, 1994.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ConstantFactorApproximationAlgo	Chayant Tantipathananandh Tanya Berger-Wolf			Constant-factor Approximation Algorithms for Identifying Dynamic Communities		KDD-2009 Proceedings		10.1145/1557019.1557110		2009