Cornell University

Spring 2018

**Instructor: Jon Kleinberg**- Office hours: 9-10am, Thursday, 318 Gates.
**Part-time TAs: Rediet Abebe, Hedyeh Beyhaghi, and Soroush Alamdari.**- Office hours: 12:30-1:30pm, Wednesday, 324 Gates.
- Office hours: 9-10am, Thursday, 318 Gates.

The past decade 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. Coursework should be handed in through CMS.

(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) **Heavy-Tailed Distributions in Networks**

- Power Laws
- M. Mitzenmacher A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.

- Power Laws

- Preferential Attachment and Rich-get-Richer Processes
- Section 18.7 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Preferential Attachment and Rich-get-Richer Processes

- Hierarchical Network Models and Zipf's Law
- J. Leskovec, J. Kleinberg, C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2005.

- Hierarchical Network Models and Zipf's Law

- Power Laws through Optimization
- A. Fabrikant, E. Koutsoupias, C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002.

- Power Laws through Optimization

(4) **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