Sparse exchangeable graphs and their limits via graphon processes

MaRDI QIDQ4558542zbMATHFDO

Authors Henry Cohn, Nina Holden, Christian Borgs, Jennifer T. Chayes

Publication date 22 November 2018

Full work available at URL https://arxiv.org/abs/1601.07134

zbMATH Keywords

graph convergencegraphonsexchangeable graph modelsmodelling of sparse networkssparse graph convergence

Mathematics Subject Classification ID

Multivariate analysis (62H99) Applications of graph theory (05C90) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Random measures (60G57) Exchangeability for stochastic processes (60G09)

Abstract: In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in $mathbb{R}_{+}$. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over $sigma$-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a $sigma$-finite measure space $(S,mathcalS,mu)$ and the connection probabilities by an integrable function $WcolonSimesSo[0,1]$, we construct a random family $(G_t{)}_{tgeq0}$ of growing graphs such that the vertices of $G_t$ are given by a Poisson point process on $S$ with intensity $tmu$, with two points $x,y$ of the point process connected with probability $W(x,y)$. We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on $mathbb{R}_{+}$ equipped with Lebesgue measure.

Recommendations

• Sampling perspectives on sparse exchangeable graphs
• Identifiability for graphexes and the weak kernel metric
• On edge exchangeable random graphs
• Measures on the square as sparse graph limits
• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 3443893 (Why is no real title available?)
• A nonparametric view of network models and Newman–Girvan and other modularities
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Counting graph homomorphisms
• Essentials of integration theory for analysis
• Graph limits and exchangeable random graphs
• Graphons, cut norm and distance, couplings and rearrangements
• Latent Space Approaches to Social Network Analysis
• Left and right convergence of graphs with bounded degree
• Limits of dense graph sequences
• Matrix estimation by universal singular value thresholding
• Metrics for sparse graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Oracle inequalities for network models and sparse graphon estimation
• Probabilistic Symmetries and Invariance Principles
• Probability and stochastics.
• Probability theory. An analytic view.
• Quick approximation to matrices and applications
• Rate-optimal graphon estimation
• Representations for partially exchangeable arrays of random variables
• Sparse graphs using exchangeable random measures
• Spectral clustering and the high-dimensional stochastic blockmodel
• Stochastic blockmodels with a growing number of classes
• Szemerédi's lemma for the analyst
• The method of moments and degree distributions for network models
• The phase transition in inhomogeneous random graphs

Cited in

(44)

• On edge exchangeable random graphs
• Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
• On convergence for graphexes
• A statistical framework for modern network science
• Graph polynomials associated with Dyson-Schwinger equations
• Sparse graphs using exchangeable random measures
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Asymptotic behavior of common connections in sparse random networks
• Projective, sparse and learnable latent position network models
• Subgraph densities in Markov spaces
• Kontsevich Graphons
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• The dynamics of non-perturbative phases via Banach bundles
• Exchangeable trait allocations
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• The cut metric for probability distributions
• Higher-order fluctuations in dense random graph models
• Remarks on power-law random graphs
• Local exchangeability
• Sampling perspectives on sparse exchangeable graphs
• Action convergence of operators and graphs
• Sparse maximum-entropy random graphs with a given power-law degree distribution
• Pattern Formation in Random Networks Using Graphons
• Bootstrap estimators for the tail-index and for the count statistics of graphex processes
• Graph limits and exchangeable random graphs
• Non-perturbative graph languages, halting problem and complexity
• On sparsity, power-law, and clustering properties of graphex processes
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Random walks on dense graphs and graphons
• Truncated simulation and inference in edge-exchangeable networks
• Identifiability for graphexes and the weak kernel metric
• Local 2-separators
• A statistical mechanical model for non-perturbative regimes
• Exchangeable graph-valued Feller processes
• Tractably modelling dependence in networks beyond exchangeability
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• The complexities of nonperturbative computations
• Sampling and estimation for (sparse) exchangeable graphs
• From Dyson-Schwinger equations to quantum entanglement
• The analytic evolution of Dyson-Schwinger equations via homomorphism densities
• Limit theorems for distributions invariant under groups of transformations

This page was built for publication: Sparse exchangeable graphs and their limits via graphon processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558542)