Higher-Order Graphon and Permuton Theories: Fluctuations, Inference, and Degeneracies
Presenter
September 30, 2023
Abstract
Motifs (patterns of subgraphs), such as edges and triangles, encode important structural information about the geometry of a network. Consequently, counting motifs in a large network is an important statistical and computational problem. In this talk we will consider the problem of estimating motif densities and fluctuations of subgraph counts in an inhomogeneous random graph sampled from a graphon. We will show that the limiting distributions of subgraph counts can be Gaussian or non-Gaussian, depending on a notion of regularity of subgraphs with respect to the graphon. Using these results and a novel multiplier bootstrap for graphons, we will construct confidence intervals for the motif densities. We will also present parallel results for patterns in random permutations through the lens of permuton theory. Finally, we will discuss various structure theorems and open questions about degeneracies of the limiting distribution.