Detection of Critical Links for Improving Network Resilience

Identifying and eliminating critical links in multi-hop networks is essential for enhancing overall network resilience. In this study, we propose a novel algorithm to detect links that significantly impact the pairwise connectivity of multi-hop networks. We formulate the critical link detection problem as minimizing pairwise connectivity subject to a total edge weight constraint c. The proposed method first computes the maximum flow between neighboring nodes to evaluate strong connections, and then progressively contracts these nodes to expose weaker connections. Throughout this iterative process, the algorithm records previously identified flows to minimize redundant flow computations. At each step, it also keeps track of the cut sets that reduce the network’s pairwise connectivity. Ultimately, it selects the subset of these cut sets whose removal minimizes pairwise connectivity while satisfying the total weight constraint c. This approach consistently identifies fewer yet more impactful critical edges than traditional Min-Cut or Greedy strategies. We evaluate the performance of our method against existing algorithms across various network sizes and node degrees. Experimental results show that the proposed method consistently discovers more influential edges and achieves a 34–38% reduction in pairwise connectivity, outperforming Greedy (22–24%), Min-Cut (24–32%), and Degree-based (12–19%) methods.