Geometric preferential attachment with choice-based edge step

Capa

Citar

Texto integral

Resumo

We study the asymptotic behavior of the maximum degree in the geometric graph model with a preferential attachment choice-based edge step. Geometric graphs are natural models that describe some nanoscale systems, while preferential attachment provides a good description of complex networks, particularly different neural networks. The model is a recursively built sequence of graphs. We start with the initial graph on a single vertex and we add a new vertex and draw a few edges on each step. Each vertex is assigned a parameter that represents its location. The recursion step consists of two parts. First, we introduce a new vertex and draw edges to close enough vertices. This step represents the geometric part of the model. Then, we draw edges between vertices by preferential attachment with the choice rule. We prove that dependent on model parameters, the maximum degree could exhibit sublinear (similar to the standard preferential attachment) and linear (representing concentration effect) behavior.

Sobre autores

Yury Malyshkin

Tver State University

Email: yury.malyshkin@mail.ru
Ph. D., Docent of Applied Mathematics and Cybernetics Department

Bibliografia

  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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

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

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») на элемент с текстом «Принять и продолжить».