Limits of randomly grown graph sequences
From MaRDI portal
Publication:648961
Abstract: Motivated in part by various sequences of graphs growing under random rules (like internet models), convergent sequences of dense graphs and their limits were introduced by Borgs, Chayes, Lov'asz, S'os and Vesztergombi and by Lov'asz and Szegedy. In this paper we use this framework to study one of the motivating class of examples, namely randomly growing graphs. We prove the (almost sure) convergence of several such randomly growing graph sequences, and determine their limit. The analysis is not always straightforward: in some cases the cut distance from a limit object can be directly estimated, in other case densities of subgraphs can be shown to converge.
Recommendations
Cites work
- An analytic approach to stability
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Counting graph homomorphisms
- Limits of dense graph sequences
- Moments of two-variable functions and the uniqueness of graph limits
- On a random graph evolving by degrees
- Quick approximation to matrices and applications
- Statistical mechanics of complex networks
- Threshold graph limits and random threshold graphs
Cited in
(40)- On the dense preferential attachment graph models and their graphon induced counterpart
- Long-term stability of interacting Hawkes processes on random graphs
- Continuum limit of the nonlocal \(p\)-Laplacian evolution problem on random inhomogeneous graphs
- Graph sequences sampled from Robinson graphons
- Preferential attachment without vertex growth: emergence of the giant component
- On random walk on growing graphs
- Continuum limits for classical sequential growth models
- Uniqueness of Banach space valued graphons
- Limits of random trees. II
- The Kuramoto model on power law graphs: synchronization and contrast states
- Limit for the Euler-genus distributions of ladder-like sequences of graphs
- Dynamic random networks and their graph limits
- Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
- \(\Gamma\)-limit of the cut functional on dense graph sequences
- Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs
- Modularity Maximization for Graphons
- Tangent graphs
- Multigraph limit of the dense configuration model and the preferential attachment graph
- An example of graph limits of growing sequences of random graphs
- Multivariate Hawkes processes on inhomogeneous random graphs
- Consensus and voting on large graphs: an application of graph limit theory
- Nonlocal \(p\)-Laplacian evolution problems on graphs
- Uniform linear embeddings of graphons
- Individual-based SIS models on (not so) dense large random networks
- A noncommutative approach to the graphon Fourier transform
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- Dense graph limits under respondent-driven sampling
- Large deviations for the degree structure in preferential attachment schemes
- Contagion in graphons
- Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
- Linear embeddings of graphs and graph limits
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Limit laws for UGROW random graphs
- Pattern Formation in Random Networks Using Graphons
- Growing random graphs with a preferential attachment structure
- Graphon games: a statistical framework for network games and interventions
- The nonlinear heat equation on \(W\)-random graphs
- Limits of vertex replacement rules
- Random walks on dense graphs and graphons
- Hypergraphon mean field games
This page was built for publication: Limits of randomly grown graph sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648961)
