2016 · 25 citations · 15 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGraph AlgorithmsGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsNetwork CentralityAll-pairs Shortest PathsBetweenness CentralityDegree ReductionGraph ProcessingHigh PerformanceMulti-gpu ArchitecturesMulti-gpu ComputingMulti-gpu Systems
Betweenness Centrality (BC) is steadily growing in popularity as a metrics of the influence of a vertex in a graph. The BC score of a vertex is proportional to the number of all-pairs-shortest-paths passing through it. However, complete and exact BC computation for a large-scale graph is an extraordinary challenge that requires high performance computing techniques to provide results in a reasonable amount of time. Our approach combines bi-dimensional (2-D) decomposition of the graph and multi-level parallelism together with a suitable data-thread mapping that overcomes most of the difficulties caused by the irregularity of the computation on GPUs. In order to reduce time and space requirements of BC computation, a heuristics based on 1-degree reduction technique is developed as well. Experimental results on synthetic and real-world graphs show that the proposed techniques are well suited to compute BC scores in graphs which are too large to fit in the memory of a single computational node.
15
A Set of Measures of Centrality Based on Betweenness
Linton C. Freeman · Sociometry · 1977 · 10.2K citations
What is Twitter, a social network or a news media?
Haewoon Kwak, Changhyun Lee, Hosung Park et al. · 2010 · 6.7K citations · Full text
A faster algorithm for betweenness centrality*
Ulrik Brandes · Journal of Mathematical Sociology · 2001 · 4.9K citations · Full text
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations