An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
From MaRDI portal
Publication:5227976
Abstract: We introduce and develop a theory of limits for sequences of sparse graphs based on graphons, which generalizes both the existing 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 theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper.
Recommendations
Cites work
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1944144 (Why is no real title available?)
- scientific article; zbMATH DE number 2042286 (Why is no real title available?)
- A Brief History of Generative Models for Power Law and Lognormal Distributions
- A generalization of Hölder's inequality and some probability inequalities
- A model theory approach to structural limits.
- A nonparametric view of network models and Newman–Girvan and other modularities
- A relative Szemerédi theorem
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- An efficient sparse regularity concept
- Asymptotic Enumeration of Spanning Trees
- Bounds for graph regularity and removal lemmas
- Convergence of graphs with intermediate density
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Extremal results in sparse pseudorandom graphs
- Graphons, cut norm and distance, couplings and rearrangements
- Large networks and graph limits
- Limits of dense graph sequences
- Metrics for sparse graphs
- Modeling limits in hereditary classes: reduction and application to trees
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- On replica symmetry of large deviations in random graphs
- Power-law distributions in empirical data
- Probability. Theory and examples.
- Processes on unimodular random networks
- Quick approximation to matrices and applications
- Recurrence of distributional limits of finite planar graphs
- Sparsity. Graphs, structures, and algorithms
- Szemerédi's lemma for the analyst
- Szemerédi's regularity Lemma for matrices and sparse graphs
- Szemerédi’s Regularity Lemma for Sparse Graphs
- The large deviation principle for the Erdős-Rényi random graph
- The primes contain arbitrarily long arithmetic progressions
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(68)- Szemerédi's regularity lemma via martingales
- Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
- Optimal couplings between sparse block models
- Spectral properties for the Laplacian of a generalized Wigner matrix
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- On limits of sparse random graphs
- Long time dynamics for interacting oscillators on graphs
- An introduction to large deviations for random graphs
- The dynamics of non-perturbative phases via Banach bundles
- A unified view of graph regularity via matrix decompositions
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Universality of the mean-field for the Potts model
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- An infinite-dimensional metapopulation SIS model
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- Symmetric graph properties have independent edges
- Higher-order fluctuations in dense random graph models
- Bootstrapping exchangeable random graphs
- Semantic limits of dense combinatorial objects
- Remarks on power-law random graphs
- Cut norm discontinuity of triangular truncation of graphons
- Interview with Yufei Zhao
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
- Measures on the square as sparse graph limits
- Sampling perspectives on sparse exchangeable graphs
- Bifurcations in the Kuramoto model on graphs
- Approximating sparse graphs: The random overlapping communities model
- Optimal graphon estimation in cut distance
- Sparse graphs: metrics and random models
- Fluctuations in mean-field Ising models
- Action convergence of operators and graphs
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- On the dense preferential attachment graph models and their graphon induced counterpart
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Random walks on dense graphs and graphons
- Relating the cut distance and the weak* topology for graphons
- A detailed investigation into near degenerate exponential random graphs
- Identifiability for graphexes and the weak kernel metric
- The large deviation principle for interacting dynamical systems on random graphs
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- The Kuramoto model on power law graphs: synchronization and contrast states
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- A statistical mechanical model for non-perturbative regimes
- The semilinear heat equation on sparse random graphs
- Sparse Monte Carlo method for nonlocal diffusion problems
- Differential calculus on the space of countable labelled graphs
- Multivariate Hawkes processes on inhomogeneous random graphs
- Sparse exchangeable graphs and their limits via graphon processes
- Sampling and estimation for (sparse) exchangeable graphs
- An algorithmic regularity lemma for \(L_p\) regular sparse matrices
- Random graph asymptotics for treatment effect estimation under network interference
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- Graph polynomials associated with Dyson-Schwinger equations
- Projective, sparse and learnable latent position network models
- Subgraph densities in Markov spaces
- Kontsevich Graphons
- Computational lower bounds for graphon estimation via low-degree polynomials
- Graphon mean field systems
- Hypergraphon mean field games
- Graphon games: a statistical framework for network games and interventions
- Pattern Formation in Random Networks Using Graphons
- Non-representative sampled networks: estimation of network structural properties by weighting
- On the continuum limit of epidemiological models on graphs: convergence and approximation results
- Tractably modelling dependence in networks beyond exchangeability
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- Continuum limit of p-Laplacian evolution problems on graphs: Lq graphons and sparse graphs
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)
