An L^p theory of sparse graph convergence. II: LD convergence, quotients and right convergence

DOI10.1214/17-AOP1187zbMATH Open1386.05099arXiv1408.0744OpenAlexW3105212187WikidataQ59410900 ScholiaQ59410900MaRDI QIDQ1747754FDOQ1747754

Authors: Christian Borgs, Jennifer T. Chayes, Henry Cohn, Yufei Zhao 

Publication date: 27 April 2018

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: We extend the $L^p$ theory of sparse graph limits, which was introduced in a companion paper, by analyzing different notions of convergence. Under suitable restrictions on node weights, we prove the equivalence of metric convergence, quotient convergence, microcanonical ground state energy convergence, microcanonical free energy convergence, and large deviation convergence. Our theorems extend the broad applicability of dense graph convergence to all sparse graphs with unbounded average degree, while the proofs require new techniques based on uniform upper regularity. Examples to which our theory applies include stochastic block models, power law graphs, and sparse versions of $W$-random graphs.

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

Recommendations

• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Convergent sequences of sparse graphs: a large deviations approach
• Right-convergence of sparse random graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• On limits of sparse random graphs

zbMATH Keywords

graphongraph convergencegraph quotientsparse graph limit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42) Equilibrium statistical mechanics (82B99)

Cites Work

• Recurrence of distributional limits of finite planar 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. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Quick approximation to matrices and applications
• Left and right convergence of graphs with bounded degree
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• Szemerédi's lemma for the analyst
• Metrics for sparse graphs
• Convergent sequences of sparse graphs: a large deviations approach

Cited In (50)

• Graphon mean field systems
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Semantic limits of dense combinatorial objects
• Long-term stability of interacting Hawkes processes on random graphs
• Differential calculus on the space of countable labelled graphs
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• On the continuum limit of epidemiological models on graphs: convergence and approximation results
• Weighted exponential random graph models: scope and large network limits
• Graph polynomials associated with Dyson-Schwinger equations
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• The cut metric for probability distributions
• 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
• Respondent-driven sampling and sparse graph convergence
• Dynamic random networks and their graph limits
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• Continuum limit of p-Laplacian evolution problems on graphs: L^q graphons and sparse graphs
• Remarks on power-law random graphs
• The semilinear heat equation on sparse random graphs
• Action convergence of operators and graphs
• A transportation approach to the mean-field approximation
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• A detailed investigation into near degenerate exponential random graphs
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Universality of the mean-field for the Potts model
• Multivariate Hawkes processes on inhomogeneous random graphs
• On limits of sparse random graphs
• Matrix estimation, latent variable model and collaborative filtering
• Right-convergence of sparse random graphs
• An introduction to large deviations for random graphs
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• An infinite-dimensional metapopulation SIS model
• Measures on the square as sparse graph limits
• Optimal graphon estimation in cut distance
• A short proof of the equivalence of left and right convergence for sparse graphs
• Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
• Sampling and estimation for (sparse) exchangeable graphs
• A unified view of graph regularity via matrix decompositions
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
• Computational lower bounds for graphon estimation via low-degree polynomials
• Interview with Yufei Zhao
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Convergent sequences of sparse graphs: a large deviations approach
• Higher-order fluctuations in dense random graph models
• A random graph of moderate density
• Sparse exchangeable graphs and their limits via graphon processes
• Fluctuations in mean-field Ising models
• Hypergraphon mean field games

This page was built for publication: An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence

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