An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions

DOI10.1090/tran/7543zbMath1417.05186arXiv1401.2906OpenAlexW3101333414WikidataQ114848703 ScholiaQ114848703MaRDI QIDQ5227976

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

Publication date: 7 August 2019

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

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

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)

Related Items (55)

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

Uses Software

• plfit

Cites Work

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

This page was built for publication: An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions