Геометрическое предпочтительное присоединение с добавлением ребер, основанном на выборе вершины

Обложка

Цитировать

Полный текст

Аннотация

Мы изучаем асимптотическое поведение максимальной степени вершины в геометрической модели графа с шагом добавления ребра на основе выбора вершины. Геометрические графы являются естественными моделями, которые описывают наномасштабные системы, в то время как предпочтительное присоединение обеспечивает хорошее описание сложных сетей, в частности, различных нейронных сетей. Модель представляет собой рекурсивно построенную последовательность графов. Мы начинаем с исходного графа на одной вершине и на каждом шаге добавляем новую вершину и проводим несколько ребер. Каждой вершине соответствует параметр, характеризующий ее местоположение. Шаг рекурсии состоит из двух частей. Сначала мы вводим новую вершину и проводим ребра от нее до достаточно близких вершин. Затем мы проводим ребро между вершинами с помощью предпочтительного присоединения с выбором. В работе доказывается, что в зависимости от параметров модели максимальная степень может демонстрировать сублинейное (аналогично стандартному предпочтительному присоединению) и линейное (что представляет эффект концентрации) поведение.

Об авторах

Юрий Андреевич Малышкин

Тверской государственный университет

Email: yury.malyshkin@mail.ru
к.ф.-м.н.., доцент кафедры информационных технологий

Список литературы

  1. Ž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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».