Informatics and Applications
2023, Volume 17, Issue 1, pp 2834
AN AVERAGE DISTANCE IN THE POWERLAW CONFIGURATION GRAPHS
Abstract
In random configuration graphs with a discrete powerlaw vertex degree distribution with a fixed parameter, the average distance in the graph is considered, i. e., the arithmetic mean of distances between all pairs of graph nodes. This characteristic is estimated using simulation methods. Due to computational constraints, the author considers graphs in the preasymptotic domain (in this paper, these are the graphs up to 7000 nodes). The models of dependencies of the average distance on the graph size and the parameter of vertex degree distribution are reseived. The obtained results are compared with the results of theoretical studies of the typical distance in a graph in the asymptotics (i. e., when the number of graph vertices tends to infinity), given in the works by R. Hofstad
[+] References (10)
 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.
 Newman, M.E.J. 2010. Networks. An introduction. Oxford: Oxford University Press. 772 p. doi: 10.1093/ acprof:oso/9780199206650.001.0001.
 Newman, M.E.J. 2018. Networks. 2nd ed. Oxford: Oxford University Press. 800 p. doi: 10.1093/oso/9780198805090.001.0001.
 Hofstad, R. 2020. Random graphs and complex networks. Notes RGCNII. Vol. 2. 314 p. Available at: https:// www.win.tue.nl/~rhofstad/NotesRGCNII.pdf (accessed January 18, 2023)
 Faloutsos, C., P. Faloutsos, and M. Faloutsos. 1999. On powerlaw relationships of the internet topology. Comput. Commun. Rev. 29:251262. doi: 10.1145/316194.316229.
 Reittu, H., and I. Norros. 2004. On the powerlaw random graph model of massive data networks. Perform. Evaluation 5(12)5:323. doi: 10.1016/S01665316(03)00097X.
 Bollobas, B. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combin. 1(4):311316. doi: 10.1016/S0195 6698(80)800308.
 Chung, F., and L. Lu. 2002. The average distances in random graphs with given expected degrees. P. Natl. Acad. Sci. USA 99(25):1587915882. doi: 10.1073/pnas.252631999.
 Dijkstra, E.W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1(1):269271. doi: 10.1007/BF01386390.
[+] About this article
Title
AN AVERAGE DISTANCE IN THE POWERLAW CONFIGURATION GRAPHS
Journal
Informatics and Applications
2023, Volume 17, Issue 1, pp 2834
Cover Date
20230410
DOI
10.14357/19922264230104
Print ISSN
19922264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
configuration graph; powerlaw distribution; average distance in a graph; simulation
Authors
M. M. Leri
Author Affiliations
Institute of Applied Mathematical Research of the Karelian Research Center of the Russian Academy of Sciences,
11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
