Randomised reproducing graphs

DOI10.1214/EJP.V16-921MaRDI QIDQ428534zbMATH OpenOpenAlexFDO

Authors Jonathan H. Jordan

Publication date 22 June 2012

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

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

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)

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.

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

Cited in

(10)

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

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)