Informatics and Applications
2023, Volume 17, Issue 1, pp 28-34
AN AVERAGE DISTANCE IN THE POWER-LAW CONFIGURATION GRAPHS
Abstract
In random configuration graphs with a discrete power-law 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 pre-asymptotic 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 power-law relationships of the internet topology. Comput. Commun. Rev. 29:251-262. doi: 10.1145/316194.316229.
- Reittu, H., and I. Norros. 2004. On the power-law random graph model of massive data networks. Perform. Evaluation 5(1-2)5:3-23. doi: 10.1016/S0166-5316(03)00097-X.
- 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.
- Chung, F., and L. Lu. 2002. The average distances in random graphs with given expected degrees. P. Natl. Acad. Sci. USA 99(25):15879-15882. doi: 10.1073/pnas.252631999.
- Dijkstra, E.W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1(1):269-271. doi: 10.1007/BF01386390.
[+] About this article
Title
AN AVERAGE DISTANCE IN THE POWER-LAW CONFIGURATION GRAPHS
Journal
Informatics and Applications
2023, Volume 17, Issue 1, pp 28-34
Cover Date
2023-04-10
DOI
10.14357/19922264230104
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
configuration graph; power-law 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
|