Class Syllabus

The course commences with an overview of the nascent field of complex networks, dividing it into three related but distinct strands: Statistical description of large scale networks, viewed as static objects; the dynamic evolution of networks, where now the structure of the network is understood in terms of a growth process; and dynamical processes that take place on fixed networks; that is, "networked dynamical systems". (A fourth area of potential research ties all the previous three strands together under the rubric of co-evolution of networks and dynamics, but very little research has been done in this vein and so it is omitted.)

The remainder of the course treats each of the three strands in greater detail, introducing technical knowledge as required, summarizing the research papers that have introduced the principal ideas, and pointing out directions for future development. With regard to networked dynamical systems, the course treats in detail the more specific topic of information propagation in networks, in part because this topic is of great relevance to social science, and in part because it has received the most attention in the literature to date.

Note 1: Readings followed by (*) are compulsory. Other readings are optional but recommended.
Note 2: Syllabus and Readings may change. Check site for updated versions.
Note 3: You may obtain a printable version of the syllabus by clicking here.

Topic 1: Introduction

a. Overview of the Course

The small-world problem
A world of networks

  1. Handout 1 (*)
  2. J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32(4), 425-443 (1969) (*)
  3. J. F. Hauer and J. E. Dagel. Consortium for electric reliability technology solutions, grid of the future: White paper on review of recent reliability issues and system events. U.S. Dept. of Energy. (1999).
  4. S. Milgram, The small world problem. Psychology Today 2, 60-67 (1967).

 
b. Introduction to graph theory terminology
 

Topic 2: Random and Random-Biased Networks

Paul Erdos and random graphs
Anatol Rapoport and random-biased nets

  1. Handout 2 (*)
  2. Watts, D. J. Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton, Princeton University Press, 1999), Chapter 2.
  3. A. Rapoport. A contribution to the theory of random and biased nets. Bulletin of Mathematical Biophysics 19, 257-271 (1957). Also in S. Leinhardt (ed.) Social Networks: A Developing Paradigm, 389-409 (New York, Academic Press, 1977).
  4. A. Rapoport. Mathematical Models of Social Interaction. In R. D. Luce, R. R. Bush, and E. Galanter (Eds.) Handbook of Mathematical Psychology, Vol. 2, 493-579 (New York, Wiley, 1963).
 

Topic 3: Social Network Analysis
a. Groups
Cohesive subgroups
Multidimensional Scaling
Structural equivalence, roles and positions
  1. Handout 3 (*)
  2. R. N. Shepard. Multidimensional scaling, tree fitting, and clustering. Science, 210: 390-398 (1980).
  3. M. L. Davison. Multidimensional scaling. (John Wiley and Sons, 1983).
  4. S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications (Cambridge, Cambridge University Press, 1994), Chapters 7 and 9.

 
b. Individuals
Ego networks
Clustering
Weak ties
Structural holes
Centrality measures
  1. Handout 4 (*)
  2. A. Degenne and M. Forse. Introducing Social Networks. (London, Sage Publications, 1999), Chapter 5.
  3. S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications (Cambridge, Cambridge University Press, 1994). Chapter 5.
 

Topic 4: Dynamics, Emergence, and Multiple Scales
a. Emergence, Part 1 (General Concepts)
Local vs. global
Emergence
Multiple scales
Bottom-up vs. top-down representations
Example: Spin Systems
  1. Handout 5 (*)
  2. P. Anderson. More is different. Science. 177, 393-396 (1972).
  3. M. Newman and G. Barkema. Monte Carlo Methods in Statistical Physics (Oxford, Clarendon Press, 1999), Chapter 1.
  4. R. Palmer. Broken ergodicity. In D. Stein (Ed.) Lectures in the Science of Complexity, SFI Studies in the Sciences of Complexity, Volume 1, 275-300 (Addison Wesley Longman, 1989).
  5. D. Stein. Disordered systems: mostly spin glasses. In D. Stein (Ed.) Lectures in the Science of Complexity, SFI Studies in the Sciences of Complexity, Volume 1, 301-353 (Addison Wesley Longman, 1989).

 
b. Emergence, Part 2 (Social Systems and Networks)

Guest: Dr. David Gibson (Columbia, Harvard)

  1. M. Granovetter. The strength of weak ties. American Journal of Sociology. 81, 1287-1303 (1973). (*)
  2. T. Schelling. Micomotives and Macrobehavior, Chapter 1. (Norton, 1978) (*)
 

Topic 5: 'Small-World' Networks
a. 'Small-world' networks, Part 1

The alpha-model
Phase transitions and the small-world phenomenon

  1. Handout 6 (*)
  2. Watts, D. J. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, (1999). (*)
  3. Watts, D. J. Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton, Princeton University Press, 1999), Chapter 3.

 
'Small-world' networks, Part 2

The beta-model
Comparisons with real network data

  1. Handout 7 (*)
  2. D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393, 440-442 (1998). (*)
  3. Watts, D. J. Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton, Princeton University Press, 1999), Chapter 3.
 

Topic 6: Scale-Free Networks

Degree distributions
Basic scale-free model
Comparisons with data

  1. Handout 8 (*)
  2. Barabasi, A. and Albert, R. Emergence of scaling in random networks. Science 286, 509-512 (1999). (*)
  3. L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley. Classes of small-world networks. Proceedings of the National Academy of Sciences, 97(21), 11149-11152 (2000) (*)
 

Topic 7: Affiliation Networks
a. Affiliation networks, Part 1: Empirical properties

"Who is the best connected scientist?"
Guest Lecture, Prof. Mark Newman (Santa Fe Institute)

  1. M. E. J. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences, 98(2), 404-409. (2000). (*)
  2. M. E. J. Newman Who is the best connected scientist? A study of scientific coauthorship networks. (2000). (*)

 
b. Affiliation networks, Part 2: Theoretical models.

  1. Handout 9 (*)
  2. M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. (2000).
 

Topic 8: Searching on Networks
a. Search Part I: Search on Small-World Networks

Milgram revisted
Searching on small-world networks
Searchable small-world networks

  1. Handout 10 (*)
  2. J. Kleinfeld. Could It Be a Big World After All? What the Milgram Papers in the Yale Archives Reveal About the Original Small World Study. Working paper, University of Alaska, Fairbanks (Oct 2000).
  3. J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Cornell Computer Science Technical Report 99-1776, (1999).

 
b. Search Part II: Search on Scale-Free Networks
  1. L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law networks.(*)

 
c. Search Part III: Search on Bipartite Networks
  1. Handout 11 (*)

 
d. Search Part IV: Link Structure as Content
  1. J. M. Kleinberg. Authoritative sources in a hyperlinked environment.
  2. G. W. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities.
 

Topic 9: Epidemiological Models of Contagion
  1. Watts, D. J. Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton, Princeton University Press, 1999), Chapter 6.
 

Topic 10: Percolation Models of Contagion and Robustness
  1. D. Stauffer and A. Aharony. Introduction to Percolation Theory. (Taylor and Francis, 1992), Chapter 1. (*)
  2. R. Albert and A. L. Barabasi. Error and attack tolerance of complex networks. (*)
  3. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts.
 

Topic 11: Threshold Models of Binary Decisions, and Contagion

Two player games and threshold rules
Simple model
Application to information cascades

  1. T. Schelling. Hockey helmets, concealed weapons, and daylight saving: A study of binary choices with externalities. Journal of Conflict Resolution, 17(3), 381-428 (1973). Also reprinted in T. Schelling. Micomotives and Macrobehavior, Chapter 7. (Norton, 1978) (*)
  2. D. J. Watts. A simple model of fads and cascading failures. Santa Fe Institute Working Paper 00-12-062.