Group formation in large social networks: membership, growth, and evolution

ABSTRACT

The processes by which communities come together, attract new members, and develop over time is a central research issue in the social sciences - political movements, professional organizations, and religious denominations all provide fundamental examples of such communities. In the digital domain, on-line groups are becoming increasingly prominent due to the growth of community and social networking sites such as MySpace and LiveJournal. However, the challenge of collecting and analyzing large-scale time-resolved data on social groups and communities has left most basic questions about the evolution of such groups largely unresolved: what are the structural features that influence whether individuals will join communities, which communities will grow rapidly, and how do the overlaps among pairs of communities change over time.Here we address these questions using two large sources of data: friendship links and community membership on LiveJournal, and co-authorship and conference publications in DBLP. Both of these datasets provide explicit user-defined communities, where conferences serve as proxies for communities in DBLP. We study how the evolution of these communities relates to properties such as the structure of the underlying social networks. We find that the propensity of individuals to join communities, and of communities to grow rapidly, depends in subtle ways on the underlying network structure. For example, the tendency of an individual to join a community is influenced not just by the number of friends he or she has within the community, but also crucially by how those friends are connected to one another. We use decision-tree techniques to identify the most significant structural determinants of these properties. We also develop a novel methodology for measuring movement of individuals between communities, and show how such movements are closely aligned with changes in the topics of interest within the communities.

REFERENCES

• 1: Lada A. Adamic, Orkut Buyukkokten, and Eytan Adar, A Social Network Caught in the Web First Monday, 8(6), 2003.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: S.Boorman, P. Levitt. The genetics of altruism. Acad. Pr. 1980.
• 4: Christian Borgs , Jennifer Chayes , Mohammad Mahdian , Amin Saberi, Exploring the community structure of newsgroups, 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.1016914]
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: R. Burt. Structural Holes: The Social Structure of Competition. Harv. U. Press, 1992. Harvard, 1992.
• 7: D. Centola, M. Macy, V. Eguiluz. Cascade Dynamics of Multiplex Propagation. Physica A, to appear.
• 8: J. Coleman Social Capital in the Creation of Human Capital, American Journal of Sociology, 94(Supplement): 1988.
• 9: J. Coleman. Foundations of Social Theory. Harvard, 1990.
• 10: S. Deerwester, S. Dumais, T. Landauer, G. Furnas, R. Harshman. Indexing by latent semantic analysis. JASIS 41(1990). J. Amer. Soc. for Information Science, 41(6), 1990.
• 11: Stephen Dill , Ravi Kumar , Kevin S. McCurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.69-78, September 11-14, 2001
• 12: P. S. Dodds, D. J. Watts. Universal behavior in a generalized model of contagion. Phys. Rev. Lett., 92:218701, 2004.
• 13: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 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: G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph Clustering and Minimum Cut Trees. Internet Math. 1(2004).
• 16: M. Girvan, M. E. J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(2002).
• 17: M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6): 1360--1380, 1973.
• 18: P. Hoff, A. Raftery, M. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(2002).
• 19: P. Holme, M. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. arXiv physics/0603023, March 2006.
• 20: 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]
• 21: 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]
• 22: Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
• 23: G. Kossinets, D. Watts. Empirical analysis of an evolving social network. Science, 311:88--90, 2006.
• 24: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Structure and evolution of blogspace, Communications of the ACM, v.47 n.12, December 2004 [doi>10.1145/1035134.1035162]
• 25: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, Proceedings of the 7th ACM conference on Electronic commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134732]
• 26: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci. USA, 102 (Aug 2005).
• 27: M. Macy, personal communication, June 2006.
• 28: M. E. J. Newman. Detecting community structure in networks. Eur. Phys. J. B 38, 321--330 (2004).
• 29: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 30: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 31: E. Rogers. Diffusion of innovations Free Press, 1995.
• 32: Purnamrita Sarkar , Andrew W. Moore, Dynamic social network analysis using latent space models, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.31-40, December 2005 [doi>10.1145/1117454.1117459]
• 33: D. Strang, S.. Soule. Diffusion in Organizations and Social Movements: From Hybrid Corn to Poison Pills. Annual Review of Sociology 24(1998).
• 34: T. Valente. Network Models of the Diffusion of Innovations. Hampton Press, 1995.
• 35: Fernanda B. Viégas , Marc Smith, Newsgroup Crowds and AuthorLines: Visualizing the Activity of Individuals in Conversational Cyberspaces, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 4, p.40109.2, January 05-08, 2004
• 36: Xuerui Wang , Andrew McCallum, Topics over time: a non-Markov continuous-time model of topical trends, 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.1150450]
• 37: S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994.

INDEX TERMS

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

General Terms:
Measurement, Theory

Keywords:
diffusion of innovations, on-line communities, social networks