Геометрическое предпочтительное присоединение с добавлением ребер, основанном на выборе вершины
- Авторы: Малышкин Ю.А.1
-
Учреждения:
- Тверской государственный университет
- Выпуск: № 16 (2024)
- Страницы: 381-386
- Раздел: Теория наносистем
- URL: https://ogarev-online.ru/2226-4442/article/view/319443
- DOI: https://doi.org/10.26456/pcascnn/2024.16.381
- EDN: https://elibrary.ru/ILIYMV
- ID: 319443
Цитировать
Полный текст
Аннотация
Мы изучаем асимптотическое поведение максимальной степени вершины в геометрической модели графа с шагом добавления ребра на основе выбора вершины. Геометрические графы являются естественными моделями, которые описывают наномасштабные системы, в то время как предпочтительное присоединение обеспечивает хорошее описание сложных сетей, в частности, различных нейронных сетей. Модель представляет собой рекурсивно построенную последовательность графов. Мы начинаем с исходного графа на одной вершине и на каждом шаге добавляем новую вершину и проводим несколько ребер. Каждой вершине соответствует параметр, характеризующий ее местоположение. Шаг рекурсии состоит из двух частей. Сначала мы вводим новую вершину и проводим ребра от нее до достаточно близких вершин. Затем мы проводим ребро между вершинами с помощью предпочтительного присоединения с выбором. В работе доказывается, что в зависимости от параметров модели максимальная степень может демонстрировать сублинейное (аналогично стандартному предпочтительному присоединению) и линейное (что представляет эффект концентрации) поведение.
Ключевые слова
Об авторах
Юрий Андреевич Малышкин
Тверской государственный университет
Email: yury.malyshkin@mail.ru
к.ф.-м.н.., доцент кафедры информационных технологий
Список литературы
- Živkovic J., Tadic B. Nanonetworks: The graph theory framework for modeling nanoscale systems. Nanoscale Systems: Mathematical Modeling, Theory and Applications, 2013, vol. 2, pp. 30-48. doi: 10.2478/nsmmt-2013-0003.
- Vecchio D.A., Mahler S.H., Hammig M.D., Kotov N.A. Structural analysis of nanoscale network materials using graph theory. ACS Nano, 2021, vol. 15, issue 8, pp. 12847-12859. doi: 10.1021/acsnano.1c04711.
- Rana M.M., Nguyen D.D. Geometric graph learning to predict changes in binding free energy and protein thermodynamic stability upon mutation, The Journal of Physical Chemistry Letters, 2023, vol. 14, issue 49, pp. 10870-10879. doi: 10.1021/acs.jpclett.3c02679.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Malyshkin Y., Paquette E. The power of choice combined with preferential attachment, Electronic Communications in Probability, 2014, vol. 19, issue 44, pp. 1-13. doi: 10.1214/ECP.v19-3461.
- Haslegrave J., Jordan J., Yarrow M. Condensation in preferential attachment models with location-based choicem Random Structures and Algorithms, 2020, vol. 56, issue 3, pp. 775-795. doi: 10.1002/rsa.20889.
- Malyshkin Y. Sublinear preferential attachment combined with a growing number of choices, Electronic Communications in Probability, 2020, vol. 25, issue 87, pp. 1-12. doi: 10.1214/20-ECP368.
- Malyshkin Y., Paquette E. The power of choice over preferential attachment, Latin American Journal of Probability and Mathematical Statistics, 2015, vol. 12, issue 2, pp. 903-915.
- Alves C., Ribeiro R., Sanchis R. Preferential attachment random graphs with edge-step functions, Journal of Theoretical Probability, 2021, vol. 34, issue 1, pp. 438-476. doi: 10.1007/s10959-019-00959-0.
- Chen H.F. Stochastic approximation and its applications, Nonconvex Optimization and Its Applications. New York, Springer, 2002, vol. 64, XV, 360 p. doi: 10.1007/b101987.
- Malyshkin Y. Preferential attachment with choice-based edge step. Available at: https://arxiv.org/abs/2309.16591 (accessed 01.08.2024). doi: 10.48550/arXiv.2309.16591.
Дополнительные файлы
