Cornell University

Spring 2011

**Instructor: Jon Kleinberg**- Office hours: 2:15-3:00 pm, Monday and Wednesday, 5134 Upson.
**TA: Sigal Oren**- Office hours: 2:15-3:00 pm, Monday and Wednesday, 5134 Upson.

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.

- Problem Set 1. (due 2/11)
- Problem Set 2. (due 2/25)

(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) **Game-Theoretic Models of Behavior in Networks**

- Game-Theoretic Models of Network Formation
- Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker, On a Network Creation Game. In Proc. of 2003 PODC, pages 347-351.

- Game-Theoretic Models of Network Formation

- Strategic Behavior in Network Cost-Sharing
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS 2004.

- Strategic Behavior in Network Cost-Sharing

- Network Models of Markets
- R. Kranton, D. Minehart. A Theory of Buyer-Seller Networks. American Economic Review, 91(30), June 2001, pp. 485--508.
- Section 15.9 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
- R. Kranton, D. Minehart. A Theory of Buyer-Seller Networks. American Economic Review, 91(30), June 2001, pp. 485--508.

- Network Models of Markets

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

(6) **Clustering and Communities in Networks**

- Hierarchical Clustering of Networks
- Section 3.6 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Hierarchical Clustering of Networks

- Minimum Cuts for Graph Partitioning
- Yuri Boykov, Olga Veksler and Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence vol. 23, no. 11 pages 1222-1239 (2001).
- Avrim Blum, Shuchi Chawla. Learning from Labeled and Unlabeled Data using Graph Mincuts. International Conference on Machine Learning (ICML), 2001.
- Gary Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Technical Report 2002-06, NEC, Princeton, NJ, 2002.
- Yuri Boykov, Olga Veksler and Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence vol. 23, no. 11 pages 1222-1239 (2001).

- Minimum Cuts for Graph Partitioning

- Enumerating Small Communities
- R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Trawling the web for emerging cyber-communities. 8th International World Wide Web Conference, May 1999.
- R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules. 20th Int'l Conference on Very Large Databases (VLDB), 1994.
- R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Trawling the web for emerging cyber-communities. 8th International World Wide Web Conference, May 1999.

- Enumerating Small Communities

- Partitioning Signed Networks: Structural Balance Theory
- Section 5.5 of D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

- Partitioning Signed Networks: Structural Balance Theory