Cornell University

Fall 2020

**Instructor: Jon Kleinberg**

This is a seminar focusing on models for networks and for some of the fundamental processes that take place within them. Topics will include the small-world phenomenon, decentralized search, contagion, cascading behavior, graph partitioning, and spectral analysis.

The seminar is structured as a 2-credit S/U-only class at the 7000-level, and in keeping with this format the classwork will consist of lecture participation and supplementary reading of papers, but no graded material.

(1) **Cascading Behavior in Networks**

- Simple Probabilistic Models of Contagion.
- Section 21.8 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
- R.M. Karp. The transitive closure of a random digraph. Random Structures and Algorithms, 1:1(1990).
- Section 21.8 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Simple Probabilistic Models of Contagion.

- Models of Collective Action.
- M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.

- Models of Collective Action.

- Threshold-Based Models of Diffusion in Networks.
- Section 19.7 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Threshold-Based Models of Diffusion in Networks.

- Finding Influential Sets of Nodes.
- J. Kleinberg. Cascading Behavior in Networks: Algorithmic and Economic Issues. In
__Algorithmic Game Theory__(N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, eds.), Cambridge University Press, 2007.- J. Kleinberg. Cascading Behavior in Networks: Algorithmic and Economic Issues. In

- Finding Influential Sets of Nodes.

(2) **Small-World Phenomena in Networks **

- Small-world experiments in social networks.
- J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32(1969).
- J. Kleinfeld. Could it be a Big World After All? The `Six Degrees of Separation' Myth. Society, April 2002.
- Peter Sheridan Dodds, Roby Muhamad, Duncan J. Watts. An Experimental Study of Search in Global Social Networks. Science 301(2003), 827.
- J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32(1969).

- Small-world experiments in social networks.

- Basic Random Graph Models, and the Consequences of Expansion.

- Decentralized Search in Networks.
- J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
- Section 20.7 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
- J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.

- Decentralized Search in Peer-to-Peer Systems
- H. Balakrishnan, M.F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Looking up data in P2P systems. Communications of the ACM 46:43-48, February 2003.

- Decentralized Search in Peer-to-Peer Systems

- Nearest-Neighbor Search in Metric Spaces
- David R. Karger, Matthias Ruhl. Finding nearest neighbors in growth-restricted metrics. STOC 2002: 741-750

- Nearest-Neighbor Search in Metric Spaces

(3) **Spectral Analysis of Networks**

- Graph Partitioning
- Notes on Spectral Analysis of Graphs.
- Daniel A. Spielman and Shang-Hua Teng. Spectral Partitioning Works: Planar graphs and finite element meshes. Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, 1996.
- Notes on Spectral Analysis of Graphs.

- Graph Partitioning

- Random Walks

- Link Analysis and Web Search
- Section 14.6 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Link Analysis and Web Search