Исследование зависимостей и распределений в случайных сетях для смешанных моделей эволюции и при удалении узлов

Обложка

Цитировать

Полный текст

Аннотация

Изучается эволюция случайной сети моделями предпочтительного (preferential attachment), кластерного (clustering attachment) и смешанного присоединений для формирования связей вновь присоединенных узлов с существующими узлами. Рассматриваются стратегии удаления узла на каждом шаге эволюции сети: 1) без удаления узлов и связей; 2) удаление наименее влиятельного узла среди наиболее "старых", где в качестве меры влиятельности узла используется его пейджранг; 3) удаление узла с вероятностью, обратно пропорциональной числу его связей. Для этих стратегий удаления моделированием сравниваются зависимости двух характеристик случайных сетей: числа связей узлов и числа их треугольников (т.е. троек связанных узлов, в которые узел вовлечен) и поведение кластерных коэффициентов узлов. Оценивается тяжесть хвоста распределения для числа связей и треугольников. Смешанное кластерно-предпочтительное присоединение предлагается впервые.

Об авторах

Наталья Михайловна Маркович

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: nat.markovich@gmail.com
Москва

Максим Сергеевич Рыжов

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: maksim.ryzhov@frtk.ru
Москва

Михаил Ростиславович Кулик

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: mishakulik2002@yandex.ru
Москва

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

  1. AIELLO W., BONATO A., COOPER C., JANSSEN J.,PRA LAT P. A spatial web graph model with local influenceregions // Internet Mathematics. – 2009. – No. 5. – P. 175–196.
  2. ALBERT R., BARAB ´ ASI A.-L. Statistical mechanics ofcomplex networks // Rev. Mod. Phys.. – 2002. – Vol. 74. –P. 47–97.
  3. ALBERT R., BARAB ´ ASI A.-L. Emergence of scaling inrandom networks // Science. – 2002. – No. 286. – P. 509–512.
  4. ARNOLD N.A., MONDRAGON R.J., CLEGG R.G.Likelihood-based approach to discriminate mixtures of networkmodels that vary in time // Sci. Rep. – 2021. – No. 11. –P. 5205.
  5. AVRACHENKOV K., LEBEDEV D. PageRank of scale-freegrowing networks // Internet Mathematics. – 2006. – Vol. 3,No. 2. – P. 207–231.
  6. BARAB ´ ASI A.-L., ALBERT R. Statistical mechanics ofcomplex networks // Rev. Modern Phys. – 1999. – No. 74. –P. 47–97.
  7. BAGROW J., BROCKMANN D. Natural Emergence ofClusters and Bursts in Network Evolution // Physical ReviewX. – 2012. – Vol. 3., No. 2. – P. 021016.
  8. BEIRLANT J., GOEGEBEUR Y., TEUGELS J., SEGERS J.Statistics of Extremes: Theory and Applications. – Chichester,West Sussex: Wiley, 2004. –504 p.
  9. BRIN S., PAGE L. The anatomy of a large-scale hypertextualWeb search engine // Computer Networks and ISDN Systems. –1998. – Vol. 30, No. 1–7. – P. 107–117.
  10. BRINGMANN K., KEUSCH R., LENGLER J. Geometricinhomogeneous random graphs // Theoretical ComputerScience. – 2019. – No. 760. – P. 35–54.
  11. BOLLOB ´ AS B., RIORDAN O.M. Mathematical Results onScale-Free Random Graphs. – Weinheim: Wiley-WCH, 2002.
  12. CIRKOVIC D., TIANDONG WANG, RESNICK S.I.Preferential attachment with reciprocity: properties andestimation // Journal of Complex Networks. – 2023. – No. 11, –Issue. 5. – P. cnad031.
  13. CHEN N., LITVAK N., OLVERA-CRAVIOTO M. PageRankin Scale-Free Random Graphs // WAW 2014, LNCS 8882, ed.A. Bonato et al. Switzerland: Springer. – 2014. – P. 120–131.
  14. COHEN W.W. // http://www.cs.cmu.edu/˜ enron/ (дата обраще-ния: 17.04.2024).
  15. DE HAAN L., FERREIRA A. Extreme Value Theory: AnIntroduction. – Springer Science and Business Media, 2006. –417 p.
  16. DEKKERS A.L.M., EINMAHL J.H.J., DE HAAN L. AMoment Estimator for the Index of an Extreme-ValueDistribution // Ann. Statist. – 1989. – No. 17. – P. 1833–1855.
  17. ESTRADA E. The Structure of Complex Networks: Theory andApplications. – Oxford, 2011; online edn, Oxford Academic,2013.
  18. FRAGA ALVES M.I., GOMES M.I., DE HAAN L. Mixedmoment estimator and location invariant alternatives //Extremes. – 2009. – No. 12. – P. 149–185.
  19. GHOSHAL G., CHI L., BARABASI A.L. Uncovering the roleof elementary processes in network evolution // Sci. Rep. –2013. – No. 3. – P. 2920.
  20. ISKHAKOV L., KAMINSKI B., MIRONOV M. et al.Clustering Properties of Spatial Preferential Attachment Model// In: Bonato, A., Pralat, P., Raigorodskii, A. (eds.) Algorithmsand Models for the Web Graph. WAW 2018. Lecture Notes inComputer Science. – 2018. – Vol. 10836. – P. 30–43.
  21. JACOB E., MORTERS P. A Spatial Preferential AttachmentModel with Local Clustering // In: Bonato, A., Mitzenmacher,M., Pra lat, P. (eds) Algorithms and Models for the Web Graph.WAW 2013. Lecture Notes in Computer Science. – 2013. –Vol. 8305. – P. 14–25.
  22. LAI Z., XIAO W., LI M., ZHANG Z. An ExponentialDistribution Complex Network Model Constructed by DegreeSequence Length Iteration // IEEE Int. Conf. on ComputationalScience and Engineering (CSE) and IEEE Int. Conf. onEmbedded and Ubiquitous Computing (EUC) – 2017. –P. 267–271.
  23. MARKOVICH N.M. Nonparametric Analysis of UnivariateHeavy–Tailed Data: Research and Practice. – Chichester, WestSussex: Wiley, 2007. –343 p.
  24. MARKOVICH N.M., VAI ˇ CIULIS M. Extreme Value Statisticsfor Evolving Random Networks // Mathematics. – 2023. –Vol. 11, No. 9. – P. 2171.
  25. MARKOVICH N.M., VAI ˇ CIULIS M. Investigation of trianglecounts in graphs evolved by uniform clustering attachment //arXiv: 2401.11548v1. – 2024. – P. 1–16.
  26. MARKOVICH N.M., RYZHOV M.S., VAI ˇ CIULIS M.Inferences for Random Graphs Evolved by ClusteringAttachment // arXiv: 2403.00551v1. – 2024. – P. 1–25.
  27. MICHIELAN R., LITVAK N., STEGEHUIS C. Detectinghyperbolic geometry in networks: why triangles are notenough // Phys. Rev. E. – 2022. – Vol. 106, No. 5. – P. 054303.
  28. NORROS I., REITTU H. On a conditionally poissonian graphprocess // Advances in Applied Probability. – 2006. – No. 38. –P. 59–75.
  29. PENROSE M. Random Geometric Graphs. – Oxford Studies inProbability: Oxford Academic, 2003.
  30. POURSAFAEI F., HUANG S., PELRINE K. et al. Towardsbetter evaluation for dynamic link prediction // Advances inNeural Information Processing Systems. – 2022. – Vol. 35. –P. 32928–32941.
  31. RAMOS-CARRENO C., TORRECILLA J.L. dcor: Distancecorrelation and energy statistics in Python // SoftwareX. –2023. – Vol. 22. – P. 101326.
  32. ROSSI R.A., AHMED N.K. The Network Data Repository withInteractive Graph Analytics and Visualization // Proc. of theAAAI Conf. on Artificial Intelligence. –2015. – Vol. 29, No. 1. –P. 4292–4293.
  33. STROHMEIER M., OLIVE X., LUBBE J. et al. Crowdsourcedair traffic data from the OpenSky network 2019–20 // EarthSystem Science Data Discussions. – 2020. – No. 2020. –P. 1–15.
  34. WAN P., WANG T., DAVIS R. A., RESNICK S.I. Areextreme value estimation methods useful for network data? //Extremes. – 2020. – No. 23. – P. 171–195.
  35. WANG T., RESNICK S.I. Consistency of Hill estimators ina linear preferential attachment model // Extremes. – 2019. –No. 22. – P. 1—28.
  36. WANG T., RESNICK S.I. 2RV+HRV and Testing for Strong VSFull Dependence // arXiv:2312.16332v1 [math.ST]. – 2023. –P. 1—46.
  37. WEI-BING D., GUO L., LI W. et al. Worldwide Marine Transportation Network: Efficiency and ContainerThroughput // Chinese Physics Letters. – 2009. – No. 26. –P. 118901.

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

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


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

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