Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T19:06:11.669Z Has data issue: false hasContentIssue false
  • English
  • Français

Preferential duplication graphs

Part of: Stochastic processes Graph theory Special processes

Published online by Cambridge University Press:  14 July 2016

Netta Cohen ,
Jonathan Jordan  and
Margaritis Voliotis
Netta Cohen*
Affiliation:
University of Leeds
Jonathan Jordan*
Affiliation:
University of Sheffield
Margaritis Voliotis*
Affiliation:
University of Leeds
*
∗ Postal address: School of Computing, University of Leeds, Leeds, LS2 9JT, UK.
∗∗ Postal address: Department of Probability and Statistics, University of Sheffield, Hicks Building, Sheffield, S3 7RH, UK. Email address: jonathan.jordan@shef.ac.uk
∗ Postal address: School of Computing, University of Leeds, Leeds, LS2 9JT, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider a preferential duplication model for growing random graphs, extending previous models of duplication graphs by selecting the vertex to be duplicated with probability proportional to its degree. We show that a special case of this model can be analysed using the same stochastic approximation as for vertex-reinforced random walks, and show that ‘trapping’ behaviour can occur, such that the descendants of a particular group of initial vertices come to dominate the graph.

Keywords

Preferential duplication graphsstochastic approximationvertex-reinforced random walk

MSC classification

Secondary: 05C80: Random graphs 60G99: None of the above, but in this section 60K35: Interacting random processes; statistical mechanics type models; percolation theory

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 2 , June 2010 , pp. 572 - 585
Copyright
Copyright © Applied Probability Trust 2010 

References

[1] Bebek, G. et al. (2006). The degree distribution of the generalized duplication model. Theoret. Comput. Sci. 369, 239–249.Google Scholar
[2] Benaïm, M.} (1997). Dynamics of stochastic approximation algorithms. In Séminaires de Probabilités XXXIII (Lecture Notes Math. 1709), Springer, Berlin, pp. 1–68.Google Scholar
[3] Benaïm, M. and Tarrès, P.} (2008). Dynamics of vertex-reinforced random walks. To appear in Ann. Prob. Google Scholar
[4] Bollobás, B. and Riordan, O. M. (2003). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks, eds Bornholdt, S. and Schuster, H. G., Wiley-VCH, Weinheim, pp. 1–34.Google Scholar
[5] Bonato, A. et al. (2010). Models of on-line social networks. To appear in Internet Math.Google Scholar
[6] Chung, F., Lu, L., Dewey, T. G. and Galas, D. J. (2003). Duplication models for biological networks. J. Comput. Biol. 10, 677–687.Google Scholar
[7] Kumar, R. {it et al.} (2000). Stochastic models for the web graph. In Proc. 41st Annual Symp. on Foundations of Comput. Sci. (Redondo Beach, CA, 2000), IEEE Computer Society Press, Los Alamitos, CA, pp. 57–65.Google Scholar
[8] Pemantle, R. (1988). {Random processes with reinforcement}. Doctoral Thesis, Department of Mathematics, Massachusetts Institute of Technology.Google Scholar
[9] Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1–79.Google Scholar
[10] Raval, A. (2003). Some asymptotic properties of duplication graphs. Phys. Rev. E 68, 066119, 10 pp.Google Scholar
[11] Volkov, S. (2001). Vertex-reinforced random walk on arbitrary graphs. Ann. Prob. 29, 66–91.Google Scholar