Kai Lai Chung Lecture: Jennifer Chayes (University of California, Berkeley)

Thursday 2:10-3:10

Title: Graphons and Graphexes as Limits and Models of Large Sparse Graphs

Abstract: Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. I start with the theory of dense graph limits, and then give two alternative approaches for limits of sparse graphs (those that occur most often in nature) — one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons and graphexes over sigma-finite measure spaces. I then recast the limits of dense graphs in terms of exchangeability and the Aldous-Hoover Theorem, and generalize this using Kallenberg’s Theorem to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.