Limits of randomly grown graph sequences
From MaRDI portal
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
(47)- A series criterion for the almost-sure growth rate of the generalized diameter of an increasing sequence of random points
- Consensus and voting on large graphs: an application of graph limit theory
- Large deviations for the degree structure in preferential attachment schemes
- The Kuramoto model on power law graphs: synchronization and contrast states
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- A noncommutative approach to the graphon Fourier transform
- Multivariate Hawkes processes on inhomogeneous random graphs
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- Limit for the Euler-genus distributions of ladder-like sequences of graphs
- Preferential attachment without vertex growth: emergence of the giant component
- On random walk on growing graphs
- Limits of random trees. II
- Linear embeddings of graphs and graph limits
- Uniqueness of Banach space valued graphons
- Limit laws for UGROW random graphs
- An example of graph limits of growing sequences of random graphs
- The nonlinear heat equation on \(W\)-random graphs
- Limits of vertex replacement rules
- Dynamic random networks and their graph limits
- Continuum limits for classical sequential growth models
- Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
- Dense graph limits under respondent-driven sampling
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Nonlocal p-Laplacian evolution problems on graphs
- Growing random graphs with a preferential attachment structure
- \(\Gamma\)-limit of the cut functional on dense graph sequences
- Continuum limits of nonlocal p-Laplacian variational problems on graphs
- Continuum limit of the nonlocal p-Laplacian evolution problem on random inhomogeneous graphs
- Random walks on dense graphs and graphons
- On the dense preferential attachment graph models and their graphon induced counterpart
- Modularity Maximization for Graphons
- Pattern Formation in Random Networks Using Graphons
- Long-term stability of interacting Hawkes processes on random graphs
- Graph sequences sampled from Robinson graphons
- Tangent graphs
- Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
- Contagion in graphons
- Graphon games: a statistical framework for network games and interventions
- Hypergraphon mean field games
- Individual-based SIS models on (not so) dense large random networks
- On network-based epidemiological models: analysis, simulations, and continuum limit
- Continuous limits of large plant-pollinator random networks and some applications
- Persistence of steady states for dynamical systems on large networks
- The ``zero charge problem via graphon processes
- Uniform linear embeddings of graphons
- Urn modeling of random graphs across granularity scales: a framework for origin-destination human mobility networks
- Inverse graph limit problem of the graphon multi-agent systems
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)
