Faster Clustering Coefficient Using Vertex Covers

摘要

Clustering coefficients, also called triangle counting, is a widely-used graph analytic for measuring the closeness in which vertices cluster together. Intuitively, clustering coefficients can be thought of as the ratio of common friends versus all possible connections a person might have in a social network. The best known time complexity for computing clustering coefficients uses adjacency list intersection and is O(V. d2max), where dmax is the size of the largest adjacency list of all the vertices in the graph. In this work, we show a novel approach for computing the clustering coefficients in an undirected and unweighted graphs by exploiting the use of a vertex cover, hatV subseteq V. This new approach reduces the number of times that a triangle is counted by as many as 3 times per triangle. The complexity of the new algorithm is O(hatV. hatd_max^2 + t_VC) where hatd_max is the size of the largest adjacency list in the vertex cover and t_VC is the time needed for finding the vertex cover. Even for a simple vertex cover algorithm this can reduce the execution time 10-30% while counting the exact number of triangles (3-circuits). We extend the use of the vertex cover to support counting squares (4-circuits) and clustering coefficients for dynamic graphs.