Preview

Вестник кибернетики

Расширенный поиск

Распределения степеней в графах с линейным правилом предпочтительного связывания и в графах Джексона – Роджерса

Полный текст:

Аннотация

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

Об авторах

В. Н. Задорожный
Омский государственный технический университет
Россия


Е. Б. Юдин
Институт математики им. С. Л. Соболева, Сибирское отделение РАН
Россия
г. Новосибирск


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

1. Barabasi A. L., Albert R. Emergence of scaling in random networks // Science. 1999. V. 286. P. 509–512.

2. Barabasi A. L. Scale-free networks: A decade and beyond // Science. 2009. V. 325. P. 412– 413.

3. Jackson M. O., Rogers B. W. Meeting Strangers and Friends of Friends: How Random are Social Networks? Forthcoming // American Economic Review, 2006.

4. Jackson M. O. Social and Economic Networks: Models and Analysis. Stanford University ; Santa Fe Institute: CIFAR, 2010.

5. 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.

6. Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. 2010. № 6. С. 2–11.

7. 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.

8. 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.

9. 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.

10. 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.

11. Karrer B., Newman M. E. J. Competing epidemics on complex networks // Phys Rev. 2011. № 84.

12. Boccaletti S., Latora V., Moreno Y., Chavez M., Hwang D-U. Complex networks: Structure and dynamics // Physics Reports. 2006. № 424. Р. 175–308.

13. Zan Y. DSIR double-rumors spreading model in complex networks // Chaos, Solitons and Fractals. 2018. V. 110. P. 191–202.

14. Witten G., Poulter G. Simulations of infections diseases on networks // Computers in Biology and Medicine. 2007. V. 37. № 2. Р. 195–205.

15. 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.


Рецензия

Для цитирования:


Задорожный В.Н., Юдин Е.Б. Распределения степеней в графах с линейным правилом предпочтительного связывания и в графах Джексона – Роджерса. Вестник кибернетики. 2018;(3):68-81.

For citation:


Zadorozhnyi V.N., Yudin E.B. Degrees Distributions in Linear Preferential Attachment Graphs and Jackson – Rogers Graphs. Proceedings in Cybernetics. 2018;(3):68-81. (In Russ.)

Просмотров: 38


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1999-7604 (Online)