Seminar

Registration required to attend.

Graphons and graphexes are limits of graphs that allow us to model and estimate properties of large-scale networks. Graphons are by now widely used in theory and applications; indeed, they are the topic of much of the Simons Institute’s semester program on Graph Limits and Processes on Networks: From Epidemics to Misinformation. For dense graphs, there are many equivalent ways to define the limit, some more global and others more local in nature. For sparse graphs of unbounded degree, there are two alternative theories for finding the limits — a probabilistic approach that leads to bounded graphons over probability spaces, and a statistical approach leading to graphexes over sigma-finite measure spaces. The former is in many ways the extension of the “global approach” for dense graphs. For some time, it was believed that there was no natural way to extend the local notions to sparse graphs. However, the statistical approach finally emerged, and that is what this talk will focus on. After a very brief review of the theory for dense graphs and the probabilistic approach for sparse graphs, this talk will formulate the statistical approach. It will recast limits of dense graphs in terms of exchangeability and the Aldous-Hoover theorem, and then generalize this 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 that allows a generalization of many of the well-known results and techniques for dense graph sequences. This statistical approach is better suited to describing the evolution of large sparse networks.