Network clustering coefficient without degree-correlation biases

The clustering coefficient quantifies how well connected are the neighbors of a vertex in a graph. In real networks it decreases with the vertex degree, which has been taken as a signature of the network hierarchical structure. Here we show that this signature of hierarchical structure is a consequence of degree-correlation biases in the clustering coefficient definition. We introduce a definition in which the degree-correlation biases are filtered out, and provide evidence that in real networks the clustering coefficient is constant or decays logarithmically with vertex degree.

Figure 1

Double star with two vertices, 1 and 2, connected to $N-2$ other vertices. The neighbors of vertex 1 (or 2) are connected as most as their degrees allow. Yet, with the usual definition of clustering coefficient we obtain $c_1=O(1∕N)$, approaching zero in the limit $N⪢1$.

Figure 2

Algorithm to compute ${\omega }_i$. (a) A vertex $i$ (open circle) is connected to five neighbors (filled circles) with degree sequence {8,7,2,2,2}. (b) Since each neighbor can be connected at most with four other neighbors, we replace the neighbors degree sequence (lowest row) by {4,4,1,1,1} (middle row). It is easy to see that after connecting the first neighbor to all others, we get four triangles and three extra edges that cannot be used anymore (upper row). Summarizing, for this example, ${\omega }_i=4$, ${\Omega }_i=5$ and $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. (c) Subgraph with maximum number of edges among the neighbors, with $c_i=0.4$ and ${\tilde{c}}_i=1$.

Figure 3

Average clustering as a function of the vertex degree, as computed using the usual definition (circles), our definition approximating ${\omega }_i$ by ${\Omega }_i$ (squares), and our definition using ${\omega }_i$ (triangles). The graphs are shown in increasing order of their assortativity, with the most disassortative graph on the top, and the more assortative graph on the bottom.