×

Random networks with sublinear preferential attachment: the giant component. (English) Zbl 1260.05143

Summary: We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every existing vertex independently with a probability proportional to a concave function \(f\) of its current degree. We give a criterion for the existence of a giant component, which is both necessary and sufficient, and which becomes explicit when \(f\) is linear. Otherwise it allows the derivation of explicit necessary and sufficient conditions, which are often fairly close.
We give an explicit criterion to decide whether the giant component is robust under random removal of edges. We also determine asymptotically the size of the giant component and the empirical distribution of component sizes in terms of the survival probability and size distribution of a multitype branching random walk associated with \(f\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60C05 Combinatorial probability
90B15 Stochastic network models in operations research

References:

[1] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[2] Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 13 pp. (electronic). · Zbl 1010.82021 · doi:10.1214/EJP.v6-96
[3] Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2009). A weak local limit for preferential attachment graphs.
[4] Bollobás, B., Janson, S. and Riordan, O. (2005). The phase transition in the uniformly grown random graph has infinite order. Random Structures Algorithms 26 1-36. · Zbl 1063.05121 · doi:10.1002/rsa.20041
[5] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3-122. · Zbl 1123.05083 · doi:10.1002/rsa.20168
[6] Bollobás, B. and Riordan, O. (2003). Robustness and vulnerability of scale-free random graphs. Internet Math. 1 1-35. · Zbl 1062.05080 · doi:10.1080/15427951.2004.10129080
[7] 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. · Zbl 0985.05047 · doi:10.1002/rsa.1009
[8] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222-1267. · Zbl 1185.05127 · doi:10.1214/EJP.v14-647
[9] Dommers, S., van der Hofstad, R. and Hooghiemstra, G. (2010). Diameters in preferential attachment models. J. Stat. Phys. 139 72-107. · Zbl 1191.82020 · doi:10.1007/s10955-010-9921-z
[10] Hardy, R. and Harris, S. C. (2009). A spine approach to branching diffusions with applications to \({L}^{p}\)-convergence of martingales. In Séminaire de Probabilités XLII. Lecture Notes in Math. 1979 281-330. Springer, Berlin. · Zbl 1193.60100 · doi:10.1007/978-3-642-01763-6_11
[11] Kato, T. (1976). Perturbation Theory for Linear Operators , 2nd ed. Grundlehren der Mathematischen Wissenschaften 132 . Springer, Berlin. · Zbl 0342.47009
[12] Kato, T. (1982). Superconvexity of the spectral radius, and convexity of the spectral bound and the type. Math. Z. 180 265-273. · Zbl 0471.46012 · doi:10.1007/BF01318910
[13] Krapivsky, P. L. and Redner, S. (2001). Organization of growing random networks. Phys. Rev. E 63 , paper 066123. · Zbl 1109.92301
[14] Kyprianou, A. E. and Rahimzadeh Sani, A. (2001). Martingale convergence and the functional equation in the multi-type branching random walk. Bernoulli 7 593-604. · Zbl 1017.60090 · doi:10.2307/3318727
[15] Pinsky, R. G. (1995). Positive Harmonic Functions and Diffusion. Cambridge Studies in Advanced Mathematics 45 . Cambridge Univ. Press, Cambridge. · Zbl 0858.31001
[16] Ramm, A. G. (1983). Variational principles for eigenvalues of compact nonselfadjoint operators. II. J. Math. Anal. Appl. 91 30-38. · Zbl 0505.49021 · doi:10.1016/0022-247X(83)90089-6
[17] Shepp, L. A. (1989). Connectedness of certain random graphs. Israel J. Math. 67 23-33. · Zbl 0733.05058 · doi:10.1007/BF02764896
[18] van der Hofstad, R. (2011). Random graphs and complex networks. Lecture notes. Available at . · Zbl 1229.60108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.