Administrative Information
- Instructor: Amin Saberi ({lastname} [AT] stanford [DOT] edu)
- Teaching Assistant: Paul Constantine (paulcon [AT] stanford [DOT] edu)
- Lecture: Monday, Wednesday 2:00-3:15 in 380-380D
- Office Hours: Monday, Wednesday 3:15-4:15 or by appointment
- Coursework: One or two homeworks and a final project.
Assignments
You have the choice of completing a short problem set or writing a three page response paper. Here is a detailed description of the project required for the course.
Topics
- Network structure of the Internet and World Wide Web.
- 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. 22)
Recommend Reading
- V. Bush. As We May Think. Atlantic Monthly, July 1945.
Uses of Link Information (Oct. 3)
Recommend Reading
- J. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46:604-632, 1999
- L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: bringing order to the web. Stanford CS tech report SIDL-WP-1999-0120.
Additional Reading
- S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998. Also Computer Networks and ISDN Systems, 30:107-117, 1998.
Evolution of Random Graphs (Oct. 5, Oct. 10)
Topics
- G(n,p), emergence of the giant connected component
- connectivity at np = O(log n)
Recommend Reading
Scale-Free Graphs (Oct. 12, Oct 17)
Recommend Reading
- Class Notes 1, 2
- A Barabasi, R Albert, H Jeong, Emergence of scaling in random networks, Science, 1999
- Bollobas, O Riordan, J Spencer, G Tusnady, The degree sequence of a scale-free random graph process, Random Structures and Algorithms, 2001
- Durrett: Sections 4.1-4.3
Additional Reading
- A Brief History of Generative Models for Power Law and Lognormal Distributions Michael Mitzenmacher
Expander Graphs (Oct. 19)
Recommend Reading
Additional Reading
- Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors - a deterministic construction of constant expanders.
- Ramanujan Graphs
Spectrum of a Graph (Oct. 26, Oct. 31)
Topics
Eigenvalues of the Laplacian, Conductance and the Spectral Gap, Cheeger's Inequality
Recommend Reading
Permutation Diameter (Harlan Sexton) (Nov. 2)
Additional Reading
Spectral Techniques for Data Mining Applications (Frank McSherry) (Nov. 7)
Various Demonstrations on Random Graph Dynamics and Spectral Clustering (David Gleich) (Nov. 9)
Propagation of Viruses (Nov. 14)
Peer-to-Peer Networks (Nov. 16)
Topics
Structured and Unstructured P2P networks, Random Walk vs. Flooding, Structure of Chord
Recommended Reading
Resource Allocation in a Large Scale Heterogeneous Network (Nov. 28)
Topics
Algorithms for finding Max-min fair and proportional fair allocations
Resources
Courses
The materials covered in the course will have a big intersection with the following two courses: A similar course currently taught at U of Washington.Books
- A great book on similar materials: Random Graph Dynamics
- Handbook of Graphs and Networks : From the Genome to the Internet
Links
- Class wiki page