Administrative Information

Assignments

Topics

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)

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)

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.