Administrative Information
- Instructor: Amin Saberi ({lastname} [AT] stanford [DOT] edu)
- Teaching Assistant: Adam Guetz (guetz [AT] stanford [DOT] edu)
- Lecture: Wednesday, Friday 2:15-3:30 in Thornton 110
- Office Hours: Wednesday, Friday 3:30-4:30 or by appointment
- Coursework: Two or three homeworks and a final project.
- Course Text: Random Graph Dynamics by Rick Durrett.
- Course Syllabus: doc pdf
Assignments
Two homeworks, one response paper, and a project. The project can either be theoretical or an empirical analysis of available network datasets.
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.Overview and Background (Sept. 24nd)
- V. Bush. As We May Think. Atlantic Monthly, July 1945.
- Durret's book: sections 1.1-1.6
Part I: Random Graph Models
Erdos-Renyi Random Graphs (Sept. 28, Oct. 3, Oct. 5)
- Class notes: emergence of the giant component, connectivity and diameter
- Link to David Gleich's Erdos-Reyni Random Graphs with Matlab tutorial
- Durret's book 2.1 and 2.3
- Pages 103-107 of Random Graphs by Janson et al.
- Bollobas and de la Vega. The diameter of random regular graphs.
Preferential Attachment and Polya's Urn (Oct. 10, 17, 19)
- Class notes: 1, 2
- R. Albert and A. Barabasi. Statistical Mechanics of Complex Networks. Reviews of Modern Physics 74, 47 (2002).
- B. Bollobas. Mathematical Results on Scale Free Graphs. (2003)
- Durrett's book: 3.1, 3.2, 4.1-4.4
- Berger, Borgs, Chayes, Saberi. A Weak Distributional Limit for Preferential Attachment graphs, preprint, 2007
Part II: Algorithmic Aspects
Conductance, Spectral Gap and Their Implications (Oct. 24, 26)
- Class notes: spectral gap and mixing time, cheeger's inequality, spectral gap of scale free networks, constant d-regular expanders
- Durrett's book: 6.1-6.4
- Gkantsidis, Mihail, Saberi. Conductance and Congestion in Power Law Graphs.
Epidemics and Diffusion (Nov. 2, 16)
- Class notes: Diffusion, gossip, and protocol design
- Lecture slides: the epidemic threshold and controlling the spread of viruses
- Durrett's book: 3.5, 4.8
- Borgs, Chayes, Ganesh, Saberi, Wilson. How to distribute antidote to control epidemics. preprint, 2007.
- J. Kleinberg. Cascading Behavior in Netorks: Algorithmic and Economic Issues. Book chapter, 2007.
- S Boyd, A Ghosh, B Prabhakar, D Shah. Randomized Gossip Algorithms. 2005.
Small World Networks and Decentralized Search (Dec. 1, 3, 7)
- Class notes: 1
- J. Kleinberg. The small-world phenomenon: an algorithmic perspective. 1999.
- J. Kleinberg. Complex Networks and Decentralized Search Algorithms. ICM, 2006.
- O. Sandberg, I. Clarke. The evolution of navigable small-world networks. 2006.
- R Karp, C Schindelhauer, S Shenker, B Vocking. Randomized Rumor Spreading. 2000.
Part III: Real Networks
The Web Graph
- World Wide Web Consortium. A Little History of the World Wide Web, 1945-1995.
- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the web. WWW, May 2000.
- J. Keinberg. Authoritative sources in a hyperlinked environment. JACM, 1999.
- S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW, 1998.
The Internet Graph (Lecture by David Alderson)
- Lecture slides: pending...
- L. Li, D. Alderson, J. Doyle, and W. Willinger, Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications. Internet Mathematics, 2006.
- L. Li, D. Alderson, W. Willinger, and J. Doyle, A First-Principles Approach to Understanding the Internet's Router-Level Topology. Proc. ACM SIGCOMM, 2004.
NetFlix network and spectral partitioning (Lecture by David Gleich)
Resources
Similar Courses
- The course webpage from 2005.
- A The Structure of Information Networks currently taught at Cornell University.
- See also
From Random Graphs to Complex Networks
More references
- For basic concepts and defintions on graphs see Graph Theory by Diestel.
- Handbook of Graphs and Networks : From the Genome to the Internet
- Complex Social Networks