Asymptotic properties of a random graph with duplications

2013/08/07 by Ágnes Backhausz, Backhausz, Ágnes, Tamás F. Móri +1 · 1 citation
Mathematics · #05C80 #60G42 #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1308.1506

openalex publication_date 2013/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We deal with a random graph model evolving in discrete time steps by duplicating and deleting the edges of randomly chosen vertices. We prove the existence of an a.s. asymptotic degree distribution, with streched exponential decay; more precisely, the proportion of vertices of degree d tends to some positive number c_d>0 almost surely as the number of steps goes to infinity, and c_d∼ (eπ)^1/2 d^1/4 e^{-2√ d} holds as d→∞.

Cited by

• Duplication-divergence growing graph models

Related

• Further properties of a random graph with duplications and deletions
• Randomised reproducing graphs
• On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
• Generalised De-Preferential Random Graphs
• The expected degree distribution in transient duplication divergence models