Table of Content

Open Access iconOpen Access

ARTICLE

A Fast Method for Shortest-Path Cover Identification in Large Complex Networks

Qiang Wei1, 2, *, Guangmin Hu1, Chao Shen3, Yunfei Yin4, 5

1 School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu, 611731, China.
2 National Key Laboratory of Science and Technology on Blind Signal Processing, Chengdu, 610041, China.
3 MOE Key Lab for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, 710049, China.
4 The Electronic Engineering Department, Universidad de Sevilla, Seville, 41004, Spain.
5 School of Astronautics, Harbin Institute of Technology, Harbin, 150001, China.

* Corresponding Author: Qiang Wei. Email: email.

Computers, Materials & Continua 2020, 63(2), 705-724. https://doi.org/10.32604/cmc.2020.07467

Abstract

Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring. However, the existing methods are time-consuming for even moderate-scale networks. In this paper, we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries. The effectiveness of the proposed method is validated through synthetic and real-world networks. The experimental results show that our method is 105 times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.

Keywords


Cite This Article

APA Style
Wei, Q., Hu, G., Shen, C., Yin, Y. (2020). A fast method for shortest-path cover identification in large complex networks. Computers, Materials & Continua, 63(2), 705-724. https://doi.org/10.32604/cmc.2020.07467
Vancouver Style
Wei Q, Hu G, Shen C, Yin Y. A fast method for shortest-path cover identification in large complex networks. Comput Mater Contin. 2020;63(2):705-724 https://doi.org/10.32604/cmc.2020.07467
IEEE Style
Q. Wei, G. Hu, C. Shen, and Y. Yin "A Fast Method for Shortest-Path Cover Identification in Large Complex Networks," Comput. Mater. Contin., vol. 63, no. 2, pp. 705-724. 2020. https://doi.org/10.32604/cmc.2020.07467



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1691

    View

  • 1350

    Download

  • 0

    Like

Related articles

Share Link