2024/07/16 by Lukas Berner, Berner, Lukas, Henning Meyerhenke +1 · 1 voice
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.2407.11521
openalex publication_date 2024/07/16 · arxiv published 2024/07/16 · arxiv updated 2024/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Assessing and improving the robustness of a graph G are critical steps in network design and analysis. To this end, we consider the optimisation problem of removing k edges from G such that the resulting graph has minimal robustness, simulating attacks or failures. In this paper, we propose total harmonic resistance as a new robustness measure for this purpose - and compare it to the recently proposed forest index [Zhu et al., IEEE Trans. Inf. Forensics and Security, 2023]. Both measures are related to the established total effective resistance measure, but their advantage is that they can handle disconnected graphs. This is also important for originally connected graphs due to the removal of the k edges. To compare our measure with the forest index, we first investigate exact solutions for small examples. The best k edges to select when optimizing for the forest index lie at the periphery. Our proposed measure, in turn, prioritizes more central edges, which should be beneficial for most applications. Furthermore, we adapt a generic greedy algorithm to our optimization problem with the total harmonic resistance. With this algorithm, we perform a case study on the Berlin road network and also apply the algorithm to established benchmark graphs. The results are similar as for the small example graphs above and indicate the higher suitability of the new measure.