Greedy optimization of resistance-based graph robustness with global and local edge insertions

Maria Predari, Lukas Berner, Robert Kooij*, Henning Meyerhenke

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Downloads (Pure)

Abstract

The total effective resistance, also called the Kirchhoff index, provides a robustness measure for a graph G. We consider two optimization problems of adding k new edges to G such that the resulting graph has minimal total effective resistance (i.e., is most robust)—one where the new edges can be anywhere in the graph and one where the new edges need to be incident to a specified focus node. The total effective resistance and effective resistances between nodes can be computed using the pseudoinverse of the graph Laplacian. The pseudoinverse may be computed explicitly via pseudoinversion, yet this takes cubic time in practice and quadratic space. We instead exploit combinatorial and algebraic connections to speed up gain computations in an established generic greedy heuristic. Moreover, we leverage existing randomized techniques to boost the performance of our approaches by introducing a sub-sampling step. Our different graph- and matrix-based approaches are indeed significantly faster than the state-of-the-art greedy algorithm, while their quality remains reasonably high and is often quite close. Our experiments show that we can now process larger graphs for which the application of the state-of-the-art greedy approach was impractical before.

Original languageEnglish
Article number130
Number of pages20
JournalSocial Network Analysis and Mining
Volume13
Issue number1
DOIs
Publication statusPublished - 2023

Keywords

  • Effective resistance
  • Graph robustness
  • Kirchhoff index
  • Laplacian pseudoinverse
  • Optimization problem

Fingerprint

Dive into the research topics of 'Greedy optimization of resistance-based graph robustness with global and local edge insertions'. Together they form a unique fingerprint.

Cite this