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:

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:

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

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:

Tue Oct 13
Strategic network formation models.

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

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:

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.

Diffusion demos:

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

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]