### 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 p^{1/3} less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p^{2/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 language | English (US) |
---|---|

Title of host publication | Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 |

Publisher | Association for Computing Machinery, Inc |

ISBN (Electronic) | 9781450351140 |

DOIs | |

State | Published - Nov 12 2017 |

Event | International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 - Denver, United States Duration: Nov 12 2017 → Nov 17 2017 |

### Publication series

Name | Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 |
---|

### Other

Other | International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 |
---|---|

Country | United States |

City | Denver |

Period | 11/12/17 → 11/17/17 |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Computer Networks and Communications
- Software

### Cite this

*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

**Scaling betweenness centrality using communication-efficient sparse matrix multiplication.** / Solomonik, Edgar Vadimovich; Besta, Maciej; Vella, Flavio; Hoefler, Torsten.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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, International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017, Denver, United States, 11/12/17. https://doi.org/10.1145/3126908.3126971

}

TY - GEN

T1 - Scaling betweenness centrality using communication-efficient sparse matrix multiplication

AU - Solomonik, Edgar Vadimovich

AU - Besta, Maciej

AU - Vella, Flavio

AU - Hoefler, Torsten

PY - 2017/11/12

Y1 - 2017/11/12

N2 - 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.

AB - 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.

KW - Betweenness centrality

KW - Communication cost

KW - Parallel algorithm

KW - Sparse matrix multiplication

UR - http://www.scopus.com/inward/record.url?scp=85040162024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040162024&partnerID=8YFLogxK

U2 - 10.1145/3126908.3126971

DO - 10.1145/3126908.3126971

M3 - Conference contribution

AN - SCOPUS:85040162024

T3 - Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

BT - Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

PB - Association for Computing Machinery, Inc

ER -