Optimizing network robustness via Krylov subspaces

2023/03/09 by Stefano Massei, Massei, Stefano, Francesco Tudisco +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.2303.04971

openalex publication_date 2023/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We consider the problem of attaining either the maximal increase or reduction of the robustness of a complex network by means of a bounded modification of a subset of the edge weights. We propose two novel strategies combining Krylov subspace approximations with a greedy scheme and an interior point method employing either the Hessian or its approximation computed via the limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm (L-BFGS). The paper discusses the computational and modeling aspects of our methodology and illustrates the various optimization problems on networks that can be addressed within the proposed framework. Finally, in the numerical experiments we compare the performances of our algorithms with state-of-the-art techniques on synthetic and real-world networks.

Cited by

• Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations
• Sensitivity of Perron and Fiedler eigenpairs to structural perturbations of a network

Related

• Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivity
• Non-Uniform Robust Network Design in Planar Graphs
• Improving Network Robustness through Edge Augmentation While Preserving\n Strong Structural Controllability
• Robustifying networks for flow problems against edge failure
• Minimal Construction of Graphs with Maximum Robustness