2016/09/22 by Edgar Solomonik, Solomonik, Edgar, Maciej Besta +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #G.1.0 #G.2.2 #Interconnection Networks and Systems #Mathematical Software (cs.MS) #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1609.07008
openalex publication_date 2016/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Betweenness centrality (BC) is a crucial graph problem that measures the\nsignificance of a vertex by the number of shortest paths leading through it. We\npropose Maximal Frontier Betweenness Centrality (MFBC): a succinct BC algorithm\nbased on novel sparse matrix multiplication routines that performs a factor of\np1/3 less communication on p processors than the best known\nalternatives, for graphs with n vertices and average degree k=n/p2/3. We\nformulate, implement, and prove the correctness of MFBC for weighted graphs by\nleveraging monoids instead of semirings, which enables a surprisingly succinct\nformulation. MFBC scales well for both extremely sparse and relatively dense\ngraphs. It automatically searches a space of distributed data decompositions\nand sparse matrix multiplication algorithms for the most advantageous\nconfiguration. The MFBC implementation outperforms the well-known CombBLAS\nlibrary by up to 8x and shows more robust performance. Our design methodology\nis readily extensible to other graph problems.\n