Sparse exchangeable graphs and their limits via graphon processes

zbMATH Open1469.60158arXiv1601.07134MaRDI QIDQ4558542FDOQ4558542

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

Publication date: 22 November 2018

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.

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

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

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)

Cites Work

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

Cited In (42)

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