Cornell University

Fall 2021

**Instructor: Jon Kleinberg****TAs: Katherine Van Koevering and Jing Nathan Yan.**

The past two decades has seen a convergence of social and technological networks, with systems such as the World Wide Web characterized by the interplay between rich information content, the millions of individuals and organizations who create it, and the technology that supports it. This course covers recent research on the structure and analysis of such networks, and on models that abstract their basic properties. Topics include combinatorial and probabilistic techniques for link analysis, centralized and decentralized search algorithms, network models based on random graphs, and connections with work in the social sciences.

The course prerequisites include introductory-level background in algorithms, graphs, probability, and linear algebra, as well as some basic programming experience (to be able to manipulate network datasets).

The work for the course will consist primarily of two problem sets, a short reaction paper, and a more substantial project.

(1) **Random Graphs and Small-World Properties**

- 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

(2) **Cascading Behavior in Networks**

- 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.

- 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.

- Simple Probabilistic Models of Contagion.

- 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.

(3) **Spectral Analysis and Random Walks in 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