An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions

DOI10.1090/TRAN/7543zbMATH Open1417.05186arXiv1401.2906OpenAlexW3101333414WikidataQ114848703 ScholiaQ114848703MaRDI QIDQ5227976FDOQ5227976

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

Publication date: 7 August 2019

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^{i}nfty$ theory of dense graph limits and its extension by Bollob'as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. In this paper, we lay the foundations of the $L^p$ theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper.

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

Recommendations

• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• On limits of sparse random graphs
• Measures on the square as sparse graph limits
• Metrics for sparse graphs
• Sparse graphs: metrics and random models

zbMATH Keywords

\(L^p\) theory of graphonssequences of sparse graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Density (toughness, etc.) (05C42)

Cites Work

• Power-Law Distributions in Empirical Data
• A nonparametric view of network models and Newman–Girvan and other modularities
• Limits of dense graph sequences
• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Probability
• Title not available (Why is that?)
• Asymptotic Enumeration of Spanning Trees
• Processes on unimodular random networks
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Extremal results in sparse pseudorandom graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• The primes contain arbitrarily long arithmetic progressions
• An Efficient Sparse Regularity Concept
• Sparsity. Graphs, structures, and algorithms
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• A relative Szemerédi theorem
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Quick approximation to matrices and applications
• On replica symmetry of large deviations in random graphs
• Convergence of graphs with intermediate density
• The large deviation principle for the Erdős-Rényi random graph
• Szemerédi's lemma for the analyst
• Bounds for graph regularity and removal lemmas
• Szemerédi’s Regularity Lemma for Sparse Graphs
• A Model Theory Approach to Structural Limits
• Graphons, cut norm and distance, couplings and rearrangements
• Szemerédi's Regularity Lemma for Matrices and Sparse Graphs
• Title not available (Why is that?)
• A generalization of Hölder's inequality and some probability inequalities
• Metrics for sparse graphs
• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• Modeling limits in hereditary classes: reduction and application to trees

Cited In (62)

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Semantic limits of dense combinatorial objects
• Differential calculus on the space of countable labelled graphs
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• The Semilinear Heat Equation on Sparse Random Graphs
• Long time dynamics for interacting oscillators on graphs
• Spectral properties for the Laplacian of a generalized Wigner matrix
• Sampling perspectives on sparse exchangeable graphs
• The Kuramoto model on power law graphs: synchronization and contrast states
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Identifiability for Graphexes and the Weak Kernel Metric
• Kontsevich Graphons
• 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
• Bootstrapping exchangeable random graphs
• Remarks on power-law random graphs
• Action convergence of operators and graphs
• A detailed investigation into near degenerate exponential random graphs
• Optimal couplings between sparse block models
• 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
• Cut norm discontinuity of triangular truncation of graphons
• The large deviation principle for interacting dynamical systems on random graphs
• An introduction to large deviations for random graphs
• Relating the cut distance and the weak* topology for graphons
• A statistical mechanical model for non-perturbative regimes
• Random Walks on Dense Graphs and Graphons
• An infinite-dimensional metapopulation SIS model
• Measures on the square as sparse graph limits
• Optimal graphon estimation in cut distance
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
• Sampling and estimation for (sparse) exchangeable graphs
• Szemerédi's regularity lemma via martingales
• A unified view of graph regularity via matrix decompositions
• The dynamics of non-perturbative phases via Banach bundles
• Sparse Monte Carlo Method for Nonlocal Diffusion Problems
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
• Interview with Yufei Zhao
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Bifurcations in the Kuramoto model on graphs
• Pattern Formation in Random Networks Using Graphons
• Higher-order fluctuations in dense random graph models
• Symmetric Graph Properties Have Independent Edges
• An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices
• Fluctuations in mean-field Ising models
• Random graph asymptotics for treatment effect estimation under network interference
• Graphon mean field systems
• On the continuum limit of epidemiological models on graphs: convergence and approximation results
• Graph polynomials associated with Dyson-Schwinger equations
• Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
• Projective, sparse and learnable latent position network models
• Subgraph densities in Markov spaces
• Non-representative sampled networks: estimation of network structural properties by weighting
• Tractably modelling dependence in networks beyond exchangeability
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• Computational lower bounds for graphon estimation via low-degree polynomials
• Graphon games: a statistical framework for network games and interventions
• Hypergraphon mean field games

Uses Software

• plfit

This page was built for publication: An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions

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