Degrees Distributions in Linear Preferential Attachment Graphs and Jackson – Rogers Graphs
Abstract
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.
About the Authors
V. N. Zadorozhnyi
Omsk State Technical University
Russian Federation
Russian Federation
E. B. Yudin
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
Russian Federation
Novosibirsk
Russian Federation
Novosibirsk
References
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.
Review
For citations:
Zadorozhnyi V.N., Yudin E.B. Degrees Distributions in Linear Preferential Attachment Graphs and Jackson – Rogers Graphs. Proceedings in Cybernetics. 2018;(3 (31)):68-81. (In Russ.)
Views:
146
Email this article 