On Searching Multiple Disjoint Shortest Paths in Scale-Free Networks With Hyperbolic Geometry

Qiang Wang, Hao Jiang, Ying Jiang, Shuwen Yi, Lixia Li, Cong-Cong Xing, Jun HuangIEEE Trans. Network Science & Engineering 2022 · OpenReview

Abstract

Intensive research efforts have been devoted to the study of multiple disjoint shortest paths (MDSP) in complex networks. Most existing studies on this subject, unfortunately, either require global topology information about the network to find multiple shortest paths, or merely aim at finding a single unconstrained shortest path, leaving the (constrained) MDSP on local topology much less-investigated. In this paper, we model and analyze the problem of MDSP per hyperbolic random graphs. We find that the locations of MDSP have a high probability to be close to the corresponding hyperbolic geodesics. On the basis of this observation, we identify the network navigation skeleton for the source-destination pair, and subsequently devise an algorithm for searching MDSP on such a skeleton (local topology information) in a hyperbolic space. Our experiments on both synthetic and real-world networks demonstrate that the proposed algorithm not only guarantees the success of MDSP searching, but also achieves significant gains in terms of running time.
BibTeX
@article{wang2022searching,
  author = {Qiang Wang and Hao Jiang and Ying Jiang and Shuwen Yi and Lixia Li and Cong-Cong Xing and Jun Huang},
  title = {{On Searching Multiple Disjoint Shortest Paths in Scale-Free Networks With Hyperbolic Geometry}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2022},
  url = {https://openreview.net/forum?id=QB3L9nCHjF},
}

Loading related content...

Figure