Геометрическое предпочтительное присоединение с добавлением ребер, основанном на выборе вершины
Ю.А. Малышкин
ФГБОУ ВО «Тверской государственный университет»
DOI: 10.26456/pcascnn/2024.16.381
Краткое сообщение
Аннотация: Мы изучаем асимптотическое поведение максимальной степени вершины в геометрической модели графа с шагом добавления ребра на основе выбора вершины. Геометрические графы являются естественными моделями, которые описывают наномасштабные системы, в то время как предпочтительное присоединение обеспечивает хорошее описание сложных сетей, в частности, различных нейронных сетей. Модель представляет собой рекурсивно построенную последовательность графов. Мы начинаем с исходного графа на одной вершине и на каждом шаге добавляем новую вершину и проводим несколько ребер. Каждой вершине соответствует параметр, характеризующий ее местоположение. Шаг рекурсии состоит из двух частей. Сначала мы вводим новую вершину и проводим ребра от нее до достаточно близких вершин. Затем мы проводим ребро между вершинами с помощью предпочтительного присоединения с выбором. В работе доказывается, что в зависимости от параметров модели максимальная степень может демонстрировать сублинейное (аналогично стандартному предпочтительному присоединению) и линейное (что представляет эффект концентрации) поведение.
Ключевые слова: геометрические графы, сложные сети, случайные графы, предпочтительное присоединение, выбор вершины
- Малышкин Юрий Андреевич – к.ф.-м.н.., доцент кафедры информационных технологий, ФГБОУ ВО «Тверской государственный университет»
Ссылка на статью:
Малышкин, Ю.А. Геометрическое предпочтительное присоединение с добавлением ребер, основанном на выборе вершины / Ю.А. Малышкин // Физико-химические аспекты изучения кластеров, наноструктур и наноматериалов. — 2024. — Вып. 16. — С. 381-386. DOI: 10.26456/pcascnn/2024.16.381.
Полный текст: загрузить PDF файл
Библиографический список:
1. Živkovic, J. Nanonetworks: The graph theory framework for modeling nanoscale systems / J. Zivkovic, B. Tadic // Nanoscale Systems: Mathematical Modeling, Theory and Applications. – 2013. – V. 2. – P. 30-48. DOI: 10.2478/nsmmt-2013-0003.
2. Vecchio, D.A. Structural analysis of nanoscale network materials using graph theory / D.A. Vecchio, S.H. Mahler, M.D. Hammig, N.A. Kotov // ACS Nano. – 2021. – V. 15 – I. 8. – P. 12847-12859. DOI: 10.1021/acsnano.1c04711.
3. Rana, M.M. Geometric graph learning to predict changes in binding free energy and protein thermodynamic stability upon mutation / M.M. Rana, D.D. Nguyen // The Journal of Physical Chemistry Letters. – 2023. – V. 14 – I. 49. – P. 10870-10879. DOI: 10.1021/acs.jpclett.3c02679.
4. 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.
5. 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
6. 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.
7. 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.
8. 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.
9. 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.
10. Malyshkin, Y. The power of choice combined with preferential attachment / Y. Malyshkin, E. Paquette // Electronic Communications in Probability. – 2014. – V. 19. – I. 44. – P. 1-13. DOI: 10.1214/ECP.v19-3461.
11. 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.
12. Malyshkin, Y. Sublinear preferential attachment combined with a growing number of choices / Y. Malyshkin // Electronic Communications in Probability. – 2020. – V. 25. – I. 87. – P. 1-12. DOI: 10.1214/20-ECP368.
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. – I. 2. – P. 903-915.
14. Alves, C. Preferential Attachment Random Graphs with Edge-Step Functions / C. Alves, R. Ribeiro, R. Sanchis // Journal of Theoretical Probability. – 2021. – V. 34. – I. 1. – P. 438-476. DOI: 10.1007/s10959-019-00959-0.
15. Chen, H.F. Stochastic approximation and its applications / H.F. Chen // In book series: Nonconvex Optimization and Its Applications. – New York: Springer, 2002. – V. 64. – XV, 360 p. DOI: 10.1007/b101987.
16. Malyshkin, Y. Preferential attachment with choice-based edge step / Y. Malyshkin. – Режим доступа: https://arxiv.org/abs/2309.16591. – 01.08.2024. DOI: 10.48550/arXiv.2309.16591.