Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-13T06:47:29.450Z Has data issue: false hasContentIssue false

Preferential duplication graphs

Published online by Cambridge University Press:  14 July 2016

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: [email protected]
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.

Type
Research Article
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, 239249.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. 168.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. 134.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, 677687.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. 5765.Google Scholar
[8] Pemantle, R. (1988). {Random processes with reinforcement}. , Department of Mathematics, Massachusetts Institute of Technology.Google Scholar
[9] Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 179.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, 6691.Google Scholar