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)
Lecture 4: Epidemic Models for Diffusion (April 30)
Lecture 5: Controlling a diffusion (May 7)
Lecture 6: Diffusion as dynamics of a game (May 14)
Lecture 7: Social Learning in Networks (May 21)
- Invited Speaker: Kostas Bimpikis (Stanford), slides
- A Simple Model of Herd Behavior by Banerjee, The Quarterly Journal of Economics (1992)
- Dynamics of information exchange in endogenous social networks by Daron Acemoglu, Kostas Bimpikis, Asuman Ozdaglar (working paper, 2012)
- Bayesian learning in social networks by Daron Acemoglu, Munther Dahleh, Ilan Lobel, Asuman Ozdaglar (Review of Economic Studies, forthcoming)
- Strategic Experimentation with Exponential Bandits by Keller, Rady and Cripps (Econometrica, 2005)
Assignments