Local treelike structure in the power-law configuration graphs

M. M. Leri, Yu. L. Pavlov

Institute of Applied Mathematical Research, Karelian Research Center of the Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation

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.

Keywords: configuration graph, power-law distribution, local treelike structure, tree size, simulations.

Received: 19.06.2023

DOI: 10.14357/19922264240107