TY - GEN
T1 - Shortest path algorithm based on community detection
AU - Wang, Huixiong
AU - Fu, Fangyou
AU - Pan, Xing
AU - Chen, Xi
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/12
Y1 - 2018/12
N2 - To overcome the performance limitation of traditional shortest path algorithms when processing large amount of calculation in large scale networks, this article proposes a novel shortest path algorithm based on community detection. In the proposed algorithm, community detection is utilized to integrate the necessary but tedious information in the network and reduce the scale of the network, which accelerates the calculation. Particularly, when processing multiple shortest path queries, the community information can be reused, which leads to considerable improvement of the efficiency. Based on the results in performance evaluation, it turns out that in middle (500 nodes) and large-scale (1500 or 5000 nodes) BA networks, our algorithm is more efficient than traditional Dijkstra's algorithm in both single query (5%- 138%) and multiple query (104%-3905%).
AB - To overcome the performance limitation of traditional shortest path algorithms when processing large amount of calculation in large scale networks, this article proposes a novel shortest path algorithm based on community detection. In the proposed algorithm, community detection is utilized to integrate the necessary but tedious information in the network and reduce the scale of the network, which accelerates the calculation. Particularly, when processing multiple shortest path queries, the community information can be reused, which leads to considerable improvement of the efficiency. Based on the results in performance evaluation, it turns out that in middle (500 nodes) and large-scale (1500 or 5000 nodes) BA networks, our algorithm is more efficient than traditional Dijkstra's algorithm in both single query (5%- 138%) and multiple query (104%-3905%).
KW - Algorithm design and analysis
KW - Complex networks
KW - Computational efficiency
KW - Network theory
KW - Shortest path problem
UR - https://www.scopus.com/pages/publications/85076379653
U2 - 10.1109/EECS.2018.00073
DO - 10.1109/EECS.2018.00073
M3 - 会议稿件
AN - SCOPUS:85076379653
T3 - Proceedings - 2018 2nd European Conference on Electrical Engineering and Computer Science, EECS 2018
SP - 361
EP - 365
BT - Proceedings - 2018 2nd European Conference on Electrical Engineering and Computer Science, EECS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2nd European Conference on Electrical Engineering and Computer Science, EECS 2018
Y2 - 20 December 2018 through 22 December 2018
ER -