Fast Estimation for Forest Matrix of Signed Graphs

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 \textsc{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, \textsc{FMDE} and \textsc{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 \url{https://github.com/HaoxinSun98/SignedForestDiagonal}.

Many real-world networks contain both friendly and unfriendly relationships, such as cooperation and competition in social networks. Understanding how information or opinions spread in such networks is important, but existing methods are often designed only for networks with positive relationships and become inefficient or inaccurate when negative relationships are present. This paper studies how to quickly estimate an important mathematical representation of these signed networks, which helps measure node importance and predict stable opinions in social systems. Instead of directly performing expensive matrix computations, we develop a new theory that connects this representation to special forest-like structures in the network. Based on this connection, we design fast sampling algorithms that estimate the needed quantities efficiently. Experiments on a wide range of real and synthetic networks show that the proposed methods are accurate, much faster than direct computation, and can scale to very large networks with more than twenty million nodes. This makes the approach useful for analyzing large-scale social and information networks involving both agreement and conflict.