Informatics and Applications
2024, Volume 18, Issue 1, pp 46-53
LOCAL TREELIKE STRUCTURE IN THE POWER-LAW CONFIGURATION GRAPHS
Abstract
The local treelike structure of configuration graphs intended for modeling complex communication networks is stidued. In such graphs, the vertex degrees are independent and identically distributed according to the power law. In the case of a limited number of graph vertices, the dependences of the maximum volume of a treelike subgraph on the number of graph vertices and the vertex degree distribution parameter are found. The same problem was solved for the number of trees of a given size. Estimates are also given for the average size of a tree in the graph. It is shown that with a limited number of vertices of the configuration graph, the found dependences statistically significantly improve the description of the network structure in comparison with the previously known asymptotic models.
[+] References (9)
- Faloutsos, C., P. Faloutsos, and M. Faloutsos. 1999. On power-law relationships of the internet topology. Comput. Commun. Rev. 29:251-262. doi: 10.1145/316194.316229.
- Durrett, R. 2007. Random graph dynamics. Cambridge: Cambridge University Press. 221 p. doi: 10.1017/ CBO9780511546594.
- Hofstad, R. 2017. Random graphs and complex networks. Cambridge: Cambridge University Press. Vol. 1. 337 p. doi: 10.1017/9781316779422.
- Hofstad, R. 2023. Random graphs and complex networks. Notes RGCNII. Vol. 2. 314 p. Available at: https://www.win. tue.nl/?rhofstad/NotesRGCNII.pdf (accessed April 17, 2023).
- Bollobas, B. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combin. 1(4):311-316. doi: 10.1016/S0195- 6698(80)80030-8.
- Reittu, H., and I. Norros. 2004. On the power-law random graph model of massive data networks. Perform. Evaluation. 55(1-2):3-23. doi: 10.1016/S0166-5316(03)00097-X.
- Pavlov, Yu. L. 2021. The maximum tree of a random forest in the configuration graph. Sb. Math. 212(9):1329-1346. doi: 10.1070/SM9481.
- Pavlov, Yu. L., and I. A. Cheplyukova. 2022. Sizes of trees in a random forest and configuration graphs. P. Steklov Inst. Math. 316:280-297. doi: 10.1134/S0081543822010205.
- Pavlov, Yu. L. 2000. Random forests. Utrecht: VSP. 122 p.
[+] About this article
Title
LOCAL TREELIKE STRUCTURE IN THE POWER-LAW CONFIGURATION GRAPHS
Journal
Informatics and Applications
2024, Volume 18, Issue 1, pp 46-53
Cover Date
2024-04-10
DOI
10.14357/19922264240107
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
configuration graph; power-law distribution; local treelike structure; tree size; simulations
Authors
M. M. Leri  and Yu. L. Pavlov
Author Affiliations
Institute of Applied Mathematical Research, Karelian Research Center of the Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
|