A framework for analysis of dynamic social networks

ABSTRACT

Finding patterns of social interaction within a population has wide-ranging applications including: disease modeling, cultural and information transmission, and behavioral ecology. Social interactions are often modeled with networks. A key characteristic of social interactions is their continual change. However, most past analyses of social networks are essentially static in that all information about the time that social interactions take place is discarded. In this paper, we propose a new mathematical and computational framework that enables analysis of dynamic social networks and that explicitly makes use of information about when social interactions occur.

REFERENCES

• 1: J. Aizen, D. Huttenlocher, J. Kleinberg, and A. Novak. Traffic-based feedback on the web. Proc. Natl. Acad. Sci., 101(Suppl.1):5254--5260, 2004.
• 2: R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74:47--97, 2002.
• 3: A.-L. Barabási. The origin of bursts and heavy tails in human dynamics. Nature, 435:207--211, 2005.
• 4: J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace. Discovering hidden groups in communication networks. Proc. 2nd NSF/NIJ Symp. on Intel. and Security Inform., 2004.
• 5: S. Bernstein, A. Clearwater, S. Hill, C. Perlich, and F. Provost. Discovering knowledge from relational data extracted from business news. Proc. Workshop on Multi-Relational Data Mining, 2002.
• 6: K. Carley. Communicating new ideas: The potential impact of information and telecommunication technology. Tech. in Society, 18(2):219--230, 1996.
• 7: K. Carley. Dynamic network analysis. In R. Breiger, K. Carley, and P. Pattison, eds, Dynamic Social Network Modeling and Analysis, 133--145. The Nat. Acad. Press, Wash., DC, 2003.
• 8: Kathleen M. Carley , Michael J. Prietula, Computational organization theory, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1994
• 9: L. Chen and K. Carley. The impact of social networks in the propagation of computer viruses and countermeasures. IEEE Trans. Sys., Man and Cyber., forthcoming.
• 10: D. Croft, J. Krause, and R. James. Social networks in the guppy (Poecilia Reticulata). Proc. Royal Soc. London. Series B. Bio. Sci, 271:516--519, 2004.
• 11: 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.
• 12: A. Davis, B. B. Gardner, and M. R. Gardner. Deep South. The University of Chicago Press, Chicago, IL, 1941.
• 13: P. Doreian. On the delineation of small group structure. In H. C. Hudson, ed, Classifying Social Data. Jossey-Bass, San Francisco, CA, 1979.
• 14: S. Eubank, H. Guclu, V. Kumar, M. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429:429:180--184., Nov 2004. Supplement material.
• 15: 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 Natl Acad. Press, Washington, D.C., 2003.
• 16: M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360--1380, 1973.
• 17: P. Jaccard. The distribution of flora in the alpine zone. The New Phytologist, 11(2):37--50, 1912.
• 18: 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]
• 19: J. Kleinberg. Temporal dynamics of on-line information streams. Draft chapter for the forthcoming book Data Stream Management: Processing High-Speed Data Streams (M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer.
• 20: J. Kleinberg. Small-world phenomena and the dynamics of information. In Proc. 17th Intl. Joint Conf. Artif. Intel., Morgan Kaufman, 2001.
• 21: G. Kolata. Ideas and trends; Enron offers an unlikely boost to e-mail surveillance. New York Times, May 22 2005.
• 22: M. Kretzschmar and M. Morris. Measures of concurrency in networks and the spread of infectious disease. Math. Biosci., 133:165--195, 1996.
• 23: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the bursty evolution of blogspace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775233]
• 24: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 25: D. Lusseau and M. E. J. Newman. Identifying the role that individual animals play in their social network. Proc. R. Soc. London B (Suppl.), 271:S477--S481, 2004.
• 26: 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 Intel. and Security Inform., 2003.
• 27: M. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 28: C. Papadimitriou. Computational aspects of organization theory. Lecture Notes in Computer Science, 1997.
• 29: C. Papadimitriou and E. Servan-Schreiber. The origins of the deadline: Optimizing communication in organizations. Complexity in Economics., 1999.
• 30: Joshua R. Tyler , Dennis M. Wilkinson , Bernardo A. Huberman, Email as spectroscopy: automated discovery of community structure within organizations, Communities and technologies, Kluwer, B.V., Deventer, The Netherlands, 2003
• 31: S. Wasserman and F. K. Social Network Analysis. Cambridge University Press, Cambridge, MA, 1994.
• 32: B. Wellman. An electronic group is virtually a social network. In S. Kiesler, editor, Culture of the Internet, pages 179--205. Lawrence Erlbaum, Mahwah, NJ, 1997.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
algorithms, disease spread, dynamic social networks