Dynamic Networks and Social Networks Analysis in Computer Science
Models, Algorithms and Applications

Network like structures permeate life as we know it, from neurons in our brains to the social circles of friends with which we communicate, from the roads and highways on which we travel to the web of veins and arteries through which our blood flows. It is easy to envision how an ability to recognize, characterize and learn these structures automatically, and ways to map learned models to and from real-world phenomena becomes crucial to the advancement of science. Graph theory and discrete mathematics provide an initial formal framework and the set of tools that underly speculation. Prior work (not included in this reference) in social science (including organizational theory, sociology, and group psychology) provides a semantic basis of interpreting and measuring relationships. Bringing these together allows us to incorporate semantics into these frameworks and analyze, for example, systems of organisms (natural or artificial, intelligent or reactive) engaged in real tasks (coordination, decision making, information processing, etc). It is therefore not surprising to see a recent explosion in the occurrence and scope of work related to dynamic network and social network analysis in computer science literature. Below are some citations we consider important in computer science literature and in computational sociology literature, each listed separately. (If you have an additional citation you deem essential to this collection, please let us know.)

Application Areas: Information flow, Information extraction, Information fusion, Link analysis, Entity resolution, Social network analysis, Dynamic network analysis, Text learning, data mining, homeland security, law-enforcement, intelligence analysis

Selected References (Computer Science, primarily from ACM and IEEE publications)

1. Aiello, W., Chung, F., and Lu, L. Random evolution in massive graphs, Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (2001) 510-519. (PDF)

2. Airoldi E, Malin B. Data mining challenges for electronic safety: the case of fraudulent intent detection in e-mails. In Proceedings of the Privacy and Security Aspects of Data Mining Workshop, in conjunction with the 4th IEEE Internation Conference on Data Mining. Brighton, England. 2004.

3. Baumes J, Goldberg M, Magdon-Ismail M, Wallace W. Discovering hidden groups in communication networks. In Proceedings of the 2nd NSF/NIJ Symposium on Intelligence and Security Informatics. 2004.

4. Bernstein A, Clearwater S, Hill S, Perlich C, and Provost F. Discovering Knowledge from Relational Data Extracted from Business News. Proceedings of the Workshop on Multi-Relational Data Mining, in conjunction with the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2002. (PDF)

5. Bhattacharya I and Getoor L. Iterative record linkage for cleaning and integration. In Proceedings of the Workshop on Research issues in Data Mining and Knowledge Discovery, in conjunction with the 9th ACM SIGMOD Conference. Paris, France. 2004; 11-18.

6. Bhattacharya I and Getoor L. Deduplication and group detection using links. In Proceedings of the Workshop on Link Analysis and Group Detection, in conjunction with the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle, WA. 2004.

7. Broido, A., and Claffy, K. Internet topology: connectivity of IP graphs, in Proceedings of SPIE ITCom, August 2001. (PDF)

8. Califf M and Mooney R. Bottom-up relational learning of pattern-match rules for information extraction. In Journal of Machine Learning Research. 4: 177-210, 2003.

9. Califf M and Mooney R. Relational learning of pattern-match rules for information extraction. In Working notes of AAAI Spring Symposium on Applying Machine Learning to Discourse Processing. 1997. (PDF)

10. Carley, K. Estimating Vulnerabilities in Large Covert Networks Using Multi-Level Data. In Proceedings of the 2004 International Symposium on Command and Control Research and Technology. Conference held in June, SanDiego, CA., Evidence Based Research, Vienna, VA, 2004.

11. Carley, K., Prietula, M., eds.: Computational Organization Theory. Lawrence Erlbaum associates, Hillsdale, NJ. 2001.

12. Carley, K.  Smart agents and organizations of the future.  In Lievrouw, L., Livingstone, S., eds.: The Handbook of New Media.  Sage (2002) 205--220.

13. Carley, K., Kamneva, N.  A network optimization approach for improving organizational design.  Technical Report CMU-ISRI-04-102, School of Computer Science.  Carnegie Mellon University (2004)

14. Carley, K., Reminga, J., and Borgatti, S. Destabilizing Dynamic Networks Under Conditions of Uncertainty, IEEE KIMAS, Boston MA. 2003

15. Carley, K. and Reminga, J. ORA: Organization Risk Analyzer. Carnegie Mellon University, School of Computer Science, Institute for Software Research International, Technical Report, 2004, CMU-ISRI-04-101.

16. Chakrabarti, S., Joshi, M., Punera, K., and Pennock, D. The structure of broad topics on the web. In Proceedings of the Eleventh International World Wide Web Conference, 2002. (PDF)

17. Chen, L. and Carley, K. The Impact of Social Networks in the Propagation of Computer Viruses and Countermeasures. IEEE Trasactions on Systems, Man and Cybernetics, forthcoming.

18. Cohen W and Sarawagi S. Exploiting dictionaries in named entity extraction: combining semi-markov extraction processes and data integration methods. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle, WA. 2004. (PDF)

19. Collins M and Singer Y. Unsupervised models for named entity classification. In Proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP99), CollegePark, MD, 1999. (PDF)

20. Contractor, N., Carley, K., Levitt, R., Monge, P., Wasserman, S., Fulk, F.B.J., Kunz, A.H.J.  Co-evolution of knowledge networks and 21st century organizational forms: Computational modeling and empirical testing.  Technical Report TEC2000-01, University of Illinois at Urbana-Champaign (2000)

21. Cortes C, Pregibon D, and Volinsky C. Communities of interest. Lecture Notes in Computer Science 2189. 2001. (PDF)

22. Diesner, J. and Carley, K. Revealing Social Structure from Texts: Meta- Matrix Text Analysis as a novel method for Network Text Analysis In V.K Naraynan, & D.J. Armstrong (Eds.), Causal Mapping for Information Systems and Technology Research: Approaches, Advances, and Illustrations. Harrisburg, PA: Idea Group Publishing, forthcoming.

23. Diesner, J. and Carley, K. AutoMap1.2 - Extract, analyze, represent, and compare mental models from texts. Carnegie Mellon University, School of Computer Science, Institute for Software Research International, Technical Report, 2004, CMU-ISRI-04-100.

24. Dombroski, M. and Carley, K. NETEST: Estimating a Terrorist Network's Structure, Graduate Student Best Paper Award, CASOS 2002 Conference, Computational & Mathematical Organization Theory, 8, 2002, pp. 235-241.

25. Eick, S., and Wills, G. Navigating Large Networks with Hierarchies, In Proceedings Visualization Conference '93, pp204-210, San Jose, Calif. ,Oct 93. (PDF)

26. Faloutsos, C., Faloutsos, M., and Faloutsos, P. On power-law relationships of the internet topology, Proc. of ACM SIGCOMM, Aug. 1999. (PDF)

27. Flake, G., Lawrence, S., Lee Giles, C. and Coetzee, F. Self-organization and identification of Web communities. IEEE Computer, 35(3):66--71, 2002. (PDF)

28. Getoor L, Friedman N., Koller D, and Taskar B. Learning Probabilistic Models of Link Structure. Journal of Machine Learning Research. 2003.

29. Gibson D, Kleinberg J, and Raghavan P. Inferring Web communities from link topology. In Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, 1998. (PDF)

30. Goldenberg A, Kubica J, Komarek P, Moore A, and Schneider J. A Comparison of Statistical and Machine Learning Algorithms on the Task of Link Completion. In Proceedings of the Workshop on Link Analysis for Detecting Complex Behavior, in conjunction with the 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Washington DC. 2003.

31. Graham J. Wills. Nicheworks -- interactive visualization of very large graphs. In Graph Drawing '97 Conference Proceedings. Springer-Verlag Lecture Notes in Computer Science, 1997.

32. Hill S. Social network relational vectors for anonymous identity matching. In Proceedings of the IJCAI 2003 Workshop on Learning Statistical Models from Relational Data. Acapulco, Mexico, 2003.

33. Hopcroft J, Khan O, Kulls B, and Selman B. Tracking evolving communities in large linked networks. PNAS USA. 2004 Apr 6;101 Suppl 1:5249-53.

34. Hunter, D., Handcock, M.  Inference in curved exponential family models for networks.  Technical Report TR0402, Department of Statistics.  Penn State University (2004)

35. Jensen D, Neville J, and Gallagher B. Why Collective Inference Improves Relational Classification. Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle, WA. 2004.

36. Jensen D and Neville J. Data mining in social networks. In Proceedings of the National Academy of Sciences Symposium on Dynamic Social Network Analysis. 2002.

37. Kamneva, N. and Carley, K. A Network Optimization Approach for Improving Organizational Design. Carnegie Mellon University, School of Computer Science, Institute for Software Research International, Technical Report, 2004, CMU-ISRI-04-102.

38. Kempe, D., Kleinberg, J., Tardos, E.  Maximizing the spread of influence through a social network.  In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. (2003) (PDF)

39. Kleinberg, J.  The small-world phenomenon: An algorithmic perspective.  In: Proceedings of the Thirty-second ACM Symposium on Theory of Computing. (2000) (PDF)

40. Kleinberg, J.  Small-world phenomena and the dynamics of information.  In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, Morgan Kaufman (2001) (PDF)

41. Kleinberg, J.  The small-world phenomenon and decentralized search.  SIAM News 37 (2004) (PDF)

42. Kubica J, Moore A, and Schneider J. Tractable Group Detection on Large Link Data Sets. In Proceedings of the 3rd IEEE International Conference on Data Mining. Melbourne, Florida. 2003: 573-576.

43. Kubica J, Moore A, Cohn D, and Schneider J. Finding Underlying Connections: A Fast Graph-Based Method for Link Analysis and Collaboration Queries. In Proceedings of the International Conference on Machine Learning (ICML). Washington DC. 2003: 392-399.

44. Kubica J, Moore A, Cohn D, and Schneider J. cGraph: A Fast Graph-Based Method for Link Analysis and Queries. In Proceedings of the 2003 IJCAI Text-Mining & Link-Analysis Workshop. Acapulco Mexico. 2003.

45. Kubica J, Moore A, Schneider J, and Yang Y. Stochastic Link and Group Detection. In Proceedings of the 2002 AAAI Conference. Edmonton, Alberta. 2002; 798-804. (PDF)

46. Liben-Nowell D. and J. Kleinberg. The Link Prediction Problem for Social Networks. In Proceedings of the 12th International Conference on Information and Knowledge Management (CIKM). 2003. (PDF)

47. Lu Q and Getoor L. Link-based classification. In Proceedings of the 20th International Conference on Machine Learning (ICML). Washington, DC. 2003.

48. Magdon-Ismail, M., Goldberg, M., Wallace, W., Siebecker, D. Locating hidden groups in communication networks using Hidden Markov Models. In Proceedings of the International Conference on Intelligence and Security Informatics (ISI 2003), Tucson, AZ. 2003

49. Malin B. Data and collocation surveillance through location access patterns. In Proceedings of the North American Association for Computational Social and Organizational Science (NAACSOS) Conference. Pittsburgh, PA, June 2004.

50. Malin B and Sweeney L. How (Not) To Protect Genomic Data Privacy in a Distributed Network: Using Trail Re-identification to Evaluate and Design Anonymity Protection Systems. Journal of Biomedical Informatics. 2004; 37(3): 179 - 132.

51. Mann G, Yarowsky D. Unsupervised Personal Name Disambiguation. In Proceedings of CoNLL-2003. Edmonton, Canada, 2003, pp. 33-40. (PDF)

52. Neville J, Adler M, and Jensen D. Clustering Relational Data Using Attribute and Link Information. In Proceedings of the Text Mining and Link Analysis Workshop, 18th International Joint Conference on Artificial Intelligence. 2003.

53. Neville J and Jensen, D. Iterative classification in relational data. In L. Getoor and D. Jensen (Eds) Papers of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data. AAAI Press. pages 42-49, Austin, TX, 2000. (PDF)

54. Newman M. The Structure and Function of Complex Networks. SIAM Review. 2003; 45: 167-256.

55. Newman M. Detecting community structure in networks. Eur. Phys. J. 2004; 38: 321-330.

56. Newman M. Fast algorithm for detecting community structure in networks. Phys. Rev. 2004; 69: 066133.

57. Newman M. and Girvan M. Finding and evaluating community structure in networks. Phys. Rev. 2004; 69: 026113.

58. Newman M. and Park J. Why social networks are different from other types of networks. Phys. Rev. 2003; 68: 036122.

59. Newman, M., Watts, D., and Strogatz, S. Random graph models of social networks, Proc. Natl. Acad. Sci., to appear.

60. Ng, A., Zheng, A., Jordan, M.  Link analysis, eigenvectors, and stability.  In Nebel, B., ed.: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence.  Morgan Kaufman (2001) 903--910. (PDF)

61. Papadimitriou, C.  Computational aspects of organization theory.  Lecture Notes in Computer Science (1997) (PDF)

62. Papadimitriou, C., Servan-Schreiber, E.  The origins of the deadline: Optimizing communication in organizations.  In: Complexity in Economics. (1999) (PDF)

63. Schreiber, C. and Carley, K. Construct - A Multi-agent Network Model for the Co-evolution of Agents and Socio-cultural Environments. Carnegie Mellon University, School of Computer Science, Institute for Software Research International, Technical Report, 2004, CMU-ISRI-04-109.

64. Tsvetovat M, Carley K. Modeling Complex Socio-technical Systems using Multi-Agent Simulation Methods. Kunstliche Intelligenz (Artificial Intelligence Journal), Special Issue on Applications of Intelligent Agents. 2004.

65. Tsvetovat M, Sycara K, Chen Y, and Ying J. Customer Coalitions in Electronic Marketplaces. In Agent-Mediated Electronic Commerce III, Lecture Notes on Artificial Intelligence, Springer-Verlag Frank Dignum, Ulises Cortes (Eds.) 2003.

66. Tyler JR, Wilkinson DM, Huberman BA. Email as spectroscopy: Automated Discovery of Community Structure Within Organizations. In Proceedings of the First International Conference on Communities and Technologies. 2003.

67. Wasserman S and Faust K. Social Network Analysis. Cambridge University Press, Cambridge. 1994.

68. Watts DJ, Dodds PS, and Newman ME. Identity and search in social networks. Science. 2002; 296, 1302-1305.

69. Watts DJ and Strogatz SH. Collective Dynamics of 'Small-World' Networks. Nature. 1998; 393, 440.

70. Wellman, B. An Electronic Group is Virtually a Social Network. Pp. 179-205 in Culture of the Internet, edited by Sara Kiesler. Mahwah, NJ: Lawrence Erlbaum. 1997.

71. Zandt, T.V.  Decentralized information processing in the theory of organizations.  In Sertel, M., ed.: Contemporary Economic Development Reviewed, Volume 4: The Enterprise and its Environment.  MacMillan Press Ltd. (1997) (PDF)

References (Computational Sociology)

• Computational Analysis of Social and Organizational Systems (CASOS)
• CASOS Publications

• Data Privacy Lab White Papers
• Data Privacy Lab Technical Reports
• Data Privacy Lab Published Citations
• Data Privacy Lab References
• Data Privacy Lab Projects