Resistance Eccentricity in Graphs: Distribution, Computation and Optimization

We study resistance eccentricity, a fundamental metric in network science for measuring the structural significance of a node. For a node in a graph, the resistance eccentricity is its maximum resistance distance to all other nodes. Fast computation of resistance eccentricity for a given subset of nodes is essential for a wide range of applications. However, a naive computation, requiring the pseudoinverse of the graph Laplacian, takes cubic time and is thus infeasible for huge networks with millions of nodes. In this paper, we devise a near-linear time algorithm to approximate the resistance eccentricity for one or multiple given nodes, accompanied by a theoretically guaranteed error bound. Furthermore, we investigate the problem of minimizing the resistance eccentricity for a given node by adding$k$missing edges to the graph, for a budget$k$. We show that while the objective function is monotone, it does not possess the submodularity property, ruling out the classical hill-climbing algorithm with theoretical guarantees. Instead, we propose two fast heuristic algorithms to approximately solve this problem. Then, we conduct extensive experiments on different networks with sizes up to several million nodes, demonstrating the superiority of our algorithms in terms of efficiency and effectiveness.