Identification of Key Nodes by Algorithm of Betweenness Centrality Based on Traversal of Spark Graph

DOI

10.2991/cnci-19.2019.44How to use a DOI?

Keywords

Global network topology, the backtracking of the graph, betweenness centrality, the traversal of graph, the platform of Spark GRAPHX distributed graph processing.

Abstract

The betweenness center algorithm, which relies on the global network topology, can effectively identify the key nodes of the network.In the existing algorithm for accurately calculating betweenness centrality, the algorithm proposed by Ulrik brands based on the backtracking of graph is recognized as the fastest running, and its running time is still difficult to accept.The peer proposes approximate calculation and parallel computation of the betweenness Center to shorten the running time, and the running results and time are still difficult to accept.For this reason, this paper proposes an algorithm of betweenness obtains the total number of shortest paths in the network and the number of bars each node appears in the middle of the shortest path through the traversal of the graph, and then accurately calculates betweenness centrality of the nodes by using the formula of betweenness centrality, and implements the algorithm on the platform of Spark GRAPHX distributed graph processing. Experiments show that, this method is consistent with the method proposed by Ulrik brands to identify key nodes, the running time is halved, and it is suitable for large-scale networks.

Copyright

© 2019, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Hongye Xue
AU  - Tianmei Li
AU  - Xiangyu Luo
PY  - 2019/05
DA  - 2019/05
TI  - Identification of Key Nodes by Algorithm of Betweenness Centrality Based on Traversal of Spark Graph
BT  - Proceedings of the 2019 International Conference on Computer, Network, Communication and Information Systems (CNCI 2019)
PB  - Atlantis Press
SP  - 299
EP  - 305
SN  - 2352-538X
UR  - https://doi.org/10.2991/cnci-19.2019.44
DO  - 10.2991/cnci-19.2019.44
ID  - Xue2019/05
ER  -