Asymptotic degree distribution of a duplication-deletion random graph model

Abstract

We study a discrete-time duplication-deletion random graph model and analyse its asymptotic degree distribution. The random graphs consists of disjoint cliques. In each time step either a new vertex is brought in with probability $0<p<1$ and attached to an existing clique, chosen with probability proportional to the clique size, or all the edges of a random vertex are deleted with probability $1-p$. We prove almost sure convergence of the asymptotic degree distribution and find its exact values in terms of a hypergeometric integral, expressed in terms of the parameter $p$. In the regime $0<p<\frac{1}{2}$ we show that the degree sequence decays exponentially at rate $\frac{p}{1-p}$, whereas it satisfies a power-law with exponent $\frac{p}{2p-1}$ if $\frac{1}{2}<p<1$. At the threshold $p=\frac{1}{2}$ the degree sequence lies between a power-law and exponential decay.

1 figure

References in corpus (1)

• Growing networks with preferential addition and deletion of edges

Cited by in corpus (6)

• Large-scale behavior of the partial duplication random graph
• Diameter of P.A. random graphs with edge-step functions
• The dominating colour of an infinite Pólya urn model
• Further properties of a random graph with duplications and deletions
• A time-invariant random graph with splitting events
• Almost sure convergence of vertex degree densities in the vertex-splitting model