Prof. Michael Kearns,
Tuesdays 12-3 PM (First meeting Tue Sep 15)
307 Levine Hall

URL for this page:


This seminar course will be an advanced mathematical study of the modeling of social and other large-scale networks, and the strategic issues they give rise to. Broadly speaking, in the seminar we will:

  • Examine mathematical models for network formation
  • Study the structural or topological properties these models entail
  • Compare those properties with those appearing in empirical or "natural" networks
  • Elucidate the impacts of network structure on network dynamics
  • Study the strategic and game-theoretic aspects of social and technological network models.

    To a first approximation, the seminar can be viewed as a graduate-level treatment of many the core topics covered in the Penn undergraduate course Networked Life.

    The course will draw heavily on two (required) texts:

  • Social and Economic Networks, by Matthew O. Jackson, Princeton University Press, 2008.
  • Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani, eds., Cambridge University Press, 2007.

    These books are available at the Penn Bookstore. Alternatively, both can be purchased through Amazon or other online sources.

    The current plan is to work our way sequentially through the Jackson book more or less in its entirety, supplementing it in many places with the more mathematical source papers discussed there. We will then move on to selected topics covered in the Nisan et al. volume (again with supplemental readings), focusing mainly on the chapters in which networks play an important role.

    A partial list of topics to be covered includes:

  • Empirical literature in Network Science
  • Structural properties of social and other networks: degree distributions, diameter, clustering, mixtures of local and global connectivity, and others
  • Stochastic models for network formation: random graph models, preferential attachment, small world models, configuration model, and others
  • Threshold phenomena and phase transitions in networks
  • Diffusion and contagion models in networks
  • Games on networks
  • Networked markets
  • Strategic, game-theoretic and economic network formation
  • Routing games and the price of anarchy


    This course will be run as a highly participatory seminar. While I will sometimes lead the discussions and sometimes give more formal lectures on the material, it is expected that class participants will often be responsible for leading the presentations and discussion. I tend to guide such presentations in "Oprah/O'Reilly" fashion.

    The course will meet once a week on Tuesdays from 12 to 3. Lunch will be served.

    While there are no formal prerequisites, "mathematical maturity" will be expected. Background in at least some of the following topics will be helpful: graph theory, statistics and probability theory, game theory and microeconomics, design and analysis of algorithms. If you have no exposure to any of these topics, and don't otherwise have a strong math background, you will find portions of the course difficult to follow. We will often examine formal proofs in some detail.

    Auditors and occasional participants are welcome, as are qualified undergraduates.

    The course requirements for registered students are active in-class participation, leading one week's presentation and discussion, and occasional problem sets.


    The exact timing and set of topics below will depend on our progress and will be updated as we proceed.

    Tue Sep 15
    In the first meeting, we will go over course mechanics and present a course overview, then dive right in with the preliminary and background material.

    READING: Jackson Chapters 1-3.

    RELATED LINKS: NetLogo Erdos-Renyi and preferential attachment demos.

    Tue Sep 22
    Poisson (Erdos-Renyi) random networks: degree distributions, connectivity, diameter, component sizes, threshold phenomena.

    READING: Jackson Chapter 4, and the following paper:

  • "Every Monotone Graph Property Has a Sharp Threshold". Friedgut and Kalai.

    We will at least study the main statement of the Friedgut-Kalai paper, but at most sketch the high-level tools and argument, so don't sweat the math if it's beyond your background. However, for you aficionados/gluttons out there, here is a link to the awesome course page of Ryan O'Donnell at CMU on the unbelievable variety of applications of the influence of functions.

    Tue Sep 29
    More stochastic network formation: Erods-Renyi continued, preferential attachment, small worlds, configuration model, and others; structural properties entailed (and not entailed) by each model.

    READING: Jackson Chapter 5.

    Problem Set 1 (due as hardcopy in our Oct 27 meeting --- NOTE CHANGE OF DATE AND ADDITION OF PROBLEMS 4.5 and 6.11): Jackson problems 1.2, 1.3, 1.4, 4.5, 4.7, 5.1, 6.1, 6.5, 6.11. Also, prove the Erdos-Gallai theorem, and then use it to prove that most sequences of integers in 0,...,n-1 whose sum is even are in fact degree sequences of undirected graphs over n vertices. Collaboration policy: It is fine if you discuss the problem set with others, but I ask that everyone submit their own separate write-up, and that you acknowledge your collaborators by name on your write-up. See Oct 27 entry below for problem presentation volunteers.

    Tue Oct 6
    Still more stochastic network formation: clustering, Watts-Strogatz, and Kleinberg's model. Discussion of Problem Set 1.

    READING: Jackson Chapter 5. We will also be discussing the following papers:

  • The Small World Phenomenon: An Algorithmic Perspective, Kleinberg.
  • The Scaling Laws of Human Travel. Brockmann, Hufnagel, Geisel.

    Tue Oct 13
    Strategic network formation models.

    READING: Jackson Chapter 6. We will also discuss the following paper:

  • A Small World Threshold for Economic Network Formation. Even-Dar and MK.

    Tue Oct 20

    Tue Oct 27
    Strategic network formation, continued; class presentation of Problem Set 1 solutions. Problem presentation volunteers: 1.2 (Ryan); 1.3 (Rene); 1.4 (Jenny); 4.5 (Varun); 4.7 (Sudeepa); 5.1 (Wendy); 6.1 (Andres); 6.5 (Anand); 6.11 (Jun); Erdos-Gallai problem (Michael Z.)

    READING: We will discuss material in the following paper and slides:

  • Slides on Network Formation. Aleksandr Nikolov, Rutgers doctoral student.
  • The Price of Stability for Network Design with Fair Cost Allocation. Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler, Roughgarden.

    Tue Nov 3
    Continued class presentation of Problem Set 1 solutions.

    Tue Nov 10
    Diffusion in networks; graphical games and networked markets.

    READING: Jackson Chapter 7 (diffusion), Chapter 10 (networked markets); AGT book Chapter 7.

  • Graphical Games Slides

    Diffusion demos:

  • Bass Model
  • Forest Fire
  • Epidemic
  • NetLogo Virus

    In the remaining 4 meetings (Nov 17, Nov 24, Dec 1, Dec 8), I would like registered students to form groups to present the topics listed below; I can be flexible about which topics are presented on which dates, but obviously not everyone can go last. I would guesstimate that each topic should take about an hour of meeting time, including discussion. I will also still be jumping in with various topics as well.

    Tue Nov 17
    Graphical games continued; networked markets.

    READING: AGT book Chapter 7 (graphical games); Jackson Chapter 10 (networked markets).

  • Graphical Games Slides
  • Networked Trade Slides
  • Networked Trade Formation Game Slides

    Tue Nov 24
    Class presentations:

    Routing Games (AGT book Chapter 18 and supplementary material); Presenters: Kook Jin Ahn, Daniel Wagner
    Incentives and Information Security (AGT book Chapter 25 and supplementary material); Presenters: Adam Aviv, Sushmita Gupta,   Vilhelm Sjoberg
    Learning in Networks (Jackson Chapter 8 and supplementary material); Presenters: Arastoo Fazeli, Pooya Molavi, and Ceyhun Eksin

    Tue Dec 1
    Class presentations:

    Learning in Networks, continued (Jackson Chapter 8 and supplementary material); Presenters: Arastoo Fazeli, Pooya Molavi, and Ceyhun Eksin
    Distributed Algorithmic Mechanism Design (AGT book Chapter 14 and supplementary material); Presenters: Kareem Amin, David Weiss

    Tue Dec 8
    Our final meeting! Class presentations:

    Incentives and Pricing in Communications Networks (AGT book Chapter 22 and supplementary material); Presenters: Changbin Liu,   Qi Zhang, and Zhiyi Huang.
    Incentives in Peer-to-Peer Systems (AGT book Chapter 23 and supplementary material); Presenters: Weiyu Zhang and Oleg Naroditsky
    Local Algorithms for Finding Interesting Individuals in Large Networks; Presenter: Mickey Brautbar   [paper]