ML p(r)ior | Algorithms and Heuristics for Scalable Betweenness Centrality Computation on Multi-GPU Systems

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

2016-02-02
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-04-01

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

Highlights - Most important sentences from the article

2019-03-16
1903.06950 | cs.DC

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

Highlights - Most important sentences from the article

2019-02-10

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

Highlights - Most important sentences from the article

2019-02-23
1902.08819 | cs.DC

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

Highlights - Most important sentences from the article

2019-03-28

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

Highlights - Most important sentences from the article

2017-10-20

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

Highlights - Most important sentences from the article

2018-12-10
1812.04070 | cs.DC

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

Highlights - Most important sentences from the article

2019-04-09

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

Highlights - Most important sentences from the article

2018-12-01

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

Highlights - Most important sentences from the article

2019-02-05

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

Highlights - Most important sentences from the article

2018-10-28

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

Highlights - Most important sentences from the article

2018-12-11
1812.04380 | cs.DC

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

Highlights - Most important sentences from the article

2019-04-03
1904.02241 | cs.DC

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

Highlights - Most important sentences from the article

2018-05-14

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

Highlights - Most important sentences from the article

2018-07-14
1807.08804 | cs.DB

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

Highlights - Most important sentences from the article

2017-10-23

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