Topic 1: Introduction

a. Overview of the Course

The smallworld problem
A world of networks
 Handout 1 (*)
 J. Travers and S. Milgram. An experimental study of the small world
problem. Sociometry, 32(4), 425443 (1969) (*)
 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).
 S. Milgram, The small world problem. Psychology Today 2, 6067 (1967).

b. Introduction to graph theory terminology


Topic 2: Random and RandomBiased Networks

Paul Erdos and random graphs
Anatol Rapoport and randombiased nets
 Handout 2 (*)
 Watts, D. J. Small Worlds: The Dynamics of Networks Between Order
and Randomness (Princeton, Princeton University Press, 1999), Chapter
2.
 A. Rapoport. A contribution to the theory of random and biased nets.
Bulletin of Mathematical Biophysics 19, 257271 (1957). Also
in S. Leinhardt (ed.) Social Networks: A Developing Paradigm,
389409 (New York, Academic Press, 1977).
 A. Rapoport. Mathematical Models of Social Interaction. In R. D. Luce,
R. R. Bush, and E. Galanter (Eds.) Handbook of Mathematical Psychology,
Vol. 2, 493579 (New York, Wiley, 1963).


Topic 3: Social Network Analysis

a. Groups

Cohesive subgroups
Multidimensional Scaling
Structural equivalence, roles and positions
 Handout 3 (*)
 R. N. Shepard. Multidimensional
scaling, tree fitting, and clustering. Science, 210: 390398
(1980).
 M. L. Davison. Multidimensional scaling. (John Wiley and Sons,
1983).
 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
 Handout 4 (*)
 A. Degenne and M. Forse. Introducing Social Networks. (London,
Sage Publications, 1999), Chapter 5.
 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
Bottomup vs. topdown representations
Example: Spin Systems
 Handout 5 (*)
 P. Anderson. More is
different. Science. 177, 393396 (1972).
 M. Newman and G. Barkema. Monte Carlo Methods in Statistical Physics
(Oxford, Clarendon Press, 1999), Chapter 1.
 R. Palmer. Broken ergodicity. In D. Stein (Ed.) Lectures in the
Science of Complexity, SFI Studies in the Sciences of Complexity,
Volume 1, 275300 (Addison Wesley Longman, 1989).
 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, 301353 (Addison Wesley Longman, 1989).

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

Guest: Dr. David Gibson (Columbia, Harvard)
 M. Granovetter. The
strength of weak ties. American Journal of Sociology. 81,
12871303 (1973). (*)
 T. Schelling. Micomotives and Macrobehavior, Chapter 1. (Norton,
1978) (*)


Topic 5: 'SmallWorld' Networks

a. 'Smallworld' networks, Part 1

The alphamodel
Phase transitions and the smallworld phenomenon
 Handout 6 (*)
 Watts, D. J. Networks,
dynamics, and the smallworld phenomenon. American Journal of
Sociology, (1999). (*)
 Watts, D. J. Small Worlds: The Dynamics of Networks Between Order
and Randomness (Princeton, Princeton University Press, 1999), Chapter
3.

'Smallworld' networks, Part 2

The betamodel
Comparisons with real network data
 Handout 7 (*)
 D. J. Watts and S. H. Strogatz. Collective dynamics of 'smallworld'
networks. Nature 393, 440442 (1998). (*)
 Watts, D. J. Small Worlds: The Dynamics of Networks Between Order
and Randomness (Princeton, Princeton University Press, 1999), Chapter
3.


Topic 6: ScaleFree Networks

Degree distributions
Basic scalefree model
Comparisons with data
 Handout 8 (*)
 Barabasi,
A. and Albert, R. Emergence of scaling in random networks. Science
286, 509512 (1999). (*)
 L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley. Classes
of smallworld networks. Proceedings of the National Academy
of Sciences, 97(21), 1114911152 (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)
 M. E. J. Newman. The
structure of scientific collaboration networks. Proceedings of
the National Academy of Sciences, 98(2), 404409. (2000). (*)
 M. E. J. Newman Who
is the best connected scientist?
A study of scientific coauthorship networks. (2000). (*)

b. Affiliation networks, Part 2: Theoretical models.

 Handout 9 (*)
 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 SmallWorld Networks

Milgram revisted
Searching on smallworld networks
Searchable smallworld networks
 Handout 10 (*)
 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).
 J. Kleinberg. The
smallworld phenomenon: An algorithmic perspective. Cornell Computer
Science Technical Report 991776, (1999).

b. Search Part II: Search on ScaleFree Networks

 L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search
in powerlaw networks.(*)

c. Search Part III: Search on Bipartite Networks

 Handout 11 (*)

d. Search Part IV: Link Structure as Content

 J. M. Kleinberg. Authoritative
sources in a hyperlinked environment.
 G. W. Flake, S. Lawrence, and C. L. Giles. Efficient
identification of web communities.


Topic 9: Epidemiological Models of Contagion

 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

 D. Stauffer and A. Aharony. Introduction to Percolation Theory. (Taylor
and Francis, 1992), Chapter 1. (*)
 R. Albert and A. L. Barabasi. Error
and attack tolerance of complex networks. (*)
 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

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