Administrative Information

Instructor: Amin Saberi ({lastname} [AT] stanford [DOT] edu)
Teaching Assistant: Qi Qi (kaylaqi [AT] stanford [DOT] edu)
Lecture: Tuesday, 2:15-4:30 in Education 313
Office Hours: Tuesday 4:30-6:00 or by appointment
Coursework: Three to four homeworks
Course Syllabus: doc pdf

Assignments

Assignment 1: tex pdf Solution: tex pdf
Assignment 2: tex pdf Solution: tex pdf
Assignment 3: tex pdf Solution: tex 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: Erdos-Renyi Random Graphs (April 6)

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 2: Power-Law Networks (April 13)

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, preprint.

Lecture 3: Small-World Phenomenon (April 20)

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 4: Conductance and Expansion (April 27)

Class notes: Conductance and Expansion (tex)

Lecture 5: Random Walks on Graphs (May 4)

Lovasz's survey : Random Walks on Graphs (sections 1-5).
Doyle and Snell's paper: Random Walks and Electric Networks .
For a more extensive treatment on the spectrum of the graph and its implications see www.cs.yale.edu/homes/spielman/561.

Lecture 6: Affiliation Networks (May 11)

Invited Speaker: D. Sivakumar (Google Inc.) slides
S. Lattanzi and D. Sivakumar's paper: Affiliation Network.

Lecture 7: Social learning: convergence times (May 18)

Invited Speaker: Benjamin Golub (Stanford) slides
B. Golub and M.O. Jackson's paper: How Homophily Affects Diffusion and Learning in Networks.
B. Golub and M.O. Jackson's paper: Naive Learning in Social Networks and the Wisdom of Crowds.