An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
From MaRDI portal
(Redirected from Publication:5227976)
An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
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
(85)- Identifiability for graphexes and the weak kernel metric
- On the dense preferential attachment graph models and their graphon induced counterpart
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Graphon mean field systems
- Differential calculus on the space of countable labelled graphs
- Semantic limits of dense combinatorial objects
- Social optima in linear quadratic graphon field control: analysis via infinite dimensional approach
- Graph limit and exponential consensus for the large-scale multi-agent system with delay
- Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
- Sparse Monte Carlo method for nonlocal diffusion problems
- Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
- On the continuum limit of epidemiological models on graphs: convergence and approximation results
- Mean-field limit of non-exchangeable systems
- Long time dynamics for interacting oscillators on graphs
- Graph polynomials associated with Dyson-Schwinger equations
- Approximating sparse graphs: The random overlapping communities model
- Spectral properties for the Laplacian of a generalized Wigner matrix
- Sampling perspectives on sparse exchangeable graphs
- An algorithmic regularity lemma for L_p regular sparse matrices
- The Kuramoto model on power law graphs: synchronization and contrast states
- A compactification of the set of sequences of positive real numbers with applications to limits of graphs (extended abstract)
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
- Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems
- Kontsevich Graphons
- A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
- The sparse regularity method with Schatten norms and entropy
- Bootstrapping exchangeable random graphs
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Continuum limit of p-Laplacian evolution problems on graphs: Lq graphons and sparse graphs
- Remarks on power-law random graphs
- Global stability for McKean-Vlasov equations on large networks
- The semilinear heat equation on sparse random graphs
- Action convergence of operators and graphs
- A detailed investigation into near degenerate exponential random graphs
- LDP for inhomogeneous U-statistics
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Universality of the mean-field for the Potts model
- Symmetric graph properties have independent edges
- Higher-Order Accurate Two-Sample Network Inference and Network Hashing
- Optimal couplings between sparse block models
- On limits of sparse random graphs
- Projective, sparse and learnable latent position network models
- Subgraph densities in Markov spaces
- Multivariate Hawkes processes on inhomogeneous random graphs
- The mean-field limit of sparse networks of integrate-and-fire neurons
- Cut norm discontinuity of triangular truncation of graphons
- The large deviation principle for interacting dynamical systems on random graphs
- Neural fields and noise-induced patterns in neurons on large disordered networks
- An introduction to large deviations for random graphs
- On network-based epidemiological models: analysis, simulations, and continuum limit
- Relating the cut distance and the weak* topology for graphons
- An infinite-dimensional metapopulation SIS model
- Non-representative sampled networks: estimation of network structural properties by weighting
- Measures on the square as sparse graph limits
- A statistical mechanical model for non-perturbative regimes
- Optimal graphon estimation in cut distance
- Tractably modelling dependence in networks beyond exchangeability
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- Mean-field limit of nonexchangeable interacting diffusions with singular kernels
- Conformal Prediction for Network-Assisted Regression
- Sampling and estimation for (sparse) exchangeable graphs
- Szemerédi's regularity lemma via martingales
- The dynamics of non-perturbative phases via Banach bundles
- 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
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Interview with Yufei Zhao
- Bifurcations in the Kuramoto model on graphs
- Sparse graphs: metrics and random models
- Pattern Formation in Random Networks Using Graphons
- Higher-order fluctuations in dense random graph models
- The ``zero charge problem via graphon processes
- Graphon mean-field backward stochastic differential equations with jumps and associated dynamic risk measures
- Graphon games: a statistical framework for network games and interventions
- Sparse exchangeable graphs and their limits via graphon processes
- Fluctuations in mean-field Ising models
- Random graph asymptotics for treatment effect estimation under network interference
- Random walks on dense graphs and graphons
- Hypergraphon mean field games
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)
