Fast Algorithms for Resistance Distances on Signed Graphs

The resistance distance is a fundamental metric in circuit networks, with broad applications across various domains. While signed graphs provide a more expressive framework for modeling real-world interactions, the presence of negative edges challenges conventional methods for computing resistance distances, leading to a lack of efficient algorithms. To address this challenge, an equivalent formulation of resistance distances for signed graphs is derived, establishing its physical interpretation as voltage differences in an equivalent circuit network. This formulation enables the development of two approximation algorithms: SolverRD, which employs a linear equation solver to achieve high accuracy, and RandomwalkRD, which simulates a random walk with a trap and enhances computational efficiency while maintaining relative accuracy. Extensive experiments on real-world networks containing more than ten millions of nodes validate the effectiveness and efficiency of the proposed algorithms, advancing the resistance distance computation for signed circuit networks. The proposed algorithms could find applications for detecting important nodes in large-scale complex networks.