Geodesic
High degree vertices in the power of choice model combined with preferential attachment
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2017), pp. 31-43 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We find assimpotics for the first $k$ highest degrees of the degree distribution in an evolving tree model combining the local choice and the preferential attachment. In the considered model, the random graph is constructed in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of $d$ ($d>2$) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees. It is known that the maximum of the degree distribution in this model has linear behavior. We prove that $k$-th highest dergee has a sublinear behavior with a power depends on $d$. This contrasts sharply with what is seen in the preferential attachment model without choice, where all highest degrees in the degree distribution has the same sublinear order. The proof is based on showing that the considered tree has a persistent hub by comparison with the standard preferential attachment model, along with martingale arguments.
Keywords: random graphs, preferential attachment, choice. 
@article{VTPMK_2017_1_a2,
     author = {Yu. Malyshkin},
     title = {High degree vertices in the power of choice model combined with preferential attachment},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {31--43},
     year = {2017},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2017_1_a2/}
}
TY  - JOUR
AU  - Yu. Malyshkin
TI  - High degree vertices in the power of choice model combined with preferential attachment
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2017
SP  - 31
EP  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2017_1_a2/
LA  - en
ID  - VTPMK_2017_1_a2
ER  - 
%0 Journal Article
%A Yu. Malyshkin
%T High degree vertices in the power of choice model combined with preferential attachment
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2017
%P 31-43
%N 1
%U http://geodesic.mathdoc.fr/item/VTPMK_2017_1_a2/
%G en
%F VTPMK_2017_1_a2
Yu. Malyshkin. High degree vertices in the power of choice model combined with preferential attachment. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2017), pp. 31-43. http://geodesic.mathdoc.fr/item/VTPMK_2017_1_a2/

[1] Barabási A., Albert R., “Emergence of scaling in random networks”, Science, 286:5439 (1999), 509-512 | DOI | MR | Zbl

[2] D'Souza R. M., Krapivsky P. L., Moor C., “The power of choice in growing trees”, The European Physical Journal B, 59:4 (2007), 535-543 | DOI | MR | Zbl

[3] Dommers S., Hofstad R., Hooghiemstra G., “Diameters in preferential attachment models”, Journal of Statistical Physics, 139:1 (2010), 72-107 | DOI | MR | Zbl

[4] Fenner T., Flaxman A., Frieze A., “High degree vertices and eigenvalues in the preferential attachment graph”, Internet Mathematics, 2:1 (2005), 1-19 | DOI | MR | Zbl

[5] Galashin P. A., Existence of a persistent hub in the convex preferential attachment model, October 2013, arXiv: 1310.7513 | MR

[6] Johnson N. L., Kotz S., Urn models and their application, John Wiley and Sons, New York, 1977 | MR | Zbl

[7] Krapivsky P. L., Redner S., “Choice-driven phase transition in complex networks”, Journal of Statistical Mechanics: Theory and Experiment, 2014 | MR

[8] Leyvraz F., Krapivsky P. L., Redner S., “Connectivity of growing random networks”, Physical Review Letters, 85 (2000), 4629-4632 | DOI

[9] Kuba M., Mahmoud H., Panholzer A., “Analysis of a generalized friedman's urn with multiple drawings”, Discrete Applied Mathematics, 161:18 (2013), 2968-2984 | DOI | MR | Zbl

[10] Mahmoud H., Polya urn models, Chapman and Hall/CRC, 2009 | MR

[11] Malyshkin Y., Paquette E., “The power of choice combine with preferential attachment”, Electronic Communication in Probability, 19:44 (2014), 1-13 | MR

[12] Malyshkin Y., Paquette E., “The power of choice over preferential attachment”, Latin American Journal of Probability and Mathematical Statistics, 12:2 (2015), 903-915 | MR | Zbl

[13] Tamás F. Móri, “The maximum degree of the Barabási-Albert random tree”, Combinatorics, Probability and Computing, 14:3 (2005), 339-348 | DOI | MR | Zbl

[14] Shiryaev A. N., Probability, Second edition, Springer, 1996, 621 pp. | MR