Optimizing network resilience under budget limits with graph upgrades
Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization
Social and Information Networks
Summary
Networks like power grids or communication systems need to stay strong even if some parts fail. The authors study how to add new connections to a network to make it more robust using a mathematical measure called the Kirchhoff index, which reflects overall connectivity. They develop ways to choose which links to add and how strongly to connect them within a limited budget. Their methods combine complex optimization techniques with heuristics to find good network designs efficiently, and they test these methods on simulated and real-world networks.
What this means in practice
- •For infrastructure network planners: Design network upgrades that optimally add new links under limited budgets to enhance overall system robustness.
- •For telecommunications engineers: Plan cost-effective link installations in communication networks to reduce global resistance and improve connectivity reliability.
Authors
Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen
Abstract
Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.