GSoC 2018 - Parallel Implementations of Graph Analysis Algorithms

This blog briefly summarises my GSoC 2018 project (Parallel Graph Development) and the results achieved. For a detailed description, please refer to my GSoC blog.

The project is spread over the LightGraphs codebase. It involved:

  1. Producing parallel implementations of crucial graph algorithms.
  2. Improving sequential implementation of crucial graph algorithms in LightGraphs.
  3. Implementing heuristics to obtain good solutions to crucial NP-Hard graph problems.

The benchmarks were conducted on a 64-bit linux machine using 4 cores.


Benchmark Graph Datasets:

No. Graph Vertices Edges
1 Twitter Social Circles 81,306 1,342,310
2 Astro-Physics Collaboration 17,903 197,031
3 Facebook Social Circles 4,039 88,234


The graphs were obtained from the SNAPDatasets repository.


Speed-up on parallelization with 4 cores:

Algorithm Twitter Astro-Physics Facebook
Breadth-First Search 1.92 2.59 1.54
PageRank 1.77 1.54 1.65
Bellman Ford SSSP - - 1.88
Floyd Warshall APSP - - 1.27
Johnson APSP - - 2.10
Randomized Heuristic 1.88 1.70 1.66
Betweenness Centrality - - 1.96
Closeness Centrality - - 2.17
Stress Centrality - - 1.66

Speed-up on sequential optimization:

Algorithm Twitter Astro-Physics Facebook
PageRank 3.05 3.37 3.17
Dijkstra SSSP 2.80 2.10 1.68
Prim MST 7.65 4.25 4.05
Kruskal MST 7.70 3.37 2.80

Absolute runtime (in ms) of Bread-First Search:

Algorithm Twitter Astro-Physics Facebook
Parallel 7.07 1.20 0.26
Sequential 13.63 3.11 0.41

Get the code

This section lists the functionality implemented and a link to the corresponding branch in my cloned LightGraphs repository.

Completed and merged

The following branches have been merged into LightGraphs master:

Completed but not applicable

The following branches have not been merged into LightGraphs master as the functionality is not suitable to LightGraphs:

Requires Improvement

The following branches have not been merged into LightGraphs as the parallel implementations are slower than the sequential implementation:

Acknowledgements

I would like to thank my mentor, Divyansh Srivastava and LightGraphs co-owner, Seth Bromberger for reviewing my code and providing valuable advice during the summer. I would also like to thank The Julia Project and NUMFocus for sponsoring my attendance to JuliaCon 2018.