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 language | English (US) |
---|---|
Pages | 3-10 |
Number of pages | 8 |
DOIs | |
State | Published - 2014 |
Externally published | Yes |
Event | 2014 1st Workshop on Parallel Programming for Analytics Applications, PPAA 2014 - Orlando, FL, United States Duration: Feb 16 2014 → Feb 16 2014 |
Other
Other | 2014 1st Workshop on Parallel Programming for Analytics Applications, PPAA 2014 |
---|---|
Country/Territory | United States |
City | Orlando, FL |
Period | 2/16/14 → 2/16/14 |
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Software
Keywords
- Graph algorithms
- Parallel algorithms
- Scalable programming
- Social network analysis