Finding the Balance Rate of Uncertain Signed Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911692048302080 |
|---|---|
| author | Wang, Zeyu Sergei, Kudria Chen, Jingbang Chen, Jiawei Wang, Xinyu Luo, Xiaodong Wang, Can |
| author_facet | Wang, Zeyu Sergei, Kudria Chen, Jingbang Chen, Jiawei Wang, Xinyu Luo, Xiaodong Wang, Can |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17492 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finding the Balance Rate of Uncertain Signed Graphs Wang, Zeyu Sergei, Kudria Chen, Jingbang Chen, Jiawei Wang, Xinyu Luo, Xiaodong Wang, Can Data Structures and Algorithms 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. |
| title | Finding the Balance Rate of Uncertain Signed Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.17492 |