36781, Advanced Statistical Network Models
Minisemester II, Fall 2016
1:302:50 pm on Tuesdays and Thursdays in Wean Hall 5312
Office hours 11:0012:00 on Tuesdays in Baker Hall 229C
Recent work on infinitedimensional models of networks is based on the
related notions of graph limits and of decomposing symmetric network models
into mixtures of simpler ones. This course aims to bring students with a
working knowledge of network modeling close to the research frontier. Students
will be expected to complete projects which could be original research or
literature reviews.
Prerequisites
There are no formal prerequisites, but the intended audience consists of
students who are already familiar with networks, with statistical modeling, and
with advanced probability. Others may find it possible to keep up, but you do
so at your own risk.
Auditors are welcome, provided there is space for them in the classroom.
Topics
The class will cover the following topics, in roughly this order: exchangeable
networks; the AldousHoover representation theorem for exchangeable network
models; limits of dense graph sequences ("graphons"); connection to stochastic
block models; nonparametric estimation and comparison; approaches to sparse
graphs. Additional topics or variations will depend on time and the interests
of the class. See below for the precise list of lecture topics, subject to
revision.
Textbooks
There is no required textbook for the class. The following are recommended, in roughly decreasing order of priority:
In place of textbooks, students will be expected to read selected papers, as
indicated below.
Course Mechanics
Class will meet twice a week. This will be a combination of lecture and
seminar. Participation in class will be 50% of your grade; this will be
equally divided between attendance (mandatory, except with permission
of the professor) and scribing lecture notes, on a schedule to be determined.
There will be one assignment, the completion of a 15+ page report on
material related to the course. This may be either original research or a
literature review. All topics for reports must be approved by the professor by
the halfway point in the course. An interim report will be due three weeks
before the end of the semester, and a final report at the end of the semester.
This report will be the other 50% of your grade.
Schedule
Readings for the class will be linked in below. This is subject to revision.
 25 October, Lecture 1: Conditionallyindependent dyad processes
 Lecture notes: PDF (correcting misstatements from lecture), and Rnw source file
 27 October, Lecture 2: Exchangeable networks and the AldousHoover representation theorem
 Scribed lecture notes by Momin Malik
 Peter J. Bickel and Aiyou Chen, "A nonparametric view of network
models and NewmanGirvan and other
modularities", Proceedings
of the National Academy of Sciences (USA) 106 (2009):
2106821073
 Persi Diaconis and Svante Janson, "Graph Limits and Exchangeable Random Graphs", Rendiconti di Matematica e delle sue Applicazioni
28 (2008): 3361, arxiv:0712.2749
 Kallenberg, introduction, sections 1.1 and 1.2, and sections 7.1, 7.2, 7.3 and 7.5
 1 November, Lecture 3: Limits of dense graph sequences
 Scribed lecture notes by Nicolas Kim
 Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Balázs Szegedy and Katalin Vesztergombi,
"Graph Limits and Parameter Testing", Proceedings of the 38th Annual ACM Symposium on the Theory of Computing [STOC 2006], pp. 261270
[PDF reprint via Dr. Chayes]
 Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós and Katalin Vesztergombi, "Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing", Advances in Mathematics 219 (2008): 18011851 [PDF reprint via Dr. Chayes]
 Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós and Katalin Vesztergombi, "Convergent Sequences of
Dense Graphs II: Multiway Cuts and Statistical Physics" [PDF preprint via Dr. Borgs]
 Laszlo Lovasz, Balazs Szegedy, "Limits of dense graph
sequences",
Journal of
Combinatorial Theory B 96 (2006):
933957, arxiv:math/0408173
 3 November, Lecture 4: Graph limits and graphons
 Lecture notes
 Persi Diaconis and Svante Janson, "Graph Limits and Exchangeable Random Graphs", Rendiconti di Matematica e delle sue Applicazioni
28 (2008): 3361, arxiv:0712.2749
 8 November, Lecture 5: Laws of large numbers
 Scribed notes by Alden Green
 Instructor notes with details, complements, and exercises
 10 November: NO LECTURE
 10 November: deadline for proposing topics for your final report
 15 November, Lecture 6: Graphons and standard network models;
growing stochastic block models

 17 November, Lecture 7: Nonparametric estimation of continuous latent space models
 Scribed lecture notes by Abulhair Saparov

 Cosma Rohilla Shalizi and Dena Asta, "Consistency of Maximum Likelihood for Continuousspace Network Models" [Unpublished]
 22 November, Lecture 8: Graph comparisons
 Scribed lecture notes by Neil Spencer

 Dena Asta and Cosma Rohilla Shalizi, "Geometric Network Comparison",
pp. 102110 in Marina Meila and Tom Heskes (eds.), 31st Conference on Uncertainty in Artificial Intelligence [UAI 2015] (2015), arxiv:1411.1350
 29 November, Lecture 9: Nonparametric estimation of graphons

 Peter J. Bickel, Aiyou Chen, and Elizaveta Levina, "The method of moments and degree distributions for network models", Annals
of Statistics 39 (2011): 3859, arxiv:1202.5101
 David S. Choi, Patrick J. Wolfe, "Coclustering separately exchangeable network data", arxiv:1212.4093
 Olav Kallenberg, "Multivariate Sampling and the Estimation Problem for Exchangeable Arrays", Journal of Theoretical Probability 12 (1999): 859883
 James Robert Lloyd, Peter Orbanz, Zoubin Ghahramani and Daniel M. Roy, "Random function priors for exchangeable arrays with applications to graphs and relational data", NIPS 2012
 M. E. J. Newman and Tiago P. Peixoto, "Generalized communities in networks", Physical Review Letters 115 (2015): 088701, arxiv:1505.07478
 Patrick J. Wolfe, Sofia C. Olhede, "Nonparametric graphon estimation", arxiv:1309.5936
 29 November: Interim reports due
 1 December, Lecture 10: Nonparametric estimation of graphons, continued
 Scribed lecture notes by Seth Cobb
 6 December, Lecture 11: Nonparametric estimation of graphons, further continued
 R for inclass demos
 8 December, Lecture 12: Critique of exchangeability; approaches to sparse graph limits and sparse graphons
 Scribed lecture notes by Cristobal De La Maza

 Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei
Zhao, "An $L^p$ Theory of Sparse Graph Convergence I: Limits, Sparse Random Graph Models, and Power Law Distributions", arxiv:1401.2906
 Francois Caron, Emily B. Fox, "Bayesian nonparametric models of sparse and exchangeable random graphs", arxiv:1401.1137
 14 December: Final reports due