Further properties of a random graph with duplications and deletions

2014/09/18 by Backhausz, Ágnes, Móri, Tamás F. · 1 citation
#05C80 #60F15 #68Q87 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1409.5279

Abstract

We deal with a random graph model where at each step, a vertex is chosen uniformly at random, and it is either duplicated or its edges are deleted. Duplication has a given probability. We analyse the limit distribution of the degree of a fixed vertex, and derive a.s. asymptotic bounds for the maximal degree. The model shows a phase transition phenomenon with respect to the probabilities of duplication and deletion.

Cited by

• Duplication-divergence growing graph models

Related

• Asymptotic properties of a random graph with duplications
• Randomised reproducing graphs
• The expected degree distribution in transient duplication divergence models
• On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
• On the concentration of the maximum degree in the duplication-divergence models