procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»procyber-151Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPhysics and MathematicsРаспределения степеней в графах с линейным правилом предпочтительного связывания и в графах Джексона – РоджерсаDegrees Distributions in Linear Preferential Attachment Graphs and Jackson – Rogers GraphsЗадорожныйВ. Н.ZadorozhnyiV. N.zwn2015@yandex.ruЮдинЕ. Б.YudinE. B.

г. Новосибирск

Novosibirsk

udinev@asoiu.comОмский государственный технический университетРоссияOmsk State Technical UniversityRussian FederationИнститут математики им. С. Л. Соболева, Сибирское отделение РАНРоссияSobolev Institute of Mathematics, Siberian Branch, Russian Academy of SciencesRussian Federation20182503202003 (31)6881Copyright © Задорожный В.Н., Юдин Е.Б., 20202020Задорожный В.Н., Юдин Е.Б.Zadorozhnyi V.N., 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/151

Рассматриваются два класса растущих случайных графов – графы предпочтительного связывания с линейной весовой функцией и гибридные графы Джексона – Роджерса. Выведены точные формулы финальных распределений степеней связности вершин и финальных двумерных распределений степеней связности дуг/ребер рассматриваемых графов. Доказано, что каждому гибридному графу соответствует определенный граф предпочтительного связывания с линейной весовой функцией, имеющий точно такие же, как у этого гибридного графа распределения степеней связности вершин и степеней связности дуг/ребер. Доказывается и более сильное утверждение, что всякий гибридный граф эквивалентен определенному графу с линейной весовой функцией. Выведена формула, позволяющая калибровать линейную весовую функцию для выращивания графов с требуемым асимптотически степенным распределением степеней вершин. Достоверность полученных результатов подтверждена численными проверками и имитационным моделированием. Практическая ценность результатов демонстрируется примером эффективной калибровки графа сети автономных систем Интернет.

The paper considers two classes of growing random graphs. The first class is the preferential attachment graphs with a linear weight function, and the second class is the hybrid Jackson – Rogers graphs. Exact formulas for the final vertex degree distributions and final edge/arc endpoints of two-dimensional distributions are derived. It is proved that each hybrid graph corresponds with the definite linear preferential attachment graph by vertex degree distribution and edge/arc endpoints distribution. A stronger assertion is also proved that every hybrid graph is equivalent to a definite graph with a linear weight function. A formula that allows the calibration of a linear function for growing graphs with the required asymptotic power-law vertex degree distribution is deduced. The reliability of the results is confirmed by numerical calculations and simulation modeling. The practical value of the results is demonstrated by successful graph calibration of the network model by autonomous Internet systems.

теория сетейрастущие сетиграфы предпочтительного связыванияграфы Джексона – Роджерсараспределения степеней связности вершин и дуг/реберnetwork theorygrowing networkspreferential attachment graphsJackson – Rogers graphsdegrees distribution of connectivity of vertices and arcs/edgesИсследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-31-60023 мол_а_дк.ReferencesBarabasi A. L., Albert R. Emergence of scaling in random networks // Science. 1999. V. 286. P. 509–512.Barabasi A. L., Albert R. Emergence of scaling in random networks // Science. 1999. V. 286. P. 509–512.Barabasi A. L. Scale-free networks: A decade and beyond // Science. 2009. V. 325. P. 412– 413.Barabasi A. L. Scale-free networks: A decade and beyond // Science. 2009. V. 325. P. 412– 413.Jackson M. O., Rogers B. W. Meeting Strangers and Friends of Friends: How Random are Social Networks? Forthcoming // American Economic Review, 2006.Jackson M. O., Rogers B. W. Meeting Strangers and Friends of Friends: How Random are Social Networks? Forthcoming // American Economic Review, 2006.Jackson M. O. Social and Economic Networks: Models and Analysis. Stanford University ; Santa Fe Institute: CIFAR, 2010.Jackson M. O. Social and Economic Networks: Models and Analysis. Stanford University ; Santa Fe Institute: CIFAR, 2010.Zadorozhnyi V. N., Yudin E. B. Growing network: models following nonlinear preferential attachment rule // Physica A: Statistical Mechanics and its Applications. 2015. V. 428. Р. 111–132.Zadorozhnyi V. N., Yudin E. B. Growing network: models following nonlinear preferential attachment rule // Physica A: Statistical Mechanics and its Applications. 2015. V. 428. Р. 111–132.Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2010. № 6. С. 2–11.Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2010. № 6. С. 2–11.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) 2017. Astana, Kazakhstan. 2017. Р. 1–6.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) 2017. Astana, Kazakhstan. 2017. Р. 1–6.Fortunato S., Bergstrom C. T., Börner K., Evans J. A., Helbing D., Milojević S, Petersen A. M., Radicchi F., Sinatra R., Uzzi B. , Vespignani A., Waltman L., Wang D. , Barabási A-L. Science of Science // Science. 2018. V. 359. P. 6379.Fortunato S., Bergstrom C. T., Börner K., Evans J. A., Helbing D., Milojević S, Petersen A. M., Radicchi F., Sinatra R., Uzzi B. , Vespignani A., Waltman L., Wang D. , Barabási A-L. Science of Science // Science. 2018. V. 359. P. 6379.Deville P., Song C., Eagle N., Blondel V. D., Barabasi A-L., Wang D. Scaling Identity Connects Human Mobility and Social Interactions // PNAS. 2016. V. 113. № 26. P. 7047–7052.Deville P., Song C., Eagle N., Blondel V. D., Barabasi A-L., Wang D. Scaling Identity Connects Human Mobility and Social Interactions // PNAS. 2016. V. 113. № 26. P. 7047–7052.Lo C., Cheng J., Leskovec J. Understanding Online Collection Growth Over Time: A Case Study of Pinterest // ACM International Conference on World Wide Web (WWW), 2017.Lo C., Cheng J., Leskovec J. Understanding Online Collection Growth Over Time: A Case Study of Pinterest // ACM International Conference on World Wide Web (WWW), 2017.Karrer B., Newman M. E. J. Competing epidemics on complex networks // Phys Rev. 2011. № 84.Karrer B., Newman M. E. J. Competing epidemics on complex networks // Phys Rev. 2011. № 84.Boccaletti S., Latora V., Moreno Y., Chavez M., Hwang D-U. Complex networks: Structure and dynamics // Physics Reports. 2006. № 424. Р. 175–308.Boccaletti S., Latora V., Moreno Y., Chavez M., Hwang D-U. Complex networks: Structure and dynamics // Physics Reports. 2006. № 424. Р. 175–308.Zan Y. DSIR double-rumors spreading model in complex networks // Chaos, Solitons and Fractals. 2018. V. 110. P. 191–202.Zan Y. DSIR double-rumors spreading model in complex networks // Chaos, Solitons and Fractals. 2018. V. 110. P. 191–202.Witten G., Poulter G. Simulations of infections diseases on networks // Computers in Biology and Medicine. 2007. V. 37. № 2. Р. 195–205.Witten G., Poulter G. Simulations of infections diseases on networks // Computers in Biology and Medicine. 2007. V. 37. № 2. Р. 195–205.Aksyonov K., Bykov E., Aksyonova O., Nevolina A., Goncharova N. Architecture of the Multi-agent Resource Conversion Processes Extended with Agent Coalitions : IEEE International Symposium on Robotics and Intelligent Sensors, IRIS 2016. Hosei University, Tokyo, Japan, December 17–20, 2016, Code 134518 // Procedia Computer Science. 2017. V. 105. Р. 221–226.Aksyonov K., Bykov E., Aksyonova O., Nevolina A., Goncharova N. Architecture of the Multi-agent Resource Conversion Processes Extended with Agent Coalitions : IEEE International Symposium on Robotics and Intelligent Sensors, IRIS 2016. Hosei University, Tokyo, Japan, December 17–20, 2016, Code 134518 // Procedia Computer Science. 2017. V. 105. Р. 221–226.

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