IIIT Hyderabad Publications
Parallel Ear Decomposition and Application to Betweenness Centrality
Author: Charudatt Pachorkar
Report no: IIIT/TH/2017/7
In recent years, the amount of information generated and stored is inconceivable. A plethora repsesentations are available to store such kind of data, with graphs being one of the most efficient ap- proaches, useful for studying and analysing various attributes of data. Considering amount of data to process, parallel computing is the most suitable option but many state of the art algorithms are not ef- ficient enough to take maximum advantage of available architectures. Hence researchers are focusing on development and enhancement of parallel graph algorithms. Parallel graph algorithms continue to attract a lot of attention in research given their applications to several fields of sciences and engineering. However, efficient design and implementations of graph algorithms on modern many-core accelerators has to contend with a host of challenges including not being able to reach full memory system through-put and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c and Intel Xeon E5-2650 improves the state-of-the-art by a factor of 2.3x and 2.02x on average respectively on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.
Full thesis: pdf
Centre for Security, Theory and Algorithms
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved.