Scaling Betweenness Centrality Using
Communication-Efficient Sparse Matrix Multiplication
Event Type
Paper
Communication Avoidance
Graph Algorithms
Linear Algebra
TimeThursday, November 16th10:30am -
11am
Location405-406-407
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.
Download PDF:
here
