high performance computing on graphics processing units: hgpu.org

Betweenness centrality is an important metric in the study of network analysis. This report discusses the problem of exact computation of betweenness cenrality index in network analysis. BC is an important metric in small world network analysis which is expensive to compute. A new strategy is presented to parallelize the best known serial algorithm for computing BC on CUDA architecture exploring parallelism at all the different levels of granularity offered in the algorithm. Further optimizations are made into this strategy by exploiting CUDA specific notions of coalesced memory accesses, warping, shared memory etc.