DescriptionBetweenness 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 BC algorithm based on novel sparse matrix multiplication routines that performs asymptotically less communication than previous alternatives. We formulate, implement, and prove MFBC's correctness 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 compares favorably to the CombBLAS library for social network graphs and is faster by up to 8x for denser random graphs. Our design methodology is readily extensible to other graph problems.