A time-invariant random graph with splitting events

DOI10.1214/21-ECP436MaRDI QIDQ2078234zbMATH OpenFDO

Authors John Haslegrave, Agelos Georgakopoulos

Publication date 28 February 2022

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.09630

zbMATH Keywords

birth processconvergencerandom graphsreproducing graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: We introduce a process where a connected rooted multigraph evolves by splitting events on its vertices, occurring randomly in continuous time. When a vertex splits, its incoming edges are randomly assigned between its offspring and a Poisson random number of edges are added between them. The process is parametrised by a positive real $lambda$ which governs the limiting average degree. We show that for each value of $lambda$ there is a unique random connected rooted multigraph $M(lambda)$ invariant under this evolution. As a consequence, starting from any finite graph $G$ the process will almost surely converge in distribution to $M(lambda)$, which does not depend on $G$. We show that this limit has finite expected size. The same process naturally extends to one in which connectedness is not necessarily preserved, and we give a sharp threshold for connectedness of this version. This is an asynchronous version, which is more realistic from the real-world network point of view, of a process we studied in arXiv:1506.02697, arXiv:1703.09011.

Recommendations

• On a random graph evolving by degrees
• Continuous-time independent edge-Markovian random graph process
• The split-and-drift random graph, a null model for speciation
• Evolution of random graph processes with degree constraints
• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics

Cites work

• Analyticity Results in Bernoulli Percolation
• Asymptotic degree distribution of a duplication-deletion random graph model
• Evolving protein interaction networks through gene duplication
• Existence of phase transition for percolation using the Gaussian free field
• Further properties of a random graph with duplications and deletions
• Group-Walk Random Graphs
• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 3555176 (Why is no real title available?)
• Models of online social networks
• Percolation on an infinitely generated group
• Randomised reproducing graphs
• The degree distribution of the generalized duplication model
• The split-and-drift random graph, a null model for speciation

Cited in

(2)

• Asymptotic properties of stochastic timed event graphs
• The split-and-drift random graph, a null model for speciation

This page was built for publication: A time-invariant random graph with splitting events

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078234)