Informatics and Applications
2019, Volume 13, Issue 3, pp 9-13
ON THE ASYMPTOTICS OF CLUSTERING COEFFICIENT IN A CONFIGURATION GRAPH WITH UNKNOWN DISTRIBUTION OF VERTEX DEGREES
Abstract
The author considers configuration graphs with vertex degrees being independent identically distributed random variables. The degree of each vertex equals to the number of incident half-edges that are numbered in an arbitrary order. The graph is constructed by joining each half-edge to another equiprobably to form edges. Configuration graphs are widely used for modeling of complex communication networks such as the Internet, social, transport, telephone networks. The distribution of vertex degrees can be unknown. It is only assumed that this distribution either has a finite variance or that some sufficient weak constraints on the asymptotic behavior of the tail are satisfied. The notion of clustering coefficient and its properties in such graphs are discussed. The author proves the limit theorem for the clustering coefficient with the number of vertices tending to infinity. The conditions under which this coefficient increases indefinitely are found.
[+] References (8)
- Hofstad, R. 2017. Random graphs and complex networks.
Cambridge: Cambridge University Press. Vol. 1. 337 p.
- Barabasi, A.-L., and R. Albert. 1999. Emergence of scaling
in random networks. Science 286:509-512.
- 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.
5. Pavlov, Yu. L. 2018. Conditional configuration graphs with discrete power-law distribution of vertex degrees. Sb. Math. 209(2):258-275.
6. Pavlov, Yu. L., and I. A. Cheplyukova. 2018. On asymptotics of degree structure of configuration graphs with restrictions on number of edges. Discrete Math. 28(2):58-79.
7. Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45(3):3-23.
8. Leri, M., and Y. Pavlov. 2016. Forest fire models on con-figuration random graphs. Fund. Inform. 145(3):313-322.
[+] About this article
Title
ON THE ASYMPTOTICS OF CLUSTERING COEFFICIENT IN A CONFIGURATION GRAPH WITH UNKNOWN DISTRIBUTION OF VERTEX DEGREES
Journal
Informatics and Applications
2019, Volume 13, Issue 3, pp 9-13
Cover Date
2019-09-30
DOI
10.14357/19922264190302
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
random graphs; configuration graphs; clustering coefficient; limit theorems
Authors
Yu. L. Pavlov 
Author Affiliations
Institute of Applied Mathematical Research, Karelian Research Centre of the Russian Academy of Sciences,
11 Pushkinskaya Str., Petrozavodsk 185910, Karelia, Russian Federation
|