Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges

Abstract

The Kirchhoff index, which is the sum of the resistance distance between every pair of nodes in a network, is a key metric for gauging network performance, where lower values signify enhanced performance. In this paper, we study the problem of minimizing the Kirchhoff index by adding edges. We first provide a greedy algorithm for solving this problem and give an analysis of its quality based on the bounds of the submodularity ratio and the curvature. Then, we introduce a gradient-based greedy algorithm as a new paradigm to solve this problem. To accelerate the computation cost, we leverage geometric properties, convex hull approximation, and approximation of the projected coordinate of each point. To further improve this algorithm, we use pre-pruning and fast update techniques, making it particularly suitable for large networks. Our proposed algorithms have nearly-linear time complexity. We provide extensive experiments on ten real networks to evaluate the quality of our algorithms. The results demonstrate that our proposed algorithms outperform the state-of-the-art methods in terms of efficiency and effectiveness. Moreover, our algorithms are scalable to large graphs with over 5 million nodes and 12 million edges.

Accepted by IEEE Transactions on Knowledge and Data Engineering

References in corpus (9)

• Graph Vulnerability and Robustness: A Survey
• The Role of Kemeny's Constant in Properties of Markov Chains
• Current Flow Group Closeness Centrality for Complex Networks
• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
• Efficient Estimation of Pairwise Effective Resistance
• Diameter Minimization by Shortcutting with Degree Constraints
• Minimizing the effective graph resistance by adding links is NP-hard
• Fast Computation of Kemeny's Constant for Directed Graphs