TY - GEN

T1 - Faster clustering coefficient using vertex covers

AU - Green, Oded

AU - Bader, David A.

PY - 2013

Y1 - 2013

N2 - 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 · dmax2), 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, 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̂max 2 + tVC) where d̂max is the size of the largest adjacency list in the vertex cover and tVC 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.

AB - 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 · dmax2), 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, 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̂max 2 + tVC) where d̂max is the size of the largest adjacency list in the vertex cover and tVC 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.

KW - Graph algorithms

KW - Network science

KW - Social network analysis

UR - http://www.scopus.com/inward/record.url?scp=84893586887&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893586887&partnerID=8YFLogxK

U2 - 10.1109/SocialCom.2013.51

DO - 10.1109/SocialCom.2013.51

M3 - Conference contribution

AN - SCOPUS:84893586887

SN - 9780769551371

T3 - Proceedings - SocialCom/PASSAT/BigData/EconCom/BioMedCom 2013

SP - 321

EP - 330

BT - Proceedings - SocialCom/PASSAT/BigData/EconCom/BioMedCom 2013

T2 - 2013 ASE/IEEE Int. Conf. on Social Computing, SocialCom 2013, the 2013 ASE/IEEE Int. Conf. on Big Data, BigData 2013, the 2013 Int. Conf. on Economic Computing, EconCom 2013, the 2013 PASSAT 2013, and the 2013 ASE/IEEE Int. Conf. on BioMedCom 2013

Y2 - 8 September 2013 through 14 September 2013

ER -