Случайные графы предпочтительного связывания с добавлением полных подграфов
Аннотация
Предлагается расширение модели случайных графов с нелинейным правилом предпочтительного связывания путем учета возможностей добавления в сеть целых сообществ. Эти сообщества моделируются полными графами. Такое расширение модели естественным образом обосновывается известными процессами в социальных сетях. В работе выводятся математические соотношения, которые позволяют рассчитать распределение степени связности вершин {Qk} сгенерированного графа. Также выводятся уравнения, позволяющие при заданном распределении степени связности узлов реальной сети подобрать параметры генерации, учитывающих процесс добавления сообществ. Полученные результаты проверяются путем генерации больших графов.
Список литературы
1. Barabási A. L., Albert R. Emergence of scaling in random networks // Science. 1999. Vol. 286. P. 509–512.
2. Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Generic scale of the “scale-free” growing networks // Phys. Rev. Vol. 63. 2001.
3. Klemm K., Eguíluz V. Highly clustered scale-free networks // Phys. Rev. Vol. 65. 2002.
4. 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.
5. 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.
6. 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.
7. Palla G., Barabási A.-L., Vicsek T. Quantifying social group evolution // Nature. 2007. № 446. P. 664–667.
8. Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2011. № 6. С. 2–11.
9. Zuev K., Boguñá M., Bianconi G., Krioukov D. Emergence of Soft Communities from Geometric Preferential Attachment // Scientific Reports. 2015. № 9421. doi:10.1038/srep09421.
10. 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.
11. Klemm K., Eguiluz V. M. Growing scale-free network with small world behavior // Phys Rev E Stat Nonlin Soft Matter Phys. 2002. № 65.
12. 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.
13. Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах// Омский научный вестник. 2016. № 4 (148). С. 161–165.
14. 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.
15. 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.
Рецензия
При поддержке: Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований в рамках научного проекта № 16-31-60023 мол_а_дк.
Для цитирования:
Юдин Е.Б. Случайные графы предпочтительного связывания с добавлением полных подграфов. Вестник кибернетики. 2018;(1 (29)):50-59.
For citation:
Yudin E.B. Preferential attachment random graphs with complete subgraphs increment. Proceedings in Cybernetics. 2018;(1 (29)):50-59. (In Russ.)
Просмотров: 95
Послать статью по эл. почте 