Dynamic merging of frontiers for accelerating the evaluation of betweenness centrality
MetadataShow full item record
SubjectShortest paths; GPU computing; Parallel algorithm; Large-scale graphs; Graph algorithms; Betweenness centrality
Betweenness Centrality (BC) is a widely used metric of the relevance of a node in a network. The fastestknown algorithm for the evaluation of BC on unweighted graphs builds a tree representing information about the shortest paths for each vertex to calculate its contribution to the BC score. Actually, for specific vertices, the shortest-path trees of neighboring nodes could be leveraged to reduce the computational burden, but existing BC algorithms do not exploit that information and carry out redundant computations.We propose a new algorithm, called dynamic merging of frontiers, which makes use of such information to derive the BC score of degree-2 vertices by re-using the results of the sub-trees of the neighbors.We implemented our idea in parallel fashion exploiting Graphics Processing Units. Compared to state-of-the-art implementations, our approach achieves a linear improvement in the number of degree-2 vertices and an average improvement of 4× over a variety of real-world graphs.
Showing items related by title, author, creator and subject.
Bonani A; Del Fatto V; Gennari R (Association for Computing Machinery, Inc, 2018)Algorithmic thinking is at the core of computational thinking. Tangible interactive solutions can help children develop algorithmic thinking skills. This paper focusses on exploratory research concerning tangibles for graph ...
Bonani A; Del Fatto V; Dodero G; Gennari R (RWTH, 2017)Algorithmic thinking is at the hearth of the best known computational thinking. It requires the abilities to decompose and model a problem with a certain representation, and devise or understand an algorithm for making a ...
Bonani A; Del Fatto V; Dodero G; Gennari R; Raimato G (Springer, 2017)The paper presents exploratory steps of the design of interactive tangible objects for the scaffolding of algorithmic thinking of 9–13 years old school classes, and specifically graph algorithmic thinking. By following a ...