Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-08T21:37:52.743Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Networks with Preferential Growth and Vertex Death

Part of: Graph theory Operations research and management science Markov processes

Published online by Cambridge University Press:  14 July 2016

Maria Deijfen
Maria Deijfen*
Affiliation:
Stockholm University
*
∗Postal address: Department of Mathematics, Stockholm University, Stockholm, SE-10691, Sweden. Email address: [email protected]
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.

A dynamic model for a random network evolving in continuous time is defined, where new vertices are born and existing vertices may die. The fitness of a vertex is defined as the accumulated in-degree of the vertex and a new vertex is connected to an existing vertex with probability proportional to a function b of the fitness of the existing vertex. Furthermore, a vertex dies at a rate given by a function d of its fitness. Using results from the theory of general branching processes, an expression for the asymptotic empirical fitness distribution {pk} is derived and analyzed for a number of specific choices of b and d. When b(i) = i + α and d(i) = β, that is, linear preferential attachment for the newborn and random deaths, then pk ∼ k-(2+α). When b(i) = i + 1 and d(i) = β(i + 1), with β < 1, then pk ∼ (1 + β)−k, that is, if the death rate is also proportional to the fitness, then the power-law distribution is lost. Furthermore, when b(i) = i + 1 and d(i) = β(i + 1)γ, with β, γ < 1, then logpk ∼ -kγ, a stretched exponential distribution. The momentaneous in-degrees are also studied and simulations suggest that their behaviour is qualitatively similar to that of the fitnesses.

Keywords

Branching processrandom networkpreferential attachmentpower-law distributiondegree distribution

MSC classification

Secondary: 60J85: Applications of branching processes 90B15: Network models, stochastic 05C80: Random graphs
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 4 , December 2010 , pp. 1150 - 1163
Copyright
Copyright © Applied Probability Trust 2010 

References

[1] Abramowitz, M. and Stegun, I. A. (eds) (1972). Handbook of Mathematical Functions. Dover, New York.Google Scholar
[2] Athreya, K. B., Ghosh, A. P. and Sethuraman, S. (2008). Growth of preferential attachment random graphs via continuous-time branching processes. Proc. Indian Acad. Sci. 118, 473–494.Google Scholar
[3] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.Google Scholar
[4] Britton, T. and Lindholm, M. (2010). Dynamic random networks in dynamic populations. J. Statist. Phys. 139, 518–535.Google Scholar
[5] Bollobás, B., Janson, S. and Riordan, O. (2006). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.Google Scholar
[6] Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.Google Scholar
[7] Chung, F. and Lu, L. (2004). Coupling online and offline analyses for random power law graphs. Internet Math. 1, 409–461.Google Scholar
[8] Cooper, C., Frieze, A. and Vera, J. (2004). Random deletion in a scale-free random graph process. Internet Math. 1, 463–483.Google Scholar
[9] Deo, N. and Cami, A. (2007). Preferential deletion in dynamic models of web-like networks. Inf. Process. Lett. 102, 156–162.Google Scholar
[10] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Prob. 14, 1222–1267.CrossRefGoogle Scholar
[11] Haccou, P., Jagers, P. and Vatutin, V. A. (2005). Branching Processes: Variation Growth and Extinction of Populations. Cambridge University Press.CrossRefGoogle Scholar
[12] Jagers, P. (1975). Branching Processes and Biological Applications. John Wiley, London.Google Scholar
[13] Jagers, P. and Nerman, O. (1996). The asymptotic composition of supercritical multi-type branching populations. In Séminaire de Probabilités XXX (Lecture Notes Math. 1626), Springer, Berlin, pp. 40–54.Google Scholar
[14] Krapivsky, P. L. and Redner, S. (2001). Organization of growing random networks. Phys. Rev. E 63, 066123, 14 pp.CrossRefGoogle ScholarPubMed
[15] Moore, C., Ghoshal, G. and Newman, M. E. J. (2006). Exact solutions for models of evolving networks with addition and deletion of nodes. Phys. Rev. E 74, 036121, 8 pp.Google Scholar
[16] Móri, T. F. (2005). The maximal degree of the Barabási–Albert random tree. Combinatorics Prob. Comput. 14, 339–348.Google Scholar
[17] Nerman, O. (1981). On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrscheinlichkeitsth. 57, 365–395.Google Scholar
[18] Oliveira, R. and Spencer, J. (2005). Connectivity transitions in networks with super-linear preferential attachment. Internet Math. 2, 121–163.Google Scholar
[19] Rudas, A., Toth, B. and Valko, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31, 186–202.Google Scholar
[20] Van der Hofstad, R., Hooghiemstra, G. and van Mieghem, P. (2000). On the covariance of the level sizes in random recursive trees. Random Structures Algorithms 20, 519–539.Google Scholar