Finding the Balance Rate of Uncertain Signed Graphs
It provides a practical method for quantifying balance in uncertain signed graphs, addressing a gap in network analysis for real-world applications.
The paper introduces a metric called balance rate for uncertain signed graphs, proves its computation is NP-hard, and proposes a Rao-Blackwellized spanning-tree estimator with near-linear time complexity per sample, enabling scalable balance analysis.
Signed graphs are widely used to analyze complex systems such as social, political, and biological networks. The notion of balance, a key concept of signed graphs, reflects the stability of relationships. While it has been extensively studied in deterministic graphs, real-world networks often exhibit uncertainty in their connections, which traditional approaches struggle to address. To bridge this gap, we introduce the concept of balance rate, a metric for quantifying the degree of balance in uncertain signed graphs, and prove that computing it exactly is NP-hard, motivating the need for efficient estimation methods. We propose a novel Rao-Blackwellized spanning-tree estimator that achieves near-linear time complexity per sample by leveraging graph decomposition and structural properties. We also construct asymptotically justified confidence intervals using the Delta method. Experiments on real-world datasets demonstrate the efficiency and effectiveness of our approach, enabling scalable balance analysis in uncertain signed graphs.