An MPI-Parallel Algorithm for Static and Dynamic Top-k Harmonic Centrality

• Alexander van der Grinten Humboldt-Universität zu Berlin
• Geert Custers Delft University of Technology
• Duy Le Thanh Humboldt-Universität zu Berlin
• Henning Meyerhenke Humboldt-Universität zu Berlin

Resumo

Analyzing large graphs in parallel has received considerable attention recently due to ever increasing data set sizes. Centrality measures indicate the importance of vertices (or edges) and belong to the most widely used analytic kernels. Harmonic centrality is a popular vertex centrality measure with many desirable properties. Since most of the applications of vertex centrality rely only on the ranking of vertices and not on their exact centrality scores, previous research has considered various algorithms that can quickly determine a ranking of the top-k vertices with highest harmonic centrality. Such algorithms are available for many types of real-world graphs, including dynamic graphs. Yet, no attempts have been made to efficiently parallelize these top-k algorithms (besides naive implementations based on a global lock). In this paper, we propose an MPI-distributed algorithm for (dynamic) top-k harmonic centrality. Our algorithm exploits an algebraic BFS technique and batching to parallelize the approximation of centrality scores of multiple vertices. Likewise, we use algebraic techniques to compute various bounds and heuristics that are necessary to obtain a fast top-k algorithm. Experiments demonstrate that our MPI-parallel algorithm outperforms existing implementations. Consequently, our new approach allows the computation of top-k harmonic centrality on graphs that are substantially larger.

Palavras-chave: algebraic graph algorithm, network analysis, harmonic centrality, top-k ranking, MPI parallelism