Sparse exchangeable graphs and their limits via graphon processes

MaRDI QIDQ4558542zbMATH OpenFDO

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, http://jmlr.csail.mit.edu/papers/v18/16-421.html

zbMATH Keywords

exchangeable graph modelsgraph convergencegraphonsmodelling of sparse networkssparse graph convergence

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(50)

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

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)