This article is cited in 1 paper

On the asymptotics of clustering coefficient in a configuration graph with unknown distribution of vertex degrees

Yu. L. Pavlov

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

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.

Keywords: random graphs, configuration graphs, clustering coefficient, limit theorems.

Received: 09.01.2019

DOI: 10.14357/19922264190302