×

zbMATH — the first resource for mathematics

A preferential attachment model with random initial degrees. (English) Zbl 1182.05107
Summary: In this paper, a random graph process \(\{G(t)\}_{t\geq 1}\) is studied and its degree sequence is analyzed. Let \(\{W_t\}_{t \geq 1}\) be an i.i.d. sequence. The graph process is defined so that, at each integer time \(t\), a new vertex with \(W_t\) edges attached to it, is added to the graph. The new edges added at time \(t\) are then preferentially connected to older vertices, i.e., conditionally on \(G(t-1)\), the probability that a given edge of vertex \(t\) is connected to vertex \(i\) is proportional to \(d_i(t-1)+\delta\), where \(d_i(t-1)\) is the degree of vertex \(i\) at time \(t-1\), independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent \(\tau = \min\{\tau_{W},\tau_{P}\}\), where \(\tau_{W}\) is the power-law exponent of the initial degrees \(\{W_t\}_{t\geq 1}\) and \(\tau_{P}\) the exponent predicted by pure preferential attachment. This result extends previous work by C. Cooper and A Frieze [“A general model of web graphs”, Random Struct. Algorithms 22, No. 3, 311–335 (2003; Zbl 1018.60007)].

MSC:
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aiello, W., Chung, F. and Lu, L., Random evolution in massive graphs, in Handbook of Massive Data Sets, Massive Comput. 4, pp. 97–122, Kluwer, Dordrecht, 2002. · Zbl 1024.68073
[2] Barabási, A. L. and Albert, R., Emergence of scaling in random networks, Science 286 (1999), 509–512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[3] Berestycki, N. and Durrett, R., A phase transition in the random transposition random walk, Probab. Theory Related Fields 136 (2006), 203–233. · Zbl 1102.60005 · doi:10.1007/s00440-005-0479-7
[4] Bianconi, G. and Barabási, A.-L., Bose–Einstein condensation in complex networks, Phys. Rev. Lett. 86:24 (2001), 5632–5635. · doi:10.1103/PhysRevLett.86.5632
[5] Bianconi, G. and Barabási, A.-L., Competition and multiscaling in evolving networks, Europhys. Lett. 54:4 (2001), 436–442. · doi:10.1209/epl/i2001-00260-6
[6] Bollobás, B., Borgs, C., Chayes, J. and Riordan, O., Directed scale-free graphs, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), pp. 132–139, ACM, New York, 2003. · Zbl 1094.68605
[7] Bollobás, B., Janson, S. and Riordan, O., The phase transition in inhomogeneous random graphs, Random Structures Algorithms 31 (2007), 3–122. · Zbl 1123.05083 · doi:10.1002/rsa.20168
[8] Bollobás, B. and Riordan, O., Mathematical results on scale-free random graphs, in Handbook of Graphs and Networks, pp. 1–34, Wiley, Weinheim, 2003. · Zbl 1062.05080
[9] Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G., The degree sequence of a scale-free random graph process, Random Structures Algorithms 18 (2001), 279–290. · Zbl 0985.05047 · doi:10.1002/rsa.1009
[10] Borgs, C., Chayes, J., Daskalakis, D. and Roch, C., First to market is not everything: an analysis of preferential attachment with fitness, in Proceedings of the 39th annual ACM symposium on the theory of computation, pp. 135–144, 2007. · Zbl 1232.68018
[11] Britton, T., Deijfen, M. and Martin-Löf, A., Generating simple random graphs with prescribed degree distribution, J. Stat. Phys. 124 (2006), 1377–1397. · Zbl 1106.05086 · doi:10.1007/s10955-006-9168-x
[12] Chung, F. and Lu, L., The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. USA 99:25 (2002), 15879–15882. · Zbl 1064.05137 · doi:10.1073/pnas.252631999
[13] Chung, F. and Lu, L., Connected components in random graphs with given expected degree sequences, Ann. Comb. 6 (2002), 125–145. · Zbl 1009.05124 · doi:10.1007/PL00012580
[14] Cooper, C. and Frieze, A., A general model of web graphs, Random Structures Algorithms 22 (2003), 311–335. · Zbl 1018.60007 · doi:10.1002/rsa.10084
[15] Ergün, G. and Rodgers, G. J., Growing random networks with fitness, Phys. A 303 (2002), 261–272. · Zbl 0978.90012 · doi:10.1016/S0378-4371(01)00408-3
[16] Faloutsos, C., Faloutsos, P. and Faloutsos, M., On power-law relationships of the internet topology, Computer Communications Reviews 29 (1999), 251–262. · Zbl 0889.68050 · doi:10.1145/316194.316229
[17] Feller, W., An Introduction to Probability Theory and its Applications. Vol. II, Wiley, New York, 1971. · Zbl 0219.60003
[18] Grimmett, G. R. and Stirzaker, D. R., Probability and Random Processes, Oxford University Press, New York, 2001. · Zbl 1015.60002
[19] Gut, A., Probability: A Graduate Course, Springer Texts in Statistics, Springer, New York, 2005. · Zbl 1076.60001
[20] Hagberg, O. and Wiuf, C., Convergence properties of the degree distribution of some growing network models, Bull. Math. Biol. 68:6 (2006), 1275–1291. · Zbl 1334.92158 · doi:10.1007/s11538-006-9085-9
[21] Hall, P., Order of magnitude of moments of sums of random variables, J. London Math. Soc. 24 (1981), 562–568. · Zbl 0472.60032 · doi:10.1112/jlms/s2-24.3.562
[22] van der Hofstad, R. and Hooghiemstra, G., Diameters in preferential attachment models, Preprint, 2007. · Zbl 1191.82020
[23] Jordan, J., The degree sequences and spectra of scale-free random graphs, Random Structures Algorithms 29 (2006), 226–242. · Zbl 1108.05083 · doi:10.1002/rsa.20101
[24] Katona, Z. and Móri, T. F., A new class of scale free random graphs, Statist. Probab. Lett. 76:15 (2006), 1587–1593. · Zbl 1100.05092 · doi:10.1016/j.spl.2006.04.017
[25] Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. and Upfal, E., Stochastic models for the web graph, in 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), pp. 57–65, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000.
[26] Kumar, R., Raghavan, P., Rajagopalan, S. and Tomkins, A., Trawling the web for emerging cyber communities, Computer Networks 31 (1999), 1481–1493. · doi:10.1016/S1389-1286(99)00040-7
[27] Newman, M. E. J., The structure and function of complex networks, SIAM Rev. 45 (2003), 167–256. · Zbl 1029.68010 · doi:10.1137/S003614450342480
[28] Pickands, III, J., Moment convergence of sample extremes, Ann. Math. Statist. 39 (1968), 881–889. · Zbl 0176.48804 · doi:10.1214/aoms/1177698320
[29] Söderberg, B., General formalism for inhomogeneous random graphs, Phys. Rev. E 66:6 (2002), 6 pp.
[30] Szymański, J., Concentration of vertex degrees in a scale-free random graph process, Random Structures Algorithms 26 (2005), 224–236. · Zbl 1060.05086 · doi:10.1002/rsa.20065
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.