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

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

Algorithm · Graph · Graph bandwidth · Greedy algorithm · Laplacian matrix · Line graph · Mathematical optimization · Voltage graph · Advanced Graph Neural Networks · Complex Network Analysis Techniques · Computer Science · Graph theory and applications · Mathematics · Artificial Intelligence · Theoretical Computer Science

• The Network Data Repository with Interactive Graph Analytics and Visualization

  Open Access•Ryan A Rossi, Ryan Rossi et al.•Proceedings of the AAAI…•2015

  Add to list

• NetworKit

  Open Access•Christian Staudt, Christian L Staudt et al.•Network Science•2016

  Add to list