A framework for community identification in dynamic social networks

ABSTRACT

We propose frameworks and algorithms for identifying communities in social networks that change over time. 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. Instead, we propose an optimization-based approach for modeling dynamic community structure. We prove that finding the most explanatory community structure is NP-hard and APX-hard, and propose algorithms based on dynamic programming, exhaustive search, maximum matching, and greedy heuristics. We demonstrate empirically that the heuristics trace developments of community structure accurately for several synthetic and real-world examples.

REFERENCES

• 1: J. Aizen, D. Huttenlocher, J. Kleinberg, and A. Novak. Traffic-based feedback on the web. Proc. Nat. Acad. Sci., 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. Proc. 2nd NSF/NIJ Symp. 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, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1994
• 6: 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.
• 7: P. C. Cross, J. O. Lloyd-Smith, , and W. M. Getz. Disentangling association patterns in fission-fusion societies using African buffalo as an exa. Animal Behaviour, 69:499--506, 2005.
• 8: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 9: A. Davis, B. B. Gardner, and M. R. Gardner. Deep South. The U. of Chicago Press, Chicago, IL, 1941.
• 10: 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, 2006. Submitted.
• 11: 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]
• 12: L. Freeman. On the sociological concept of "group": a empirical test of two models. American Journal of Sociology, 98:152--166, 1993.
• 13: 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.
• 14: 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]
• 15: 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]
• 16: M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci., 99:8271--8276, 2002.
• 17: 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]
• 18: 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]
• 19: P. Jaccard. Distribution de la flore alpine dans le bassin des dranses et dans quelques régions voisines. Bulletin de la Société Vaudoise des Sciences Naturelles, 37:241--272, 1901.
• 20: D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. 2003.
• 21: M. Kretzschmar and M. Morris. Measures of concurrency in networks and the spread of infectious disease. Math. Biosci., 133:165--195, 1996.
• 22: 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
• 23: M. Magdon-Ismail, M. Goldberg, W. Wallace, and D. Siebecker. Locating hidden groups in communication networks using hidden markov models. Proc. ISI '03, 2003.
• 24: B. Malin. Data and collocation surveillance through location access patterns. Proc. NAACSOS Conf., 2004.
• 25: L. A. Meyers, M. Newman, and B. Pourbohloul. Predicting epidemics on directed contact networks. Journal of Theoretical Biology, 240:400--418, 2006.
• 26: M. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev., 69, 2004.
• 27: Mark Newman , Albert-Laszlo Barabasi , Duncan J. Watts, The Structure and Dynamics of Networks: (Princeton Studies in Complexity), Princeton University Press, Princeton, NJ, 2006
• 28: 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.
• 29: E. M. Rogers. Diffusion of Innovations. Simon & Shuster, Inc., 5th edition, 2003.
• 30: 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.
• 31: N. Saitou and M. Nei. The neighbor-joining method: a new method for reconstructing phylogenetic trees. In Molecular biology and evolution, 1987.
• 32: D. Sedley. The stoic criterion of identity. Phronesis, 27:255--275, 1982.
• 33: K. L. Spalding, R. D. Bhardwaj, B. A. Buchholz, H. Druid, and J. Frisén. Retrospective birth dating of cells in humans. Cell, 122(1):133--143, 2005.
• 34: G. Simmel. The Sociology of Georg Simmel. ed. by K. H. Wolff. Free Press, Glencoe, IL, 1950.
• 35: G. Simmel. Conflict and the Web of Group Affiliations. Free Press, Glencoe, IL, 1955.
• 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: Takeaki Uno, Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs, Proceedings of the 8th International Symposium on Algorithms and Computation, p.92-101, December 17-19, 1997
• 38: S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, Cambridge, MA, 1994.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Algorithms

Keywords:
community identification, dynamic social networks