 |
|
|
| | | | | |
|
|
|
|
|
Random networks with sublinear preferential attachment: Degree evolutions
|
Steffen Dereich, Technische Universität Berlin
Peter Mörters, University of Bath
|
Abstract
We define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the empirical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which we describe in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of strong preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of weak preference, the vertex of maximal degree is changing infinitely often. Loosely speaking, the transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.
|
Full text: PDF
Pages: 122-1267
Published on: June 3, 2009
|
Bibliography
- Barabási, Albert-László; Albert, Réka. Emergence of scaling in random networks. Science 286 (1999), no. 5439, 509--512. MR2091634
- Bingham, N. H.; Goldie, C. M.; Teugels, J. L. Regular variation.Encyclopedia of Mathematics and its Applications, 27. Cambridge University Press, Cambridge, 1987. xx+491 pp. ISBN: 0-521-30787-2 MR0898871 (88i:26004)
- Bollobás, Béla; Riordan, Oliver; Spencer, Joel; Tusnády, Gábor. The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 (2001), no. 3, 279--290. MR1824277 (2002b:05121)
- Chernoff, Herman. A note on an inequality involving the normal distribution. Ann. Probab. 9 (1981), no. 3, 533--535. MR0614640 (82f:60050)
- Chung, Fan; Lu, Linyuan. Complex graphs and networks.CBMS Regional Conference Series in Mathematics, 107. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006. viii+264 pp. ISBN: 978-0-8218-3657-6; 0-8218-3657-9 MR2248695 (2007i:05169)
- Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications.Second edition.Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036 (99d:60030)
- Hofstad, R. v. d. (2009). Random graphs and complex networks. Eindhoven. Lecture Notes.
- Jacod, Jean; Shiryaev, Albert N. Limit theorems for stochastic processes.Second edition.Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 288. Springer-Verlag, Berlin, 2003. xx+661 pp. ISBN: 3-540-43932-3 MR1943877 (2003j:60001)
- Krapivsky, P. and S. Redner (2001). Organization of growing random networks. Phys. Rev. E 63, Paper 066123.
- Móri, T. F. On random trees. Studia Sci. Math. Hungar. 39 (2002), no. 1-2, 143--155. MR1909153 (2003f:05105)
- Móri, Tamás F. The maximum degree of the Barabási-Albert random tree. Combin. Probab. Comput. 14 (2005), no. 3, 339--348. MR2138118 (2006a:60014)
- Oliveira, Roberto; Spencer, Joel. Connectivity transitions in networks with super-linear preferential attachment. Internet Math. 2 (2005), no. 2, 121--163. MR2193157 (2006i:05148)
- Rudas, Anna; Tóth, Bálint; Valkó, Benedek. Random trees and general branching processes. Random Structures Algorithms 31 (2007), no. 2, 186--202. MR2343718 (2008e:05127)
- Williams, David. Probability with martingales.Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1991. xvi+251 pp. ISBN: 0-521-40455-X; 0-521-40605-6 MR1155402 (93d:60002)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context