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 . d~(2max)）, where d_(ma)x 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, V ? 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(V . d~2_max + t_(VC)) where d_(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.