@inproceedings{2c7fc2155eed495faa2e6d9c9b21ed99,
title = "Vertex-centric parallel algorithms for identifying key vertices in large-scale graphs",
abstract = "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+n2 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.",
keywords = "Key vertices, MPBC, Parallel algorithm, SPBC",
author = "Bo Li and Zhuangliang Gao and Jianwei Niu and Yanfei Lv and Hong Zhang",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015 ; Conference date: 24-08-2015 Through 26-08-2015",
year = "2015",
month = nov,
day = "23",
doi = "10.1109/HPCC-CSS-ICESS.2015.108",
language = "英语",
series = "Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "225--231",
booktitle = "Proceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015",
address = "美国",
}