Preferential attachment random graphs with complete subgraphs increment
Abstract
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.
About the Author
E. B. Yudin
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
Russian Federation
Russian Federation
References
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.
Review
For citations:
Yudin E.B. Preferential attachment random graphs with complete subgraphs increment. Proceedings in Cybernetics. 2018;(1 (29)):50-59. (In Russ.)
Views:
185
Email this article 