### Algorithms and Heuristics for Scalable Betweenness Centrality Computation on Multi-GPU Systems

**2016-02-02**

1602.00963 | cs.DC

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. Furthermore, we propose novel
heuristics which exploit the topology information of the graph in order to
reduce time and space requirements of BC computation. Experimental results on
synthetic and real-world graphs show that the proposed techniques allow the BC
computation of graphs which are too large to fit in the memory of a single
computational node along with a significant reduction of the computing time.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-04-01**

1904.00549 | cs.DC

With the rapid growth of large online social networks, the ability to analyze
large-scale social str… show more

**2019-03-16**

1903.06950 | cs.DC

Finding the Eulerian circuit in graphs is a classic problem, but inadequately
explored for parallel … show more

**2019-02-10**

1902.03522 | cs.DS

Motivated by performance optimization of large-scale graph processing systems
that distribute the gr… show more

**2019-02-23**

1902.08819 | cs.DC

We consider the Backup Placement problem in networks in the
$\mathcal{CONGEST}$ distributed setting.… show more

**2019-03-28**

1903.12085 | cs.DC

Dijkstra's algorithm for the Single-Source Shortest Path (SSSP) problem is
notoriously hard to paral… show more

**2017-10-20**

1710.07565 | cs.DC

Analyzing massive complex networks yields promising insights about our
everyday lives. Building scal… show more

**2018-12-10**

1812.04070 | cs.DC

With high computation power and memory bandwidth, graphics processing units
(GPUs) lend themselves t… show more

**2019-04-09**

1904.04626 | cs.SI

Hidden graphs are flexible abstractions that are composed of a set of known
vertices (nodes), wherea… show more

**2018-12-01**

1812.00283 | cs.SI

Bipartite networks are of great importance in many real-world applications.
In bipartite networks, b… show more

**2019-02-05**

1902.01543 | cs.DS

In the recent years, the scale of graph datasets has increased to such a
degree that a single machin… show more

**2018-10-28**

1810.11899 | cs.LG

The Graph Convolutional Network (GCN) model and its variants are powerful
graph embedding tools for … show more

**2018-12-11**

1812.04380 | cs.DC

Nowadays, in the big data era, social networks, graph databases, knowledge
graphs, electronic commer… show more

**2019-04-03**

1904.02241 | cs.DC

Efficient Graph processing is challenging because of the irregularity of
graph algorithms. Using GPU… show more

**2018-05-14**

1805.05208 | cs.DS

There has been significant interest in parallel graph processing recently due
to the need to quickly… show more

**2018-07-14**

1807.08804 | cs.DB

We utilize commonsense knowledge bases to address the problem of real- time
multimodal analysis. In … show more

**2017-10-23**

1710.08231 | cs.DS

Partitioning graphs into blocks of roughly equal size such that few edges run
between blocks is a fr… show more