Scaling betweenness centrality using communication-efficient sparse matrix multiplication

Edgar Solomonik, Maciej Besta, Flavio Vella, Torsten Hoefler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450351140
DOIs
StatePublished - Nov 12 2017
EventInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 - Denver, United States
Duration: Nov 12 2017Nov 17 2017

Publication series

NameProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

Other

OtherInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
CountryUnited States
CityDenver
Period11/12/1711/17/17

Keywords

  • Betweenness centrality
  • Communication cost
  • Parallel algorithm
  • Sparse matrix multiplication

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Scaling betweenness centrality using communication-efficient sparse matrix multiplication'. Together they form a unique fingerprint.

  • Cite this

    Solomonik, E., Besta, M., Vella, F., & Hoefler, T. (2017). Scaling betweenness centrality using communication-efficient sparse matrix multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 [47] (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017). Association for Computing Machinery, Inc. https://doi.org/10.1145/3126908.3126971