Existence of a persistent hub in the convex preferential attachment model

• Autorzy: Galashin P.
• Języki publikacji: EN

Abstrakty

EN

A vertex of a randomly growing graph is called a persistent hub if at all but finitely many moments of time it has the maximal degree in the graph. We establish the existence of a persistent hub in the Barabási-Albert random graph model with probability one. We also extend this result to the class of convex preferential attachment graphs, where a vertex of degree k gets a new edge with probability proportional to some convex function of k.

Słowa kluczowe

EN

preferential attachment; persistent hub; Barabási-Albert model

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2016
• Tom: Vol. 36, Fasc. 1
• Strony: 59--74
• Opis fizyczny: Bibliogr. 16 poz., wykr.

Twórcy

autor

Galashin P.

• Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139-4307

Bibliografia

• [1] W. Aiello, F. Chung, and L. Lu, Random evolution in massive graphs, in: Handbook of Massive Data Sets, Massive Comput., Vol. 4, Kluwer Acad. Publ., Dordrecht 2002, pp. 97-122.
• [2] Á. Backhausz, Limit distribution of degrees in random family trees, Electron. Comm. Probab. 16 (2011), pp. 29-37.
• [3] A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286 (1999), pp. 509-512.
• [4] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády, The degree sequence of a scale-free random graph process, Random Structures Algorithms 18 (3) (2001), pp. 279-290.
• [5] S. Dereich and P. Mörters, Random networks with sublinear preferential attachment: degree evolutions, Electron. J. Probab. 14 (43) (2009), pp. 1222-1267.
• [6] S. Dereich and P. Mörters, Random networks with concave preferential attachment rule, Jahresber. Deutsch. Math.-Verein. 113 (1) (2011), pp. 21-40.
• [7] C. Godrèche, H. Grandclaude, and J. M. Luck, Statistics of leaders and lead changes in growing networks, J. Stat. Mech. Theory Exp. (2) (2010), P02001.
• [8] N. L. Johnson and S. Kotz, Urn models and their application, in: An Approach to Modern Discrete Probability Theory, Wiley Ser. Probab. Math. Stat., Wiley, New York 1977.
• [9] P. L. Krapivsky and S. Redner, Organization of growing random networks, Phys. Rev. E 63 (6) (2001), 066123.
• [10] H. M. Mahmoud, Pólya urn models, Texts Statist. Sci. Ser., CRC Press, Boca Raton, FL, 2009.
• [11] T. F. Móri, On random trees, Studia Sci. Math. Hungar. 39 (1-2) (2002), pp. 143-155.
• [12] T. F. Móri, The maximum degree of the Barabási-Albert random tree, Combin. Probab. Comput. 14 (3) (2005), pp. 339-348.
• [13] M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2) (2003), pp. 167-256 (electronic).
• [14] R. Oliveira and J. Spencer, Connectivity transitions in networks with super-linear preferential attachment, Internet Math. 2 (2) (2005), pp. 121-163.
• [15] A. Rudas and I. P. Tóth, Entropy and Hausdorff dimension in random growing trees, Stoch. Dyn. 13 (1) (2013), 1250010.
• [16] A. Rudas, B. Tóth, and B. Valkó, Random trees and general branching processes, Random Structures Algorithms 31 (2) (2007), pp. 186-202.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).