procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»procyber-224Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPhysics and MathematicsСлучайные графы предпочтительного связывания с добавлением полных подграфовPreferential attachment random graphs with complete subgraphs incrementЮдинЕ. Б.YudinE. B.udinev@asoiu.comИнститут математики им. С. Л. Соболева СО РАНРоссияSobolev Institute of Mathematics, Siberian Branch, Russian Academy of SciencesRussian Federation20182603202001 (29)5059Copyright © Юдин Е.Б., 20202020Юдин Е.Б.Yudin E.B.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestcyber.ru/jour/article/view/224

Предлагается расширение модели случайных графов с нелинейным правилом предпочтительного связывания путем учета возможностей добавления в сеть целых сообществ. Эти сообщества моделируются полными графами. Такое расширение модели естественным образом обосновывается известными процессами в социальных сетях. В работе выводятся математические соотношения, которые позволяют рассчитать распределение степени связности вершин {Qk} сгенерированного графа. Также выводятся уравнения, позволяющие при заданном распределении степени связности узлов реальной сети подобрать параметры генерации, учитывающих процесс добавления сообществ. Полученные результаты проверяются путем генерации больших графов.

The model extension of nonlinear preferential attachment random graphs considering possibilities of adding entire communities in the network is proposed. The added communities are represented by entire graphs. Such an extension of model is naturally based on existing processes on social networks. Mathematical relations are derived. These relations allow calculating the degree distribution of vertices {Qk} of a generated graph. Equations are also derived which allow, for a given node degree distribution of real network getting generation properties considering the process of adding communities. The results obtained are verified by generating large graphs.

графы предпочтительного связываниясетевые сообществачисло кликpreferential attachment graphsonline communitiesnumber of clicksИсследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований в рамках научного проекта № 16-31-60023 мол_а_дк.ReferencesBarabási A. L., Albert R. Emergence of scaling in random networks // Science. 1999. Vol. 286. P. 509–512.Barabási A. L., Albert R. Emergence of scaling in random networks // Science. 1999. Vol. 286. P. 509–512.Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Generic scale of the “scale-free” growing networks // Phys. Rev. Vol. 63. 2001.Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Generic scale of the “scale-free” growing networks // Phys. Rev. Vol. 63. 2001.Klemm K., Eguíluz V. Highly clustered scale-free networks // Phys. Rev. Vol. 65. 2002.Klemm K., Eguíluz V. Highly clustered scale-free networks // Phys. Rev. Vol. 65. 2002.Jackson M. O., Rogers B. W. Meeting strangers and friends of friends: How random are social networks? // Am. Econ. Rev. 2007. № 97 (3). P. 890–915.Jackson M. O., Rogers B. W. Meeting strangers and friends of friends: How random are social networks? // Am. Econ. Rev. 2007. № 97 (3). P. 890–915.Zadorozhnyi V. N., Yudin E. B. Structural properties of the scale-free Barabasi – Albert graph // Automation and Remote Control. 2012. № 73 (4). P. 702–716. doi: 10.1134/S0005117912040091.Zadorozhnyi V. N., Yudin E. B. Structural properties of the scale-free Barabasi – Albert graph // Automation and Remote Control. 2012. № 73 (4). P. 702–716. doi: 10.1134/S0005117912040091.Zadorozhnyi V. N., Yudin E. B. Dynamic equations of node degrees in growing networks with connection losses // Dynamics of Systems, Mechanisms and Machines (Dynamics). 2016. art. no. 7819111. Р. 1–5. doi: 10.1109/Dynamics.2016.7819111.Zadorozhnyi V. N., Yudin E. B. Dynamic equations of node degrees in growing networks with connection losses // Dynamics of Systems, Mechanisms and Machines (Dynamics). 2016. art. no. 7819111. Р. 1–5. doi: 10.1109/Dynamics.2016.7819111.Palla G., Barabási A.-L., Vicsek T. Quantifying social group evolution // Nature. 2007. № 446. P. 664–667.Palla G., Barabási A.-L., Vicsek T. Quantifying social group evolution // Nature. 2007. № 446. P. 664–667.Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2011. № 6. С. 2–11.Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2011. № 6. С. 2–11.Zuev K., Boguñá M., Bianconi G., Krioukov D. Emergence of Soft Communities from Geometric Preferential Attachment // Scientific Reports. 2015. № 9421. doi:10.1038/srep09421.Zuev K., Boguñá M., Bianconi G., Krioukov D. Emergence of Soft Communities from Geometric Preferential Attachment // Scientific Reports. 2015. № 9421. doi:10.1038/srep09421.Dorodnykh А., Ostroumova Prokhorenkova L., Samosvat E. Pref erential placement for community structure formation // In International Workshop on Algorithms and Models for the Web-Graph. Springer, 2017. P. 75–89.Dorodnykh А., Ostroumova Prokhorenkova L., Samosvat E. Pref erential placement for community structure formation // In International Workshop on Algorithms and Models for the Web-Graph. Springer, 2017. P. 75–89.Klemm K., Eguiluz V. M. Growing scale-free network with small world behavior // Phys Rev E Stat Nonlin Soft Matter Phys. 2002. № 65.Klemm K., Eguiluz V. M. Growing scale-free network with small world behavior // Phys Rev E Stat Nonlin Soft Matter Phys. 2002. № 65.Zadorozhnyi V. N., Yudin E. B., Yudina M. N. Analytical and numerical methods of calibration for preferential attachment randon graphs // International Siberian Conference on Control and Communications, SIBCON ; S. Seifullin Kazakh Agrotechnical UniversityAstana; Kazakhstan; 29–30 June 2017. Astana, 2017. doi: 10.1109/SIBCON.2017.7998461.Zadorozhnyi V. N., Yudin E. B., Yudina M. N. Analytical and numerical methods of calibration for preferential attachment randon graphs // International Siberian Conference on Control and Communications, SIBCON ; S. Seifullin Kazakh Agrotechnical UniversityAstana; Kazakhstan; 29–30 June 2017. Astana, 2017. doi: 10.1109/SIBCON.2017.7998461.Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах// Омский научный вестник. 2016. № 4 (148). С. 161–165.Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах// Омский научный вестник. 2016. № 4 (148). С. 161–165.Chi Y., Song X., Zhou D., Hino K., and Tseng B. L. Evolutionary spectral clustering by incorporating temporal smoothness // KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM. N.Y., USA, 2007. P. 153–162.Chi Y., Song X., Zhou D., Hino K., and Tseng B. L. Evolutionary spectral clustering by incorporating temporal smoothness // KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM. N.Y., USA, 2007. P. 153–162.Lin Y.-R., Chi Y., Zhu S., Sundaram H., and Tseng B. L. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks // WWW ’08: Proceedings of the 17th International Conference on the World Wide Web, ACM. N.Y., USA, 2008. P. 685–694.Lin Y.-R., Chi Y., Zhu S., Sundaram H., and Tseng B. L. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks // WWW ’08: Proceedings of the 17th International Conference on the World Wide Web, ACM. N.Y., USA, 2008. P. 685–694.

The authors declare that there are no conflicts of interest present.