Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.

Scaling betweenness centrality using communication-efficient sparse matrix multiplication / Solomonik, E.; Besta, M.; Vella, F.; Hoefler, T.. - ELETTRONICO. - (2017), pp. 1-14. (Intervento presentato al convegno International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 tenutosi a Denver, CO, USA nel 12 - 17 November 2017) [10.1145/3126908.3126971].

Scaling betweenness centrality using communication-efficient sparse matrix multiplication

Vella F.;
2017-01-01

Abstract

Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.
2017
Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
New York, USA
Association for Computing Machinery, Inc
9781450351140
Solomonik, E.; Besta, M.; Vella, F.; Hoefler, T.
Scaling betweenness centrality using communication-efficient sparse matrix multiplication / Solomonik, E.; Besta, M.; Vella, F.; Hoefler, T.. - ELETTRONICO. - (2017), pp. 1-14. (Intervento presentato al convegno International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 tenutosi a Denver, CO, USA nel 12 - 17 November 2017) [10.1145/3126908.3126971].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/332840
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 42
  • ???jsp.display-item.citation.isi??? 31
social impact