Faster clustering coefficient using vertex covers

Oded Green, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - SocialCom/PASSAT/BigData/EconCom/BioMedCom 2013
Pages321-330
Number of pages10
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 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 - Washington, DC, United States
Duration: Sep 8 2013Sep 14 2013

Publication series

NameProceedings - SocialCom/PASSAT/BigData/EconCom/BioMedCom 2013

Conference

Conference2013 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
Country/TerritoryUnited States
CityWashington, DC
Period9/8/139/14/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Graph algorithms
  • Network science
  • Social network analysis

Fingerprint

Dive into the research topics of 'Faster clustering coefficient using vertex covers'. Together they form a unique fingerprint.

Cite this