# Scaling betweenness centrality using communication-efficient sparse matrix multiplication

arXiv: https://arxiv.org/abs/1609.07008 · HTML: https://mlsanity.com/paper/1609.07008/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2016.

## Built on by (most cited first, 11 of 11)

- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks](https://mlsanity.com/paper/2602.09716/) (2026)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [The Ubiquitous Sparse Matrix-Matrix Products](https://mlsanity.com/paper/2508.04077/) (2025)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)

## Abstract (arXiv)

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 Centrality (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 with n vertices and average degree k=n/p2/3. We formulate, 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.