Предпочтительное присоединение с выбором, зависящим от пригодности
Ю.А. Малышкин
ФГБОУ ВО «Тверской государственный университет»
DOI: 10.26456/pcascnn/2021.13.483
Оригинальная статья
Аннотация: Исследуется асимптотическое поведение максимальной степени вершины в графе предпочтительного присоединения с выбором вершины, основанном как на ее степени, так и на дополнительном параметре (пригодности). Модели предпочтительного присоединения широко используются для моделирования сложных сетей (таких как нейронные сети и т.д.). Они строятся следующим образом. Мы начинаем с двух вершин и ребра между ними. Затем на каждом шаге мы рассматриваем выборку из уже существующих вершин, выбранных с вероятностями, пропорциональными их степеням плюс некоторый параметр β>-1. Затем мы добавляем новую вершину и соединяем ее ребром с вершиной из выборки, на которой достигается максимум произведения ее степени на ее пригодность. Мы доказали, что в зависимости от параметров модели возможны три типа поведения максимальной степени вершины – сублинейное, линейное и порядка n/ lnn, где n – число вершин в графе.
Ключевые слова: сложные сети, случайные графы, предпочтительное присоединение, случайный выбор, пригодность
- Малышкин Юрий Андреевич – к.ф.-м.н., доцент кафедры информационных технологий, ФГБОУ ВО «Тверской государственный университет»
Ссылка на статью:
Малышкин, Ю.А. Предпочтительное присоединение с выбором, зависящим от пригодности / Ю.А. Малышкин // Физико-химические аспекты изучения кластеров, наноструктур и наноматериалов. — 2021. — Вып. 13. — С. 483-494. DOI: 10.26456/pcascnn/2021.13.483.
Полный текст: загрузить PDF файл
Библиографический список:
1. Latora, V. Complex networks: principles, methods and applications / V. Latora, G. Russo, V. Nicosia. –Cambridge: Cambridge University Press, 2017. – 585 p. DOI: 10.1017/9781316216002.
2. Erciyes, K. Complex networks: an algorithmic perspective / K. Erciyes. – 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 / E. Estrada. – Oxford: Oxford University Press, 2012. – XII, 465 p. DOI: 10.1093/acprof:oso/9780199591756.001.0001.
4. Fon, W. Complex dynamical networks constructed with fully controllable nonlinear nanomechanical oscillators / W. Fon, M.H. Matheny, J. Li et al. // Nano Letters. – 2017. – V. 17. – I. 10. – P. 5977-5983. DOI: 10.1021/acs.nanolett.7b02026.
5. Yao, H. Modelling electrical conduction in nanostructure assemblies through complex networks / H. Yao, Y.-P. Hsieh, J. Kong, M. Hofmann // Nature Materials. – 2020. – V. 19. – I. 7. – P. 745-751. DOI: 10.1038/s41563-020-0664-1.
6. Barabási, A. Emergence of scaling in random networks / A. Barabási, R. Albert // Science. – 1999. – V. 286. – I. 5439. – P. 509-512. DOI: 10.1126/science.286.5439.509.
7. Móri, T.F. On random trees / T.F. Móri // Studia Scientiarum Mathematicarum Hungarica. – 2002. – V. 39. – I. 1-2. – P. 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 / T.F. Móri // Combinatorics, Probability and Computing. – 2005. – V. 14. – I. 3. – P. 339-348. DOI: 10.1017/S0963548304006133.
9. Hofstag, R. Random graphs and complex networks / R. van der Hofstag. – Cambridge: Cambridge University Press, 2016. V. 1: Cambridge Series in Statistical and Probabilistic Mathematics, Series Number 43. – XVIII, 321 p. DOI: 10.1017/9781316779422.
10. Borgs, C. First to market is not everything: an analysis of preferential attachment with fitness / C. Borgs, J. Chayes, C. Daskalakis, S. Roch // STOC '07: Thirty-ninth annual ACM symposium on theory of computing, June 11-13, San Diego, California, USA: proceedings. – New York: Association for Computing Machinery, 2007. – P. 135-144. DOI: 10.1145/1250790.1250812.
11. Krapivsky, P.L. Choice-driven phase transition in complex networks / P.L. Krapivsky, S. Redner // Journal of Statistical Mechanics: Theory and Experiment. – 2014. – V. 2014. – Art. № P04021. – 14 p. DOI: 10.1088/1742-5468/2014/04/P04021.
12. Malyshkin, Y. The power of choice combined with preferential attachment / Y. Malyshkin, E. Paquette // Electronic Communications in Probability. – 2014. – V. 19. – P. 1-13. DOI: 10.1214/ECP.v19-3461.
13. Malyshkin, Y. The power of choice over preferential attachment / Y. Malyshkin, E. Paquette // Latin American Journal of Probability and Mathematical Statistics. – 2015. – V. 12. – № 2. – P. 903-915.
14. Haslegrave, J. Preferential attachment with choice. / J. Haslegrave, J. Jordan // Random Structures and Algorithms. – 2016. – V. 48. – I. 4. – P. 751-766. DOI: 10.1002/rsa.20616.
15. Malyshkin, Y. Preferential attachment combined with the random number of choices / Y. Malyshkin // Internet Mathematics. – 2018. – V. 1. – I. 1. – P. 1-25. DOI: 10.24166/im.01.2018.
16. Grauer, A. Preferential attachment with location-based choice: Degree distribution in the noncondensation phase / A. Grauer, L. Lüchtrath, M. Yarrow. – Access mode www.url: https://arxiv.org/pdf/1905.08481v3.pdf. – 28.03.2021.
17. Haslegrave, J. Condensation in preferential attachment models with location-based choice / J. Haslegrave, J. Jordan, M. Yarrow // Random Structures and Algorithms. – 2020. – V. 56. – I. 3. – P. 775-795. DOI: 10.1002/rsa.20889.
18. Chen, H.F. Stochastic approximation and its applications / H.F. Chen. In: Nonconvex Optimization and its Applications. – New York, Boston, Dordrecht, London, Moscow: Kluwer Academic Publishers. – 2002. – V. 64. – XV, 360 p. DOI: 10.1007/b101987.
19. Pemantle, R. A survey of random processes with reinforcement / R. Pemantle // Probability Surveys. – 2007. – V. 4. – P. 1-79. DOI: 10.1214/07-PS094.
20. Galashin, P.A. Existence of a persistent hub in the convex preferential attachment model / P.A. Galashin // Probability and Mathematical Statistics. – 2016. – V. 36. Fasc. 1. – P. 59-74.
21. Mahmoud, H.M. Polya urn models / H.M. Mahmoud. – New York: Chapman and Hall/CRC, 2008. – 312 p. DOI: 10.1201/9781420059847.
22. Johnson, N.L. Urn models and their application: an approach to modern discrete probability theory / N.L. Johnson, S. Kotz. 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 / Y. Malyshkin // Electronic Communications in Probability. – 2020. – V. 25. – P. 1-12. DOI: 10.1214/20- ECP368.