Administrative Information

Instructor: Amin Saberi ({lastname} [AT] stanford [DOT] edu)
Teaching Assistant: Farnaz Ronaghi (farnaaz [AT] stanford [DOT] edu)
Lecture: Mondays, 2:15-4:30 in Thornton 211
Office Hours: Mondays after class - 6:30 pm
Coursework: Two homeworks and a class project
Course Syllabus: doc pdf

Topics

Network structure of Internet, World Wide Web, and social networks.
Modeling: Erdös-Renyi graphs, power-law networks, small-world phenomenon.
Algorithmic aspects: methods for link analysis, centralized and decentralized search, conductance, spectral gap and the effect of structure on performance.
Economic aspects: incentive issues in network formation, routing games.
Security: vulnerability and robustness to random failures and worst-case attacks, contact process and the spread of viruses.

Lectures

There is a significant dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. We consider this a feature.

Lecture 1: Small-World Phenomenon (April 9)

J. Kleinberg's paper . The small-world phenomenon: an algorithmic perspective. (2000)
J. Kleinberg's paper. Complex Networks and Decentralized Search Algorithms.(2006)
O. Sandberg, I. Clarke's paper. The evolution of navigable small-world networks. (2006)

Lecture 2: Power-Law Networks (April 16)

Class notes: power-laws, and the preferential attachment model (tex)
Durrett's book: 3.1, 3.2, 4.1-4.4
R. Albert and A. Barabasi's paper. Statistical Mechanics of Complex Networks. (2002).
B. Bollobas's paper. Mathematical Results on Scale Free Graphs. (2003)
Berger, Borgs, Chayes, Saberi's paper. A Weak Distributional Limit for Preferential Attachment Graphs, to appear in the Annals of Probability Theory.

Lecture 3: Erdos-Renyi Random Graphs (April 23)

Class notes: emergence of the giant connected component (tex)
Link to David Gleich's Erdos-Reyni Random Graphs with Matlab tutorial, Farnaz Ronaghi's supplementary note. (matlab codes giant_component.m, evolution.m).
See Durret's book 2.1 and 2.3
See Pages 103-107 of Random Graphs by Janson et al.
Bollobas and de la Vega's paper. The diameter of random regular graphs.

Lecture 4: Epidemic Models for Diffusion (April 30)

Ganesh et al.'s paper: The effect of network topology on the spread of epidemics
Berger et al.'s paper: On the spread of viruses on the internet
Complementary slides
See Spielman's class for more information on graph expansion and spectrum.

Lecture 5: Controlling a diffusion (May 7)

Kleinberg's survey Cascading Behavior in Networks: Algorithmic and Economic Issues
Ayalvadi et al. How to Distribute Antidotes to Control Epidemics.
See this for more information about optimizing sub modular functions.

Lecture 6: Diffusion as dynamics of a game (May 14)

Montanari and Saberi's paper: The Spread of Innovations in Social Networks. See also the supplementary information, and a short excerpt.
Ellison's paper: Learning, local interaction, and coordination

Assignments

Assignment One: PDF