36-781, Advanced Statistical Network Models
Mini-semester II, Fall 2016
1:30--2:50 pm on Tuesdays and Thursdays in Wean Hall 5312
Office hours 11:00--12:00 on Tuesdays in Baker Hall 229C
Recent work on infinite-dimensional 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.
Pre-requisites
There are no formal pre-requisites, 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 Aldous-Hoover representation theorem for exchangeable network
models; limits of dense graph sequences ("graphons"); connection to stochastic
block models; non-parametric 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 half-way 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: Conditionally-independent dyad processes
- Lecture notes: PDF (correcting mis-statements from lecture), and Rnw source file
- 27 October, Lecture 2: Exchangeable networks and the Aldous-Hoover representation theorem
- Scribed lecture notes by Momin Malik
- Peter J. Bickel and Aiyou Chen, "A nonparametric view of network
models and Newman-Girvan and other
modularities", Proceedings
of the National Academy of Sciences (USA) 106 (2009):
21068--21073
- Persi Diaconis and Svante Janson, "Graph Limits and Exchangeable Random Graphs", Rendiconti di Matematica e delle sue Applicazioni
28 (2008): 33--61, 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. 261--270
[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): 1801--1851 [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):
933--957, 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): 33--61, 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 Continuous-space 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. 102--110 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): 38--59, arxiv:1202.5101
- David S. Choi, Patrick J. Wolfe, "Co-clustering separately exchangeable network data", arxiv:1212.4093
- Olav Kallenberg, "Multivariate Sampling and the Estimation Problem for Exchangeable Arrays", Journal of Theoretical Probability 12 (1999): 859--883
- 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 in-class 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