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

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