Load balanced clustering coefficients

Oded Green, Lluís Miquel Munguía, David A. Bader

Research output: Contribution to conferencePaperpeer-review

18 Scopus citations

Abstract

Clustering coefficients is a building block in network sciences that offers insights on how tightly bound vertices are in a network. Effective and scalable parallelization of clustering coefficients requires load balancing amongst the cores. This property is not easy to achieve since many real world networks are scale free, which leads to some vertices requiring more attention than others. In this work we show two scalable approaches that load balance clustering coefficients. The first method achieves optimal load balancing with an O(|E|) storage requirement. The second method has a lower storage requirement of O(|V |) at the cost of some imbalance. While both methods have a similar time complexity, they represent a tradeoff between maintaining a balanced workload and memory complexity. Using a 40-core system we show that our load balancing techniques outperform the widely used and simple parallel approach by a factor of 3X-7.5X for real graphs and 1.5X-4X for random graphs. Further, we achieve 25X - 35X speedup over the sequential algorithm for most of the graphs.

Original languageEnglish (US)
Pages3-10
Number of pages8
DOIs
StatePublished - 2014
Externally publishedYes
Event2014 1st Workshop on Parallel Programming for Analytics Applications, PPAA 2014 - Orlando, FL, United States
Duration: Feb 16 2014Feb 16 2014

Other

Other2014 1st Workshop on Parallel Programming for Analytics Applications, PPAA 2014
Country/TerritoryUnited States
CityOrlando, FL
Period2/16/142/16/14

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Software

Keywords

  • Graph algorithms
  • Parallel algorithms
  • Scalable programming
  • Social network analysis

Fingerprint

Dive into the research topics of 'Load balanced clustering coefficients'. Together they form a unique fingerprint.

Cite this