An algorithm for discovering vital nodes in regional networks based on stable path analysis

Abstract

Abstract Vital node discovery is a hotspot in network topology research. The key is using the Internet’s routing characteristics to remove noisy paths and accurately describe the network topology. In this manuscript, a vital regional routing nodes discovery algorithm based on routing characteristics is proposed. We analyze the stability of multiple rounds of measurement results to overcome the single vantage point’s path deviation. The unstable paths are eliminated from the regional network which is constructed through probing for target area, and the pruned topology is more in line with real routing rules. Finally, we weight the edge based on the actual network’s routing characteristics and discover vital nodes in combination with the weighting degree. Unlike existing algorithms, the proposed algorithm reconstructs the network topology based on communication and transforms unweighted network connections into weighted connections. We can evaluate the node importance in a more realistic network structure. Experiments on the Internet measurement data (275 million probing results collected in 107 days) demonstrate that: the proposed algorithm outperforms four existing typical algorithms. Among 15 groups of comparison in 3 cities, our algorithm found more (or the same number) backbone nodes in 10 groups and found more (or the same number) national backbone nodes in 13 groups.