Randomised reproducing graphs

DOI10.1214/EJP.V16-921zbMATH Open1244.05211arXiv1104.3679OpenAlexW2144140032MaRDI QIDQ428534FDOQ428534

Authors: Jonathan H. Jordan 

Publication date: 22 June 2012

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: We introduce a model for a growing random graph based on simultaneous reproduction of the vertices. The model can be thought of as a generalisation of the reproducing graphs of Southwell and Cannings and Bonato et al to allow for a random element, and there are three parameters, $alpha$, $$ and $gamma$, which are the probabilities of edges appearing between different types of vertices. We show that as the probabilities associated with the model vary there are a number of phase transitions, in particular concerning the degree sequence. If $(1+alpha)(1+gamma)<1$ then the degree distribution converges to a stationary distribution, which in most cases has an approximately power law tail with an index which depends on $alpha$ and $gamma$. If $(1+alpha)(1+gamma)>1$ then the degree of a typical vertex grows to infinity, and the proportion of vertices having any fixed degree $d$ tends to zero. We also give some results on the number of edges and on the spectral gap.

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

Recommendations

• Further properties of a random graph with duplications and deletions
• Phase transition on the degree sequence of a random graph process with vertex copying and deletion
• Growing Protean Graphs
• A general model of web graphs
• A Markov chain approach to randomly grown graphs

zbMATH Keywords

phase transitionrandom graphsdegree distributionreproducing graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Stochastic processes (60G99)

Cited In (9)

• Further properties of a random graph with duplications and deletions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Chris Cannings: a life in games
• Insertion-tolerance and repetitiveness of random graphs
• Approximation to the moments of ratios of cumulative sums
• Asymptotic Properties of a Random Graph with Duplications
• A time-invariant random graph with splitting events
• The connected component of the partial duplication graph
• Pseudorandom Graphs in Data Structures

This page was built for publication: Randomised reproducing graphs

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