Limits of randomly grown graph sequences
From MaRDI portal
Publication:648961
DOI10.1016/J.EJC.2011.03.015zbMATH Open1229.05247arXiv0905.3806OpenAlexW2149695599WikidataQ106143994 ScholiaQ106143994MaRDI QIDQ648961FDOQ648961
Authors: Christian Borgs, Katalin Vesztergombi, Jennifer T. Chayes, Vera T. Sós, László Lovász 
Publication date: 29 November 2011
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0905.3806
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42) Infinite graphs (05C63)
Cites Work
- Statistical mechanics of complex networks
- Limits of dense graph sequences
- Moments of two-variable functions and the uniqueness of graph limits
- Counting graph homomorphisms
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Quick approximation to matrices and applications
- Threshold graph limits and random threshold graphs
- An analytic approach to stability
- On a random graph evolving by degrees
Cited In (40)
- 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
- Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
- Dynamic random networks and their graph limits
- \(\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
- Individual-based SIS models on (not so) dense large random networks
- Uniform linear embeddings of graphons
- 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
- Pattern Formation in Random Networks Using Graphons
- Limit laws for UGROW random graphs
- 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
- Hypergraphon mean field games
- Random walks on dense graphs and graphons
- On the dense preferential attachment graph models and their graphon induced counterpart
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)
