Vertex-centric Parallel Algorithms for Identifying Key Vertices in Large-Scale Graphs

摘要

Betweenness centrality is a metric to measure the relative importance of vertices within a graph. The computation of betweenness centrality is based on shortest paths which requires O(n+m) space and O(mn) and O(nm+n log n) time on unweighted and weighted graphs, respectively. It is time-consuming to deal with large-scale graphs, which motivates us resort to distributed computing and parallel algorithms. In this paper, we design a vertex-based parallel algorithm following the shortest path approach (SPBC). Moreover, we propose a distributed algorithm based on message propagation(MPBC) to quantify the importance of vertices. MPBC takes into account the real situation of information diffusion in social networks. We implement our algorithms on Graphlab and evaluate them through comprehensive experiments. The results show that both SPBC and MPBC scale well with the increasing number of machines. SPBC on 2 machines outperforms the classical centralized algorithm by 1.59 times in terms of running time. MPBC can handle graph with ten millions of vertices and edges within an acceptable time where classical algorithms become infeasible.