SI 508 - Networks: Theory and Application

Overview

This course will cover topics in network analysis, from social networks to applications in information networks such as the internet. We will introduce basic concepts in network theory, discuss metrics and models, use software analysis tools to experiment with a wide variety of real-world network data, and study applications to areas such as information retrieval. For their final project, the students will apply the concepts learned in class to networks of interest to them.

Required Texts:

• Nooy, Wouter de, Andrej Mrvar, and Vladimir Batagelj. Exploratory Social Network Analysis with Pajek. Structural analysis in the social sciences. New York: Cambridge University Press, 2005.  (Pajek)
• Newman, M. E. J. "The Structure and Function of Complex Networks." SIAM Review. 45 (2003): 167-256. (MEJN)

Week 1

Lab: Introduction to networks

Reading: Pajek Chapter 1: Looking for Social Structure

Week 2

Topic: Basic network metrics

Reading (1 of 2): MEJN Sections 1-3

Lab: Pajek Lab

Reading (2 of 2):

• Pajek Chapter 2: Attributes and Relations
• Pajek documentation (skim through)
• Graphviz documentation  (skim through)

Week 3

Topic: Centrality and other network metrics

Reading (1 of 2):

• Baker, W. E., and R. R. Faulkner. "The Social Organization of Conspiracy: Illegal Networks in the Heavy Electrical Equipment Industry." American Sociological Review. 58. 6 (1993): 837.
• Friedkin, N. E. "Structural Bases of Interpersonal Influence in Groups: A Longitudinal Case Study." American Sociological Review. 58. 6 (1993): 861. (JSTOR account required for article)
• optional: Chapter 5: Centrality and prestige - Wasserman, Stanley, and Katherine Faust. Social Network Analysis: Methods and Applications. Structural analysis in the social sciences, 8. Cambridge: Cambridge University Press, 1994.

Lab: Centrality

Reading (2 of 2):

• Pajek Chapter 6: Center and Periphery
• Pajek Chapter 9: Prestige

Week 4

Topics:

• Clustering
• Milgram’s small world experiment
• Random graphs
• Watts-Strogatz small world model

Reading:

• Watts DJ, and SH Strogatz. "Collective Dynamics of 'small-World' Networks." Nature. 393. 6684 (1998): 440-2. (Nature subscription required for article)
• Travers, Jeffrey & Stanley Milgram. 1969. "An Experimental Study of the Small World Problem." Sociometry, Vol. 32, No. 4, pp. 425-443.
• MEJN Section 6: The Small World Model

Lab: Small world phenomenon in real-world networks & simulations

Week 5

Topics:

• Zipf’s Law & fat tails
• Preferential attachment

Reading (1 of 2):

• L. Adamic, Zipf, Power-laws, and Pareto - a ranking tutorial.
• MEJN Section 7: Models of Network Growth
• Barabasi, A-L, and R Albert. "Emergence of Scaling in Random Networks." Science. 286. 5439 (1999): 509. (Science subscription required for article)

Lab: Fitting power laws, growing networks

Reading (2 of 2):

• optional: Albert, Reka, and Albert-Laszlo Barabasi. "Interdisciplinary Physics: Biological Physics, Quantum Information, Etc. - Topology of Evolving Networks: Local Events and Universality." Physical Review Letters. 85. 24 (2000): 5234.
• optional: Pennock, D. M., G. W. Flake, S. Lawrence, E. J. Glover, and C. L. Giles. "Winners Don't Take All: Characterizing the Competition for Links on the Web." PNAS. 99 (2002): 5207-5211.

Week 6

Topic: Graph traversal

Reading (1 of 2):

• Chapter 23: Elementary graph algorithms - Cormen, Thomas H., and Thomas H. Cormen. Introduction to Algorithms. Cambridge, Mass: MIT Press, 2001.

Lab: Network analysis with GUESS

Reading (2 of 2):

• Adar, E. "GUESS: A Language and Interface for Graph Exploration." In CHI’06 (2006): 791-800.
• GUESS documentation

Week 7

Topics:

• Homophily
• Exploratory analysis of online communities
• Community structure

Reading (1 of 2):

• Girvan M, and ME Newman. "Community Structure in Social and Biological Networks." PNAS. 99. 12 (2002): 7821-6.
• S. Feld. Social structural determinants of similarity among associates. American Sociological Review, 47, 1982.
• optional: Adamic, Lada A, and Eytan Adar. "Friends and Neighbors on the Web." Social Networks. 25. 3 (2003): 211.
• optional: L. A. Adamic, O. Buyukkokten, and E. Adar. A social network caught in the web. First Monday, 8(6), June 2003.
• optional: L. A. Adamic and N. Glance. The political blogosphere and the 2004 US election: Divided they blog. In Proceedings of LinkKDD-2005, 2005.

Lab: Community structure

Reading (2 of 2):

• Pajek Chapter 3: Cohesive Subgroups
• Pajek Chapter 5: Affiliations
• optional: Pajek Chapter 12: Block Models

Week 8

Topic: Search

Reading:

• Kleinberg, J M. "Brief Communications - Networks: Navigation in a Small World." Nature. 406. 6798 (2000): 845.
• Watts, D J, P S Dodds, and M E J Newman. "Identity and Search in Social Networks." Science. 296. 5571 (2002): 1302.
• optional: Liben-Nowell D, J Novak, R Kumar, P Raghavan, and A Tomkins. "Geographic Routing in Social Networks." PNAS. 102. 33 (2005): 11623-8.
• optional: Adamic, L., and E. Adar. "How to Search a Social Network." Social Networks. 27. 3 (2005): 187-203.

No lab due to midterm.

Week 9

Topics:

• Ranking algorithms and information retrieval
• The web as a graph

Reading:

• Broder, Andrei, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. "Graph Structure in the Web." Computer Networks. 33. 1 (2000): 309.
• L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• optional: Menczer, F. "Mapping the Semantics of Web Text and Links." IEEE Internet Computing. 9. 3 (2005): 27-36.
• optional: Erkan, Güne s and Dragomir R. Radev. "LexRank: Graph-based Lexical Centrality as Salience in Text Summarization." Journal of Artificial Intelligence Research (JAIR)  22 (2004): 457-479.

Lab: The web as a graph

Week 10

Topic: Information diffusion

Reading (1 of 2):

• Davis, Gerald F., Mina Yoo, and Wayne E. Baker. "The Small World of the American Corporate Elite, 1982-2001." Strategic Organization. 1. 3 (2003): 301-326. (Sage Journals subscription required for article)
• Granovetter, Mark S. "The Strength of Weak Ties." American Journal of Sociology. 78 (1973): 1360-1380.
• optional: Burt, R. S. "Structural Holes and Good Ideas." American Journal of Sociology. 110. 2 (2004): 349-399.
• optional: Aral, Sinan and Van Alstyne, Marshall W., Networks, Information & Social Capital (formerly titled 'Network Structure & Information Advantage') (March 15, 2008).
• optional: Lazer, David, and Allan Friedman. The Parable of the Hare and the Tortoise Small Worlds, Diversity, and System Performance / David Lazer and Allan Friedman. [Cambridge, Mass.]: John F. Kennedy School of Government, Harvard University, 2005.

Lab: Diffusion

Reading (2 of 2): Pajek Chapter 8: diffusion

Week 11

Topic: Networks over time

Reading (1 of 2):

• Guimerà R, B Uzzi, J Spiro, and LA Amaral. "Team Assembly Mechanisms Determine Collaboration Network Structure and Team Performance." Science (New York, N.Y.). 308. 5722 (2005): 697-702.
• Backstrom, L., Huttenlocher, D., Kleinberg, J., and Lan, X. Group formation in large social networks: membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (Philadelphia, PA, USA, August 20 - 23, 2006). KDD '06.
• Leskovec, J., Kleinberg, J., and Faloutsos, C. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD international Conference on Knowledge Discovery in Data Mining (Chicago, Illinois, USA, August 21 - 24, 2005). KDD '05.

Lab: Tagging networks

Reading (2 of 2):

• Golder, S. A., and B. A. Huberman. "Usage Patterns of Collaborative Tagging Systems." Journal of Information Science. 32. 2 (2006): 198-208.  (Sage Journals subscription required for article)
• optional: Lambiotte, R., and M. Ausloos. "Collaborative Tagging As a Tripartite Network." Lecture Notes in Computer Science. 3993 (2006): 1114-1118.
• optional: Cattuto C, V Loreto, and L Pietronero. "Semiotic Dynamics and Collaborative Tagging." Proceedings of the National Academy of Sciences of the United States of America. 104. 5 (2007): 1461-4.

Week 12

Topic: Network robustness

Reading:

• Albert, R, H Jeong, and A-L Barabasi. "Error and Attack Tolerance of Complex Networks." Nature. 406. 6794 (2000): 378.
• optional: Kinney, R., P. Crucitti, R. Albert, and V. Latora. "Modeling Cascading Failures in the North American Power Grid." Eur. Phys. B. 46. 1 (2005): 101-107. (Springerlink subscription required for article)

Lab: none

Week 13

Project presentations