{
  "id": "1408.4268",
  "version": "v1",
  "published": "2014-08-19T09:47:48.000Z",
  "updated": "2014-08-19T09:47:48.000Z",
  "title": "Asymptotic degree distribution of a duplication-deletion random graph model",
  "authors": [
    "Erik Thörnblad"
  ],
  "comment": "1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-19T09:47:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "asymptotic degree distribution",
      "discrete-time duplication-deletion random graph model",
      "degree sequence lies",
      "degree sequence decays",
      "random graphs consists"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.4268T"
    }
  }
}