Efficient computation of the Weighted Clustering Coefficient

Abstract

The clustering coefficient of an unweighted network has been extensively used to quantify how tightly connected is the neighbor around a node and it has been widely adopted for assessing the quality of nodes in a social network. The computation of the clustering coefficient is challenging since it requires to count the number of triangles in the graph. Several recent works proposed efficient sampling, streaming and MapReduce algorithms that allow to overcome this computational bottleneck.

As a matter of fact, the intensity of the interaction between nodes, that is usually represented with weights on the edges of the graph, is also an important measure of the statistical cohesiveness of a network. Recently various notions of weighted clustering coefficient have been proposed but all those techniques are hard to implement on large-scale graphs.

In this work we show how standard sampling techniques can be used to obtain efficient estimators for the most commonly used measures of weighted clustering coefficient. Furthermore we also propose a novel graph-theoretic notion of clustering coefficient in weighted networks.

Acknowledgments

We thank Corinna Cortes for suggesting the problem.

Notes

¹ We note that our definition of weighted random random graph is different from the definition of [10] and it is more in line with the standard definition used in data mining and biology [12].

² The problem of computing a core decomposition in an uncertain graph with different probabilities on edges has been considered in [5]. The authors show how to compute the expected degree of an uncertain graph in polynomial time. This method cannot however be applied to speed up the computation of the the novel notion of weighted clustering coefficient we propose.

³ This setting is particularly relevant when graphs are generated using inference models [13].

⁴ Note that enumerating all the triangles in the graph would not work in this setting because of the dependency induced by the number of wedges in the realization of the random graph.

⁵ Unfortunately to the best of our knowledge, there is no analytic technique to estimate this quantity correctly or with a close approximation without using a dynamic programming.

⁶ Note that for this to work it is fundamental that the weight on the edges have been normalized and so are in [0, 1].

⁷ Note that a naive implementation of the sampling procedure would have running time quadratic in the size of the adjacency list. Fortunately this is not necessary in fact it is possible to select a random pair of neighbors in linear time. In particular, it is enough to assign to each neighbor a random number and then select the two neighbors with the smallest assigned values. In this way each pair of nodes has the same probability of being selected and so we can obtain a random sample.

⁸ Experimentally we observed that a nonlinear mapping perform better than the linear mapping proposed by Onnela et al.

⁹ Note that all the discussed notion of clustering coefficient can be extended to capture the directionality of the edges.