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.

Dynamic merging of frontiers for accelerating the evaluation of betweenness centrality / Vella, F.; Bernaschi, M.; Carbone, G.. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - ELETTRONICO. - 23:(2018), pp. 1-19. [10.1145/3182656]

Dynamic merging of frontiers for accelerating the evaluation of betweenness centrality

Vella F.;
2018-01-01

Abstract

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.
2018
Vella, F.; Bernaschi, M.; Carbone, G.
Dynamic merging of frontiers for accelerating the evaluation of betweenness centrality / Vella, F.; Bernaschi, M.; Carbone, G.. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - ELETTRONICO. - 23:(2018), pp. 1-19. [10.1145/3182656]
File in questo prodotto:
File Dimensione Formato  
jea3182656.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 7.11 MB
Formato Adobe PDF
7.11 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/332866
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact