Asymptotic Properties of a Random Graph with Duplications

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 almost surely asymptotic degree distribution, with stretched 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) similar to (e pi)(1/2)d(1/4)e(-2)root d holds as d -> infinity.

• Publication year

  2013

• Venue

  Journal of Applied Probability

• Publication date

  2013-08-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0021900200012523arXiv 1308.1506
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Random Graphs and Complex Networks

  2016cited by this paper
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph

  2014cited by this paper
• Tracking the Empirical Distribution of a Markov-modulated Duplication-Deletion Random Graph

  2013cited by this paper
• A random model of publication activity

  2011cited by this paper
• Randomised reproducing graphs

  2011influential reference
• Statistical behavior of embeddedness and communities of overlapping cliques in online social networks

  2010cited by this paper
• Preferential duplication graphs

  2010cited by this paper
• Mathematics and the Internet:

  2009cited by this paper
• Erdos-Renyi random graphs + forest fires = self-organized criticality

  2008cited by this paper
• Random Graph Dynamics: References

  2006cited by this paper
• The degree distribution of the generalized duplication model

  2006cited by this paper
• Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees

  2005influential reference
• A general model of web graphs

  2003influential reference
• Evolving protein interaction networks through gene duplication.

  2003cited by this paper
• Duplication Models for Biological Networks

  2002influential reference
• Infinite-order percolation and giant fluctuations in a protein interaction network.

  2002cited by this paper
• The degree sequence of a scale‐free random graph process

  2001cited by this paper
• On power-law relationships of the Internet topology

  1999cited by this paper
• Emergence of Scaling in Random Networks

  1999influential reference
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• On a Nonuniform Random Recursive Tree

  1987cited by this paper
• A general theory of bibliometric and other cumulative advantage processes

  1976cited by this paper
• Discrete Parameter Martingales

  1975cited by this paper
• ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS

  1955cited by this paper
• A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S.

  1925cited by this paper
• Emergence of Scaling in Random Networks

  year unknowninfluential reference

• Duplication-divergence growing graph models

  2025influential citation
• Random graphs with multiple type edges: asymptotic properties and epidemic spread

  2022cites this paper
• Limit shapes of large skew Young tableaux and a modification of the TASEP process

  2020cites this paper
• Diameter of P.A. random graphs with edge‐step functions

  2019cites this paper
• Topological properties of P.A. random graphs with edge-step functions

  2019cites this paper
• The connected component of the partial duplication graph

  2017influential citation
• The dominating colour of an infinite P\'olya urn model

  2015influential citation
• The dominating colour of an infinite Pólya urn model

  2015cites this paper
• Almost sure convergence of vertex degree densities in the vertex splitting model

  2015cites this paper
• Asymptotic degree distribution of a duplication-deletion random graph model

  2014influential citation
• Asymptotic Degree Distribution of a Duplication–Deletion Random Graph Model

  2014influential citation
• Large-scale behavior of the partial duplication random graph

  2014cites this paper
• Further properties of a random graph with duplications and deletions

  2014cites this paper