On a preferential attachment and generalized Pólya’s urn model. (English) Zbl 1266.05150

Summary: We study a general preferential attachment and Pólya’s urn model. At each step a new vertex is introduced, which can be connected to at most one existing vertex. If it is disconnected, it becomes a pioneer vertex. Given that it is not disconnected, it joins an existing pioneer vertex with probability proportional to a function of the degree of that vertex. This function is allowed to be vertex-dependent, and is called the reinforcement function. We prove that there can be at most three phases in this model, depending on the behavior of the reinforcement function. Consider the set whose elements are the vertices with cardinality tending a.s. to infinity. We prove that this set either is empty, or it has exactly one element, or it contains all the pioneer vertices. Moreover, we describe the phase transition in the case where the reinforcement function is the same for all vertices. Our results are general, and in particular we are not assuming monotonicity of the reinforcement function. Finally, consider the regime where exactly one vertex has a degree diverging to infinity. We give a lower bound for the probability that a given vertex ends up being the leading one, that is, its degree diverges to infinity. Our proofs rely on a generalization of the Rubin construction given for edge-reinforced random walks, and on a Brownian motion embedding.


05C80 Random graphs (graph-theoretic aspects)
90B15 Stochastic network models in operations research
60C05 Combinatorial probability
Full Text: DOI arXiv Euclid


[1] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 47-97. · Zbl 1205.82086
[2] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[3] Bhamidi, S. (2012). Universal techniques to analyze preferential attachment tree and networks: Global and local analysis. Probab. Surv.
[4] 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
[5] Chung, F., Handjani, S. and Jungreis, D. (2003). Generalizations of Polya’s urn problem. Ann. Comb. 7 141-153. · Zbl 1022.60005
[6] Cotar, C. and Limic, V. (2009). Attraction time for strongly reinforced walks. Ann. Appl. Probab. 19 1972-2007. · Zbl 1213.60087
[7] Davis, B. (1990). Reinforced random walk. Probab. Theory Related Fields 84 203-229. · Zbl 0665.60077
[8] de Solla Price, D. (1976). A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science 27 292-306.
[9] 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
[10] Deneubourg, J. L., Aron, S., Goss, S. and Pasteels, J. M. (1990). The self-organising exploratory pattern of the argentine ant. Journal of Insect Behavior 3 159-168.
[11] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222-1267. · Zbl 1185.05127
[12] Dereich, S. and Mörters, P. (2011). Random networks with sublinear preferential attachment: The giant component. Unpublished manuscript. · Zbl 1260.05143
[13] Drinea, E., Enachescu, M. and Mitzenmacher, M. (2001). Variations on random graph models of the web. Technical Repor TR-06-01, Harvard Univ.
[14] Hansen, B. and Pitman, J. (2000). Prediction rules for exchangeable sequences related to species sampling. Statist. Probab. Lett. 46 251-256. · Zbl 0944.62109
[15] Hill, B. M., Lane, D. and Sudderth, W. (1987). Exchangeable urn processes. Ann. Probab. 15 1586-1592. · Zbl 0629.60044
[16] Ishwaran, H. and James, L. F. (2003). Generalized weighted Chinese restaurant processes for species sampling mixture models. Statist. Sinica 13 1211-1235. · Zbl 1086.62036
[17] Krapivsky, P. L. and Redner, S. L. (2001). Organization of growing random networks. Phys. Rev. E 63 066123. · Zbl 1109.92301
[18] Lee, J., Quintana, F. A., Müller, P. and Trippa, L. (2012). Defining predictive probability functions for species sampling models. Unpublished manuscript. · Zbl 1331.62152
[19] Móri, T. F. (2002). On random trees. Studia Sci. Math. Hungar. 39 143-155. · Zbl 1026.05095
[20] Oliveira, R. and Spencer, J. (2005). Connectivity transitions in networks with super-linear preferential attachment. Internet Math. 2 121-163. · Zbl 1097.68016
[21] Oliveira, R. I. (2009). The onset of dominance in balls-in-bins processes with feedback. Random Structures Algorithms 34 454-477. · Zbl 1203.60104
[22] Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79. · Zbl 1189.60138
[23] Pitman, J. (1995). Exchangeable and partially exchangeable random partitions. Probab. Theory Related Fields 102 145-158. · Zbl 0821.60047
[24] Pitman, J. (1996). Some developments of the Blackwell-MacQueen urn scheme. In Statistics , Probability and Game Theory (T. S. Ferguson, L. S. Shapley and J. B. MacQueen, eds.). Institute of Mathematical Statistics Lecture Notes-Monograph Series 30 245-267. IMS, Hayward, CA.
[25] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202. · Zbl 1144.60051
[26] Shah, S., Kothari, R., Jayadeva andChandra, S. (2010). Trail formation in ants. A generalized Polya urn process. Swarm Intelligence 4 145-171.
[27] Zhou, T. (2009). Nonlinear Pòlya urn models and self-organizing processes. Ph.D. thesis, Univ. Pennsylvania. Available at .
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.