Edge v. Node Parallelism for Graph Centrality Metrics

GPU Computing Gems – Jade Edition, Oct. 2011, pp 15-28

Graphs help us model and understand various structures, but understanding large graphs, such as those now generated by instruments, simulations and the internet, increasingly depend on statistics and characterizations. Centrality metrics indicate which nodes and edges are important, to better analyze, simplify, categorize and visualize large graphs, but are expensive to compute especially on large graphs, and their parallel implementation on the most common \scale-free" graphs can su er severe load imbalance. This chapter proposes an improved edge-parallel approach for computing centrality metrics that can also accelerate breadth- rst search and all-pairs shortest path.

parallel_bc.zip (source code)51.25 KB

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer