Topic 1: Introduction
|
a. Overview of the Course
|
The small-world problem
A world of networks
- Handout 1 (*)
- J. Travers and S. Milgram. An experimental study of the small world
problem. Sociometry, 32(4), 425-443 (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, 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
- 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, 257-271 (1957). Also
in S. Leinhardt (ed.) Social Networks: A Developing Paradigm,
389-409 (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, 493-579 (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: 390-398
(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
Bottom-up vs. top-down representations
Example: Spin Systems
- Handout 5 (*)
- P. Anderson. More is
different. Science. 177, 393-396 (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, 275-300 (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, 301-353 (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,
1287-1303 (1973). (*)
- 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
- Handout 6 (*)
- Watts, D. J. Networks,
dynamics, and the small-world 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.
|
'Small-world' networks, Part 2
|
The beta-model
Comparisons with real network data
- Handout 7 (*)
- D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world'
networks. Nature 393, 440-442 (1998). (*)
- 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
- Handout 8 (*)
- Barabasi,
A. and Albert, R. Emergence of scaling in random networks. Science
286, 509-512 (1999). (*)
- 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)
- M. E. J. Newman. The
structure of scientific collaboration networks. Proceedings of
the National Academy of Sciences, 98(2), 404-409. (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 Small-World Networks
|
Milgram revisted
Searching on small-world networks
Searchable small-world 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
small-world phenomenon: An algorithmic perspective. Cornell Computer
Science Technical Report 99-1776, (1999).
|
b. Search Part II: Search on Scale-Free Networks
|
- 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
|
- 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), 381-428 (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 00-12-062.
|