Fast Estimation for Forest Matrix of Signed Graphs
This work provides the first efficient estimation method for the forest matrix of signed graphs, addressing a gap in existing algorithms that were mainly designed for unsigned graphs.
The paper tackles the problem of efficiently estimating the forest matrix of signed graphs, which is important for network science and social opinion dynamics. The proposed algorithms achieve high estimation accuracy and scale to graphs with over twenty million nodes, with time complexity O(ln) for diagonal estimation.
The forest matrix of a signed graph plays an important role in network science and social opinion dynamics, yet existing algorithms are mainly designed for unsigned graphs and are difficult to extend to signed graphs. In this paper, we study the problem of efficiently estimating the forest matrix of signed graphs with n nodes and introduce the signed forest matrix theorem, which establishes the relationship between generalized spanning converging forests and the forest matrix. Based on this result, we propose a novel algorithm GSCF, built on a variant of loop-erased random walks, to generate generalized spanning converging forests in expected O(n) time. We further develop two sampling algorithms, FMDE and FMDE+, for estimating the diagonal of the forest matrix, both with time complexity O(ln), where l is the number of samples. Extensive experiments on various signed graphs show that our methods achieve high estimation accuracy, significantly improve computational efficiency, and scale to graphs with over twenty million nodes. Our source code is publicly available on https://github.com/HaoxinSun98/SignedForestDiagonal.