×

zbMATH — the first resource for mathematics

Preferential attachment with choice. (English) Zbl 1341.05230
Summary: We consider the degree distributions of preferential attachment random graph models with choice similar to those considered in recent work by Y. Malyshkin and E. Paquette [Electron. Commun. Probab. 19, Paper No. 44, 13 p. (2014; Zbl 1298.05287)] and P. L. Krapivsky and S. Redner [“Choise-driven phase transition in complex networks”, Preprint, arXiv:1312.7803]. In these models a new vertex chooses \(r\) vertices according to a preferential rule and connects to the vertex in the selection with the \(s\)th highest degree. For meek choice, where \(s>1\), we show that both double exponential decay of the degree distribution and condensation-like behaviour are possible, and provide a criterion to distinguish between them. For greedy choice, where \(s=1\), we confirm that the degree distribution asymptotically follows a power law with logarithmic correction when \(r=2\) and shows condensation-like behaviour when \(r>2\).

MSC:
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Barabási, Emergence of scaling in random networks, Science 286 pp 509– (1999) · Zbl 1226.05223
[2] Bollobás, The degree sequence of a scale-free random graph process, Random Struct Algorithms 18 pp 279– (2001) · Zbl 0985.05047
[3] C. Borgs J. Chayes C. Daskalakis S. Roch First to market is not everything: An analysis of preferential attachment with fitness STOC, ’07 135 144 · Zbl 1232.68018
[4] Cooper, A general model of web graphs, Random Struct Algorithms 22 pp 311– (2003) · Zbl 1018.60007
[5] D’Souza, The power of choice in growing trees, Eur Phys J B 59 pp 535– (2007) · Zbl 1189.05157
[6] Jordan, The degree sequences and spectra of scale-free random graphs, Random Struct Algorithms 29 pp 226– (2006) · Zbl 1108.05083
[7] Krapivsky, Choice-driven phase transition in complex networks, J Stat Mech Theory Exp pp 1– (2014)
[8] Y. Malyshkin E. Paquette The power of 2 choices over preferential attachment · Zbl 1329.05266
[9] Malyshkin, The power of choice combined with preferential attachment, Electron Commun Probab 19 pp 1– (2014) · Zbl 1298.05287
[10] Móri, On random trees, Stud Sci Math Hungar 39 pp 143– (2002)
[11] Oliveira, Connectivity transitions in networks with super-linear preferential attachment, Internet Math 2 pp 121– (2005) · Zbl 1097.68016
[12] Riordan, Achlioptas process phase transitions are continuous, Ann Appl Probab 22 pp 1450– (2012) · Zbl 1255.05176
[13] Rudas, Random trees and general branching processes, Random Struct Algorithms 31 pp 186– (2007) · Zbl 1144.60051
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.