# 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)
##### Keywords:
random graph process; degree sequence
Full Text:
##### References:
  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  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  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  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  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  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  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  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  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  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  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  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  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  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  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  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  Feller, W., An Introduction to Probability Theory and its Applications. Vol. II, Wiley, New York, 1971. · Zbl 0219.60003  Grimmett, G. R. and Stirzaker, D. R., Probability and Random Processes, Oxford University Press, New York, 2001. · Zbl 1015.60002  Gut, A., Probability: A Graduate Course, Springer Texts in Statistics, Springer, New York, 2005. · Zbl 1076.60001  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  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  van der Hofstad, R. and Hooghiemstra, G., Diameters in preferential attachment models, Preprint, 2007. · Zbl 1191.82020  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  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  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.  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  Newman, M. E. J., The structure and function of complex networks, SIAM Rev. 45 (2003), 167–256. · Zbl 1029.68010 · doi:10.1137/S003614450342480  Pickands, III, J., Moment convergence of sample extremes, Ann. Math. Statist. 39 (1968), 881–889. · Zbl 0176.48804 · doi:10.1214/aoms/1177698320  Söderberg, B., General formalism for inhomogeneous random graphs, Phys. Rev. E 66:6 (2002), 6 pp.  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.