Informatics and Applications
2021, Volume 15, Issue 1, pp 18-22
CONNECTIVITY OF CONFIGURATION GRAPHS IN COMPLEX NETWORK MODELS
Abstract
The author considers configuration graphs whose degrees of vertices are independent and identically distributed according to the generalized power-law distribution. Connections between vertices are equiprobably formed in compliance with their degrees. Such random graphs are often used for modeling complex communication networks like the Internet and social networks. It is assumed that the distribution of vertex degrees is unknown because it depends on a slowly varying function with unknown properties. The conditions are found under which a graph is asymptotically almost surely connected as the number of vertices tends to infinity. Under these conditions, estimates of the convergence rate to zero of the probability that the graph is not connected are obtained. The results in the present paper are proved using the properties of stable distributions and slowly varying functions.
[+] References (12)
- Hofstad, R. 2017. Random graphs and complex networks. Cambridge: Cambridge University Press. Vol. 1. 337 p.
- Faloutsos, C., P Faloutsos, and M. Faloutsos. 1999. On power-law relationships of the Internet topology. Comput. Commun. Rev. 29:251-262.
- Bollobas, B. A. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combin. 1:311-316.
- Reittu, H., and I. Norros. 2004. On the power-law random graph model of massive data networks. Perform. Evaluation 55:3-23.
- Durrett, R. 2007. Random graph dynamics. Cambridge: Cambridge University Press. 212 p.
- Pavlov, Yu. L., and I. A. Cheplyukova. 2008. Random graphs of Internet type and the generalised allocation scheme. Discrete Mathematics Applications 18(5):447-463.
- Pavlov, Yu. L., and E. V. Khvorostyanskaya. 2016. On the limit distributions of the degrees of vertices in configuration graphs with a bounded number of edges. Sb. Math. 207(3):400-417.
- Pavlov, Yu. L. 2018. Conditional configuration graphs with discrete power-law distribution of vertex degrees. Sb. Math. 209(2):258-275.
- Hofstad, R. 2020. Random graphs and complex Networks. Vol. 2. Notes RGCNII Available at: https:// www.win.tue.nl/^rhofstad/NotesRGCNII.pdf (accessed January 11, 2021).
- Pavlov, Yu. L. 2019. O svyaznosti konfiguratsionnykh grafov [On connectivity of configuration graphs]. Discrete Mathematics Applications 31(2):115-123.
- Ibragimov, I.A., and Yu.V. Linnik. 1965. Nezavisimye i statsionarno svyazannye velichiny [Independent and sta-tionary sequences of random variables]. Moscow: Nauka. 524 p.
- Bigham, N.H., C.M. Goldie, and J. L. Teugels. 1987. Regular variations. Encyclopedia of mathematics and its applications. Cambridge: Cambridge University Press. Vol. 27. 513 p.
[+] About this article
Title
CONNECTIVITY OF CONFIGURATION GRAPHS IN COMPLEX NETWORK MODELS
Journal
Informatics and Applications
2021, Volume 15, Issue 1, pp 18-22
Cover Date
2021-03-30
DOI
10.14357/19922264210103
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
random graphs; configuration graphs; random vertex degrees; graph connectivity
Authors
Yu. L. Pavlov 
Author Affiliations
Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences,
11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
|