Preferential attachment with fitness dependent choice
Tver State University
Abstract: We study the asymptotic behavior of the maximum degree in the preferential attachment tree model with a choice based on both the degree and fitness of a vertex. The preferential attachment models are natural models for complex networks (like neural networks, etc.) and constructed in the following recursive way. To each vertex is assigned a parameter that is called a fitness of a vertex. We start from two vertices and an edge between them. On each step, we consider a sample with repetition of d vertices, chosen with probabilities proportional to their degrees plus some parameter β>-1. Then we add a new vertex and draw an edge from it to the vertex from the sample with the highest product of fitness and degree. We prove that the maximum degree, dependent on parameters of the model, could exhibit three types of asymptotic behavior: sublinear, linear, and of n / lnn order, where n is the number of edges in the graph.
Keywords: complex networks, random graphs, preferential attachment, power of choice, fitness
- Yury A. Malyshkin – Ph. D., Docent, Applied Mathematics and Cybernetics Department, Tver State University
Malyshkin, Yu.A. Preferential attachment with fitness dependent choice / Yu.A. Malyshkin // Physical and chemical aspects of the study of clusters, nanostructures and nanomaterials. – Tver: TSU, 2021. — I. 13. — P. 483-494. DOI: 10.26456/pcascnn/2021.13.483. (In Russian).
Full article (in Russian): download PDF file
1. Latora V., Russo G., Nicosia V. Complex networks: principles, methods and applications. Cambridge, Cambridge University Press, 2017, 585 p. DOI: 10.1017/9781316216002.
2. Erciyes K. Complex networks: an algorithmic perspective. Boca Raton, CRC Press, 2014, 318 p. DOI: 10.13140/2.1.1608.1281.
3. Estrada E. The structure of complex networks: theory and applications. Oxford, Oxford University Press, 2012, XII, 465 p. DOI: 10.1093/acprof:oso/9780199591756.001.0001.
4. Fon W., Matheny M.H., Li J. et al. Complex dynamical networks constructed with fully controllable nonlinear nanomechanical oscillators, Nano Letters, 2017, vol. 17, issue 10, pp. 5977-5983. DOI: 10.1021/acs.nanolett.7b02026.
5. Yao H., Hsieh Y.-P., Kong J., Hofmann M. Modelling electrical conduction in nanostructure assemblies through complex networks, Nature Materials, 2020, vol. 19, issue 7, pp. 745-751. DOI: 10.1038/s41563-020-0664-1.
6. Barabási A., Albert R. Emergence of scaling in random networks, Science, 1999, vol. 286, issue 5439, pp. 509-512. DOI: 10.1126/science.286.5439.509.
7. Móri T.F. On random trees, Studia Scientiarum Mathematicarum Hungarica, 2002, vol. 39, issue 1-2, pp. 143-155. DOI: 10.1556/SScMath.39.2002.1-2.9.
8. Móri T.F. The maximum degree of the Barabási-Albert random tree, Combinatorics, Probability and Computing, 2005, vol. 14, issue 3, pp. 339-348. DOI: 10.1017/S0963548304006133.
9. Hofstag R. Random graphs and complex networks. Cambridge, Cambridge University Press, 2016, vol. 1: Cambridge Series in Statistical and Probabilistic Mathematics, Series Number 43, XVIII, 321 p. DOI: 10.1017/9781316779422.
10. Borgs C., Chayes J., Daskalakis C., Roch S. First to market is not everything: an analysis of preferential attachment with fitness, STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (San Diego, California, USA, June 11-13). New York: Association for Computing Machinery, 2007, pp. 135-144. DOI: 10.1145/1250790.1250812.
11. Krapivsky P.L., Redner S. Choice-driven phase transition in complex networks, Journal of Statistical Mechanics: Theory and Experiment, 2014, vol. 2014, art. no. P04021, 14 p. DOI: 10.1088/1742- 5468/2014/04/P04021.
12. Malyshkin Y., Paquette E. The power of choice combined with preferential attachment, Electronic Communications in Probability, 2014, vol. 19, pp. 1-13. DOI: 10.1214/ECP.v19-3461.
13. Malyshkin Y., Paquette E. The power of choice over preferential attachment, Latin American Journal of Probability and Mathematical Statistics, 2015, vol. 12, no. 2, pp. 903-915.
14. Haslegrave J., Jordan J. Preferential attachment with choice, Random Structures and Algorithms, 2016, vol. 48, issue 4, pp. 751-766. DOI: 10.1002/rsa.20616.
15. Malyshkin Y. Preferential attachment combined with the random number of choices, Internet Mathematics, 2018, vol. 1, issue 1, pp. 1-25. DOI: 10.24166/im.01.2018.
16. Grauer A., Lüchtrath L., Yarrow M. Preferential attachment with location-based choice: Degree distribution in the noncondensation phase. Available at: https://arxiv.org/pdf/1905.08481v3.pdf (accessed 28.03.2021).
17. Haslegrave J., Jordan J., Yarrow M. Condensation in preferential attachment models with location-based choice, Random Structures and Algorithms, 2020, vol. 56, issue 3, pp. 775-795. DOI: 10.1002/rsa.20889.
18. Chen H.F. Stochastic approximation and its applications. In: Nonconvex Optimization and its Applications. New York, Boston, Dordrecht, London, Moscow, Kluwer Academic Publishers, 2002, vol. 64, XV, 360 p. DOI: 10.1007/b101987.
19. Pemantle R. A survey of random processes with reinforcement, Probability Surveys, 2007, vol. 4, pp. 1-79. DOI: 10.1214/07-PS094.
20. Galashin P.A. Existence of a persistent hub in the convex preferential attachment model, Probability and Mathematical Statistics, 2016, vol. 36, fasc. 1, pp. 59-74.
21. Mahmoud H.M. Polya urn models. New York, Chapman and Hall/CRC, 2008, 312 p. DOI: 10.1201/9781420059847.
22. Johnson N.L., Kotz S. Urn models and their application: an approach to modern discrete probability theory. New York, London, Sydney, Toronto, John Wiley and Sons, 1977, xiii, 402 p.
23. Malyshkin Y. Sublinear preferential attachment combined with a growing number of choices, Electronic Communications in Probability, 2020, vol. 25, pp. 1-12. DOI: 10.1214/20-ECP368.