×
Choi, Jihyeok; Sethuraman, Sunder

Large deviations for the degree structure in preferential attachment schemes. (English) Zbl 1273.60031

Ann. Appl. Probab. 23, No. 2, 722-763 (2013).
A preferential attachment scheme is specified with two functions of time: a probability \(p(t)\) and a non-negative weight component \(b(t)\). At each time step \(t\) a new node is attached to the current graph. With probability \(p(t)\) it is attached as an isolated node, and with probability \(1-p(t)\) it is attached by an edge to a node in the current graph that is selected with probability proportional to a weight \(w(t,d)=d+b(t)\) of its degree \(d\) and time \(t\). Using this scheme the convergence to power law distributions and other laws are investigated for the empirical degree distribution.
Reviewer: Ove Frank (Stockholm)

Cited in 3 Documents

MSC:

60F10 Large deviations
05C80 Random graphs (graph-theoretic aspects)

Keywords:

Preferential attachment; random graphs; degree distribution; large deviations; time-dependent; law of large numbers; power law; condensation
PDF BibTeX XML Cite
\textit{J. Choi} and \textit{S. Sethuraman}, Ann. Appl. Probab. 23, No. 2, 722--763 (2013; Zbl 1273.60031)
Full Text: DOI arXiv Euclid

References:

[1] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 47-97. · Zbl 1205.82086
[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. Math. Sci. 118 473-494. · Zbl 1153.05020
[3] Barabási, A.-L. (2009). Scale-free networks: A decade and beyond. Science 325 412-413. · Zbl 1226.91052
[4] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[5] Barrat, A., Barthelemy, M., Pastor-Satorras, R. and Vespignani, A. (2004). The architecture of complex weighted networks. PNAS 101 3747-3752.
[6] Berger, N., Borgs, C., Chayes, J. and Saberi, A. (2009). A weak local limit for preferential attachment graphs.
[7] Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2005). On the spread of viruses on the internet. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms 301-310 (electronic). ACM, New York. · Zbl 1297.68029
[8] Bhamidi, S. (2007). Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint. Available at .
[9] Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 24 5-34. · Zbl 1047.05038
[10] 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
[11] Borgs, C., Chayes, J., Lovász, L., Sós, V. and Vesztergombi, K. (2011). Limits of randomly grown graph sequences. European J. Combin. 32 985-999. · Zbl 1229.05247
[12] Bornholdt, S. and Schuster, H. G., eds. (2003). Handbook of Graphs and Networks : From the Genome to the Internet . Wiley-VCH, Weinheim. · Zbl 1044.90002
[13] Bryc, W., Minda, D. and Sethuraman, S. (2009). Large deviations for the leaves in some random trees. Adv. in Appl. Probab. 41 845-873. · Zbl 1181.60036
[14] Caldarelli, G. (2007). Scale-Free Networks : Complex Webs in Nature and Technology . Oxford Univ. Press, Oxford. · Zbl 1119.94001
[15] Chung, F., Handjani, S. and Jungreis, D. (2003). Generalizations of Polya’s urn problem. Ann. Comb. 7 141-153. · Zbl 1022.60005
[16] Chung, F. and Lu, L. (2006). Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics 107 . Amer. Math. Soc., Providence, RI. · Zbl 1114.90071
[17] Cohen, R. and Havlin, S. (2010). Complex Networks : Structure Robustness and Function . Cambridge Univ. Press, Cambridge. · Zbl 1196.05092
[18] Cooper, C. and Frieze, A. (2003). A general model of web graphs. Random Structures Algorithms 22 311-335. · Zbl 1018.60007
[19] Cooper, C. and Frieze, A. (2007). The cover time of the preferential attachment graph. J. Combin. Theory Ser. B 97 269-290. · Zbl 1114.05095
[20] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Applications of Mathematics ( New York ) 38 . Springer, New York. · Zbl 0896.60013
[21] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222-1267. · Zbl 1185.05127
[22] Dereich, S., Mönch, C. and Mörters, P. (2011). Typical distances in ultrasmall random networks. Available at . 1102.5680v1 · Zbl 1244.05199
[23] Dorogovtsev, S. N., Krapivsky, P. L. and Mendés, J. F. F. (2008). Transition from small to large world in growing networks. Europhys. Lett. EPL 81 Art. 30004, 5.
[24] Dorogovtsev, S. N. and Mendes, J. F. F. (2000). Evolution of networks with aging of sites. Phys. Rev. E 62 1842-1845.
[25] Dorogovtsev, S. N. and Mendes, J. F. F. (2001). Scaling properties of scale-free evolving networks: Continuous approach. Phys. Rev. E 63 056125 19 pp.
[26] Dorogovtsev, S. N. and Mendes, J. F. F. (2003). Evolution of Networks : From Biological Nets to the Internet and WWW . Oxford Univ. Press, Oxford. · Zbl 1109.68537
[27] Drinea, E., Enachescu, M. and Mitzenmacher, M. (2001). Variations on random graph models for the web. Harvard Technical Report TR-06-01.
[28] Drinea, E., Frieze, A. and Mitzenmacher, M. (2002). Balls and Bins models with feedback. In Proc. of the 11 th ACM-SIAM Symposium on Discrete Algorithms ( SODA ) 308-315. SIAM, Philadelphia, PA. · Zbl 1092.91537
[29] Dupuis, P. and Ellis, R. S. (1997). A Weak Convergence Approach to the Theory of Large Deviations . Wiley, New York. · Zbl 0904.60001
[30] Durrett, R. (2007). Random Graph Dynamics . Cambridge Univ. Press, Cambridge. · Zbl 1116.05001
[31] Fortunato, S., Flammini, A. and Menczer, F. (2006). Scale-free network growth by ranking. Phys. Rev. Lett. 96 218701-1-218701-4.
[32] Frieze, A., Vera, J. and Chakrabarti, S. (2006). The influence of search engines on preferential attachment. Internet Math. 3 361-381. · Zbl 1147.68346
[33] Gjoka, M., Kurant, M., Butts, C. T. and Markopoulou, A. (2011). Practical recommendations on crawling online social networks. IEEE Journal on Selected Areas in Communications 29 1872-1892.
[34] Janssen, J. and Prałat, P. (2010). Rank-based attachment leads to power law graphs. SIAM J. Discrete Math. 24 420-440. · Zbl 1213.05237
[35] Katona, Z. (2005). Width of a scale-free tree. J. Appl. Probab. 42 839-850. · Zbl 1079.05090
[36] Krapivsky, P. and Redner, S. (2001). Organization of growing random networks. Phys. Rev. E 63 066123-1-066123-14.
[37] Krapivsky, P. L. and Redner, S. (2002). Finiteness and fluctuations in growing networks. J. Phys. A 35 9517-9534. · Zbl 1038.82071
[38] Krapivsky, P. L., Rodgers, G. J. and Redner, S. (2001). Degree distributions of growing networks. Phys. Rev. Lett. 86 5401-5404.
[39] Mihail, M., Papadimitriou, C. and Saberi, A. (2006). On certain connectivity properties of the internet topology. J. Comput. System Sci. 72 239-251. · Zbl 1090.68002
[40] Mitzenmacher, M. (2004). A brief history of generative models for power law and lognormal distributions. Internet Math. 1 226-251. · Zbl 1063.68526
[41] Móri, T. F. (2002). On random trees. Studia Sci. Math. Hungar. 39 143-155. · Zbl 1026.05095
[42] Móri, T. F. (2005). The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput. 14 339-348. · Zbl 1078.05077
[43] Newman, M., Barabási, A.-L. and Watts, D. J., eds. (2006). The Structure and Dynamics of Networks . Princeton Univ. Press, Princeton, NJ. · Zbl 1362.00042
[44] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167-256 (electronic). · Zbl 1029.68010
[45] Newman, M. E. J. (2010). Networks : An Introduction . Oxford Univ. Press, Oxford. · Zbl 1195.94003
[46] Oliveira, R. and Spencer, J. (2005). Connectivity transitions in networks with super-linear preferential attachment. Internet Math. 2 121-163. · Zbl 1097.68016
[47] Ráth, B. and Szakács, L. (2011). Multigraph limit of the dense configuration model and the preferential attachment graph. Preprint. Available at . 1106.2058 · Zbl 1265.05560
[48] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202. · Zbl 1144.60051
[49] Simkin, M. V. and Roychowdhury, V. P. (2011). Re-inventing Willis. Phys. Rep. 502 1-35.
[50] Simon, H. A. (1955). On a class of skew distribution functions. Biometrika 42 425-440. · Zbl 0066.11201
[51] Yule, G. U. (1924). A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis. Philos. Trans. Roy. Soc. London Ser. B 213 21-87.
[52] Zhang, J. X. and Dupuis, P. (2008). Large-deviation approximations for general occupancy models. Combin. Probab. Comput. 17 437-470. · Zbl 1218.60023
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.