Constant-factor approximation algorithms for identifying dynamic communities

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. Proc. 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 Proc. 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. Proc. 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 Proc. Intl. Conf. on Intelligence and Security Informatics (ISI 2003), Tucson, AZ, 2003.
• 28: B. Malin. Data and collocation surveillance through location access patterns. In Proc. 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. Proc. 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
approximation algorithms, community identification, dynamic social networks