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 courseNetworked Life. The course will draw heavily on two (required) texts:
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
COURSE FORMAT, REQUIREMENTS, AND PREREQUISITES 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.
DETAILED MEETING/TOPIC SCHEDULE 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: NetLogoErdos-Renyiandpreferential attachmentdemos. 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 theawesome 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 NO CLASS THIS WEEK. 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,andZhiyi 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]