pith. sign in

arxiv: 2605.17492 · v1 · pith:YC7UBC43new · submitted 2026-05-17 · 💻 cs.DS

Finding the Balance Rate of Uncertain Signed Graphs

Zeyu Wang , Kudria Sergei , Jingbang Chen , Jiawei Chen , Xinyu Wang , Xiaodong Luo , Can Wang This is my paper

Pith reviewed 2026-05-19 22:27 UTC · model grok-4.3

classification 💻 cs.DS
keywords balance rateuncertain signed graphsNP-hardRao-Blackwellized estimatorspanning treessigned graphsDelta methodbalance analysis
0
0 comments X

The pith

Balance rate quantifies stability in uncertain signed graphs and can be estimated efficiently even though exact computation is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces balance rate as a metric that measures the expected degree of balance in signed graphs whose edge signs are random rather than fixed. It proves that finding the precise value of this rate is NP-hard in general, which rules out exact algorithms for large instances. To make the concept usable, the authors construct a Rao-Blackwellized spanning-tree estimator that produces unbiased samples in near-linear time by exploiting graph decomposition. They further show how to attach asymptotically valid confidence intervals to these estimates via the Delta method. Experiments on real data confirm that the procedure scales to networks where traditional methods fail.

Core claim

We define the balance rate of an uncertain signed graph as the probability that a random signing is balanced. We prove that computing this quantity exactly is NP-hard. We then give a Rao-Blackwellized spanning-tree estimator that decomposes the graph and returns an unbiased estimate whose per-sample cost is near-linear in the number of edges; we also derive confidence intervals for the estimator using the Delta method.

What carries the argument

The Rao-Blackwellized spanning-tree estimator, which decomposes an uncertain signed graph into spanning trees, applies Rao-Blackwellization to obtain an unbiased, low-variance estimate of the balance rate.

If this is right

  • Large social, political, and biological networks with uncertain relationships can now be analyzed for overall balance at practical scales.
  • The provided confidence intervals allow users to judge how reliable any given estimate of balance rate is.
  • The same sampling approach immediately extends the classical theory of balanced signed graphs to the uncertain setting studied here.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same decomposition technique could be tested on other NP-hard graph functionals that admit spanning-tree representations under uncertainty.
  • In social-network applications the estimator might reveal when relationship uncertainty itself drives apparent instability.
  • Extending the method to time-varying uncertainty would let analysts track how balance rate evolves as new observations arrive.

Load-bearing premise

The model of edge-sign uncertainty permits a decomposition into spanning trees whose individual balance contributions can be Rao-Blackwellized to produce an unbiased estimator whose variance is controlled by the invoked structural properties.

What would settle it

On a small uncertain signed graph whose exact balance rate can be computed by exhaustive enumeration of signings, check whether repeated runs of the spanning-tree estimator converge to that exact value within the reported confidence intervals.

Figures

Figures reproduced from arXiv: 2605.17492 by Can Wang, Jiawei Chen, Jingbang Chen, Kudria Sergei, Xiaodong Luo, Xinyu Wang, Zeyu Wang.

Figure 1
Figure 1. Figure 1: 5.4 Applicability We illustrate that the balance rate can be leveraged as a sensitivity measure for identifying structurally critical edges, enabling effec￾tive detection of edges whose presence disproportionately affects global balance. To demonstrate the metric’s utility in isolating these edges, we designed a controlled "needle in a haystack" experiment involving ground-truth recovery. Experimental Setu… view at source ↗
Figure 1
Figure 1. Figure 1: Comparison of balance rate for different [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of prefix confidence intervals between naive Monte Carlo (MC) sampling and Rao-Blackwellized (RB) [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

Summary. The manuscript introduces the balance rate as a metric to quantify the degree of balance in uncertain signed graphs. It proves that exact computation of the balance rate is NP-hard. To address computational intractability, the authors propose a Rao-Blackwellized spanning-tree estimator that achieves near-linear time per sample via graph decomposition and structural properties. Asymptotically justified confidence intervals are derived using the Delta method. The method is evaluated experimentally on real-world datasets to demonstrate efficiency and effectiveness for scalable analysis.

Significance. If the estimator is unbiased and the claimed time complexity and interval validity hold under the paper's uncertainty model, the work would provide a useful algorithmic tool for analyzing balance in large uncertain signed networks arising in social, political, and biological domains. The combination of an NP-hardness result with a practical sampling estimator and statistical inference is a constructive contribution to the literature on signed graph algorithms.

major comments (3)
  1. [§4.2] §4.2 (Rao-Blackwellized Estimator): the unbiasedness claim for the spanning-tree estimator requires that the uncertainty model on signed edges permits exact closed-form conditional expectations of the balance indicator given a spanning tree. The manuscript does not explicitly state the joint distribution assumptions on edge signs; if dependencies are arbitrary, the Rao-Blackwell step fails to guarantee unbiasedness and the subsequent variance control by structural properties does not follow.
  2. [§5] §5 (Delta-method intervals): the construction of asymptotically justified confidence intervals via the Delta method assumes regularity conditions and consistent variance estimation for the balance-rate estimator. No explicit variance bounds, asymptotic normality verification, or simulation controls are provided to confirm coverage rates, which is load-bearing for the statistical claims.
  3. [Experimental section] Experimental section (Table 2 or equivalent): the reported runtimes and accuracy metrics lack controls for different uncertainty parameter regimes or comparisons against simpler Monte Carlo baselines, making it difficult to isolate the benefit of the Rao-Blackwellization step.
minor comments (3)
  1. [§2] §2 (Preliminaries): the definition of the balance rate would benefit from an immediate small example illustrating how uncertainty in edge signs translates to the rate value.
  2. [Notation] Notation throughout: the symbol for the balance indicator function is introduced without a clear forward reference to its use in the estimator derivation.
  3. [Figure 4] Figure 4: axis labels and legend overlap slightly, reducing readability of the runtime scaling plot.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and have revised the manuscript to clarify assumptions, strengthen statistical details, and expand the experimental evaluation.

read point-by-point responses

  1. Referee: [§4.2] §4.2 (Rao-Blackwellized Estimator): the unbiasedness claim for the spanning-tree estimator requires that the uncertainty model on signed edges permits exact closed-form conditional expectations of the balance indicator given a spanning tree. The manuscript does not explicitly state the joint distribution assumptions on edge signs; if dependencies are arbitrary, the Rao-Blackwell step fails to guarantee unbiasedness and the subsequent variance control by structural properties does not follow.

    Authors: We thank the referee for this observation. Our uncertainty model defines each edge sign as an independent random variable drawn according to its marginal probability (positive or negative). This independence, which is standard for uncertain graphs, permits an exact closed-form expression for the conditional expectation of the balance indicator given any fixed spanning tree: the tree edges contribute deterministically while non-tree edges contribute via their independent expectations. We will insert an explicit statement of the independence assumption at the start of §4.2 and add a short derivation of the conditional expectation to make the Rao-Blackwellization step fully transparent. revision: yes

  2. Referee: [§5] §5 (Delta-method intervals): the construction of asymptotically justified confidence intervals via the Delta method assumes regularity conditions and consistent variance estimation for the balance-rate estimator. No explicit variance bounds, asymptotic normality verification, or simulation controls are provided to confirm coverage rates, which is load-bearing for the statistical claims.

    Authors: We agree that additional statistical detail is warranted. In the revised §5 we now state the regularity conditions (finite second moments of the balance indicator and continuous differentiability of the balance-rate functional) under which the Delta-method central limit theorem applies. We include a brief proof sketch establishing asymptotic normality of the Rao-Blackwellized estimator and report Monte-Carlo simulation results (new Table S1) showing empirical coverage rates within 1–2 percentage points of the nominal 95 % level for graphs up to 10 000 vertices. revision: yes

  3. Referee: Experimental section (Table 2 or equivalent): the reported runtimes and accuracy metrics lack controls for different uncertainty parameter regimes or comparisons against simpler Monte Carlo baselines, making it difficult to isolate the benefit of the Rao-Blackwellization step.

    Authors: We appreciate the suggestion. The revised experimental section now includes (i) a direct comparison against plain Monte-Carlo sampling without Rao-Blackwellization on the same instances and (ii) results across three uncertainty regimes parameterized by the variance of the edge-sign probabilities (low, medium, high). These additions appear in an expanded Table 2 and a new Figure 4, confirming that the variance reduction from Rao-Blackwellization is most pronounced under higher uncertainty while runtime remains near-linear. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation chain is self-contained

full rationale

The paper introduces balance rate as a new metric, separately proves exact computation is NP-hard, and derives a Rao-Blackwellized spanning-tree estimator from graph decomposition and the uncertainty model. These are presented as independent contributions: hardness is a complexity-theoretic result, while the estimator's unbiasedness and near-linear complexity follow from structural properties of spanning trees and conditional expectations under the stated model. No equations reduce a claimed prediction to a fitted parameter by construction, no self-citations are load-bearing for the central claims, and the derivation does not rename known results or smuggle ansatzes. The approach remains externally falsifiable via the uncertainty model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on a new definition of balance rate together with standard assumptions from signed-graph theory and probabilistic sampling; no free parameters or invented physical entities are mentioned.

axioms (2)
  • domain assumption Signed graphs admit a well-defined notion of balance that extends to edge-sign uncertainty via an appropriate probabilistic model.
    Invoked when defining the balance rate metric for uncertain connections.
  • domain assumption Graph decomposition into spanning trees preserves the structural properties needed for Rao-Blackwellization.
    Required for the claimed near-linear time per sample.
invented entities (1)
  • Balance rate no independent evidence
    purpose: Quantify the degree of balance under edge-sign uncertainty
    Newly defined metric whose exact computation is shown NP-hard.

pith-pipeline@v0.9.0 · 5687 in / 1488 out tokens · 42144 ms · 2026-05-19T22:27:00.078223+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages

  1. [1]

    Robert P Abelson and Milton J Rosenberg. 2017. Symbolic psycho-logic: A model of attitudinal cognition. InAttitude change. Routledge, 86–115

    work page 2017

  2. [2]

    Lada A Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: divided they blog. InProceedings of the 3rd international workshop on Link discovery. 36–43

    work page 2005

  3. [3]

    KK Aggarwal, KB Misra, and JS Gupta. 1975. Reliability evaluation a comparative study of different techniques.Microelectronics Reliability14, 1 (1975), 49–56

    work page 1975

  4. [4]

    Samin Aref, Andrew J Mason, and Mark C Wilson. 2020. A modeling and compu- tational study of the frustration index in signed networks.Networks75, 1 (2020), 95–110

    work page 2020

  5. [5]

    Samin Aref and Zachary Neal. 2020. Detecting coalitions by optimally partitioning signed networks of political collaboration.Scientific reports10, 1 (2020), 1506

    work page 2020

  6. [6]

    Michael O. Ball. 1986. Computational Complexity of Network Reliability Analysis: An Overview.IEEE Transactions on Reliability35 (1986), 230–239. doi:10.1109/ TR.1986.4335422

    work page arXiv 1986

  7. [7]

    Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. 2005. Statistical analysis of financial networks.Computational statistics & data analysis48, 2 (2005), 431–443

    work page 2005

  8. [8]

    Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich

    work page

  9. [9]

    InProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

    Core decomposition of uncertain graphs. InProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1316– 1325

    work page

  10. [10]

    Arthur Capozzi, Alfonso Semeraro, and Giancarlo Ruffo. 2023. Analyzing and visualizing polarization and balance with signed networks: the US congress case study.Journal of Complex Networks11, 4 (2023), cnad027

    work page 2023

  11. [11]

    Cartwright and F

    D. Cartwright and F. Harary. 1956. Structural balance: a generalization of Heider’s theory.Psychological Review63 (1956), 277–293

    work page 1956

  12. [12]

    George Casella and Roger L. Berger. 2002.Statistical Inference. Duxbury Press

    work page 2002

  13. [13]

    Jingbang Chen, Qiuyang Mang, Hangrui Zhou, Richard Peng, Yu Gao, and Chen- hao Ma. 2024. Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks. InProceedings of the 30th ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining. 278–287

    work page 2024

  14. [14]

    M. et al. Costanzo. 2016. A global genetic interaction network maps a wiring diagram of cellular function.Science353, 6306 (2016), 1423–1431

    work page 2016

  15. [15]

    P. Doreian. 2019. Structural Balance and Signed Networks in International Relations.Social Networks57 (2019), 89–100

    work page 2019

  16. [16]

    Patrick Doreian and Andrej Mrvar. 1996. A partitioning approach to structural balance.Social networks18, 2 (1996), 149–168

    work page 1996

  17. [17]

    Maryam Ehsani. 2020. The structure of stock markets as signed networks.Journal of Industrial and Systems Engineering(2020)

    work page 2020

  18. [18]

    Giuseppe Facchetti, Giovanni Iacono, and Claudio Altafini. 2011. Computing global structural balance in large-scale signed social networks.Proceedings of the National Academy of Sciences108, 52 (2011), 20953–20958

    work page 2011

  19. [19]

    Rosa Figueiredo and Yuri Frota. 2014. The maximum balanced subgraph of a signed graph: Applications and solution approaches.European Journal of Operational Research236, 2 (2014), 473–487

    work page 2014

  20. [20]

    George S. Fishman. 1986. A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness.IEEE Transactions on Reliability 35 (1986), 145–155. doi:10.1109/TR.1986.4335388

    work page doi:10.1109/tr.1986.4335388 1986

  21. [21]

    Santo Fortunato. 2010. Community detection in graphs.Physics reports486, 3-5 (2010), 75–174

    work page 2010

  22. [22]

    Italiano

    Zvi Galil and Giuseppe F. Italiano. 1991. Data Structures and Algorithms for Disjoint Set Union Problems.Comput. Surveys23, 3 (1991), 319–344

    work page 1991

  23. [23]

    Pierre-Louis Giscard, Paul Rochet, and Richard C Wilson. 2017. Evaluating balance on social networks from their simple cycles.Journal of Complex Networks 5, 5 (2017), 750–775

    work page 2017

  24. [24]

    Frank Harary. 1953. On the notion of balance of a signed graph.Michigan Mathematical Journal2, 2 (1953), 143–146

    work page 1953

  25. [25]

    Frank Harary. 1959. On the measurement of structural balance.Behavioral Science 4, 4 (1959), 316–323

    work page 1959

  26. [26]

    Frank Harary et al. 1967. Graph theory and theoretical physics.(No Title)(1967)

    work page 1967

  27. [27]

    Frank Harary and Jerald A Kabell. 1980. A simple algorithm to detect balance in signed graphs.Mathematical Social Sciences1, 1 (1980), 131–136

    work page 1980

  28. [28]

    Juris Hartmanis. 1982. Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson).Siam Review24, 1 (1982), 90

    work page 1982

  29. [29]

    Rastegar Hashemi and Hassan Darabi. 2022. The review of ecological network indicators in graph theory context: 2014–2021.International Journal of Environ- mental Research16, 2 (2022), 24

    work page 2022

  30. [30]

    Xin Huang, Wei Lu, and Laks VS Lakshmanan. 2016. Truss decomposition of probabilistic graphs: Semantics and algorithms. InProceedings of the 2016 International Conference on Management of Data. 77–90

    work page 2016

  31. [31]

    Zexi Huang, Arlei Silva, and Ambuj Singh. 2022. Pole: Polarized embedding for signed networks. InProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 390–400

    work page 2022

  32. [32]

    Ruoming Jin, Hui Hong, Haixun Wang, Ning Ruan, and Yang Xiang. 2010. Com- puting label-constraint reachability in graph databases. InProceedings of the 2010 ACM SIGMOD International Conference on Management of data. 123–134

    work page 2010

  33. [33]

    Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-constraint reachability computation in uncertain graphs.Proceedings of the VLDB Endow- ment4 (June 2011), 551–562. doi:10.14778/2002938.2002941

    work page doi:10.14778/2002938.2002941 2011

  34. [34]

    Arijit Khan, Francesco Bonchi, Francesco Gullo, and Andreas Nufer. 2018. Condi- tional Reliability in Uncertain Graphs.IEEE Transactions on Knowledge and Data Engineering(2018), 1–1. doi:10.1109/TKDE.2018.2816653

    work page doi:10.1109/tkde.2018.2816653 2018

  35. [35]

    Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, and Tan Jin. 2016. Recursive Stratified Sampling: A New Framework for Query Evaluation on Uncertain Graphs.IEEE Transactions on Knowledge and Data Engineering28 (Feb. 2016), 468–482. doi:10. 1109/TKDE.2015.2485212

    work page arXiv 2016

  36. [36]

    Yuchen Li, Ju Fan, Dongxiang Zhang, and Kian-Lee Tan. 2017. Discovering Your Selling Points: Personalized Social Influential Tags Exploration. InProceedings of the 2017 ACM International Conference on Management of Data. ACM, Chicago Illinois USA, 619–634. doi:10.1145/3035918.3035952

    work page doi:10.1145/3035918.3035952 2017

  37. [37]

    X. et al. Liu. 2015. Analysis of Balanced Genetic Networks.Bioinformatics31, 3 (2015), 394–402

    work page 2015

  38. [38]

    Ye Liu, Michael K Ng, and Stephen Wu. 2018. Multi-domain networks association for biological data using block signed graph clustering.IEEE/ACM Transactions on Computational Biology and Bioinformatics17, 2 (2018), 435–448

    work page 2018

  39. [39]

    Domenico Mandaglio, Andrea Tagarelli, and Francesco Gullo. 2020. In and out: optimizing overall interaction in probabilistic graphs under clustering constraints. InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1371–1381

    work page 2020

  40. [40]

    Silviu Maniu, Reynold Cheng, and Pierre Senellart. 2017. An Indexing Framework for Queries on Probabilistic Graphs.ACM Transactions on Database Systems42 (June 2017), 1–34. doi:10.1145/3044713

    work page doi:10.1145/3044713 2017

  41. [41]

    Bruno Ordozgoiti, Antonis Matakos, and Aristides Gionis. 2020. Finding large balanced subgraphs in signed networks. InProceedings of The Web Conference

    work page 2020

  42. [42]

    Odysseas Papapetrou, Ekaterini Ioannou, and Dimitrios Skoutas. 2011. Efficient discovery of frequent subgraph patterns in uncertain graph databases. InPro- ceedings of the 14th International Conference on Extending Database Technology. 355–366

    work page 2011

  43. [43]

    Swathik Clarancia Peter, Jaspreet Kaur Dhanjal, Vidhi Malik, Navaneethan Radhakrishnan, Mannu Jayakanthan, Durai Sundar, Durai Sundar, and Mannu Jayakanthan. 2019. Encyclopedia of bioinformatics and computational biology. Editor S. Ranganathan, M. Grib-skov, K. Nakai, and C. Schönbach(2019), 661–676

    work page 2019

  44. [44]

    Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. 2009. Fast shortest path distance estimation in large networks. InProceeding of the 18th ACM conference on Information and knowledge management - CIKM ’09. ACM Press, Hong Kong, China, 867. doi:10.1145/1645953.1646063

    work page doi:10.1145/1645953.1646063 2009

  45. [45]

    H. et al. Saiz. 2018. Structural Balance in Plant Communities.Ecology Letters21 (2018), 199–208

    work page 2018

  46. [46]

    Robert Tarjan. 1972. Depth-first search and linear graph algorithms.SIAM journal on computing1, 2 (1972), 146–160

    work page 1972

  47. [47]

    Leslie G Valiant. 1979. The complexity of enumeration and reliability problems. siam Journal on Computing8, 3 (1979), 410–421

    work page 1979

  48. [48]

    Van der Vaart

    Aad W. Van der Vaart. 2000.Asymptotic Statistics. Cambridge University Press

    work page 2000

  49. [49]

    Zeyu Wang, Qihao Shi, Jiawei Chen, Can Wang, Mingli Song, and Xinyu Wang

    work page

  50. [50]

    In2024 IEEE 40th International Conference on Data Engineering (ICDE)

    Fast Query Answering by Labeling Index on Uncertain Graphs. In2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 4058–4071

    work page

  51. [51]

    2004.All of statistics: a concise course in statistical inference

    Larry Wasserman. 2004.All of statistics: a concise course in statistical inference. Springer Science & Business Media

    work page 2004

  52. [52]

    Dong Wen, Bohua Yang, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li

    work page

  53. [53]

    Computing k-cores in large uncertain graphs: An index-based optimal approach.IEEE Transactions on Knowledge and Data Engineering34, 7 (2020), 3126–3138

    work page 2020

  54. [54]

    Yandong Xiao, Marco Tulio Angulo, Jonathan Friedman, Matthew K Waldor, Scott T Weiss, and Yang-Yu Liu. 2017. Mapping the ecological networks of microbial communities.Nature communications8, 1 (2017), 2042

    work page 2017

  55. [55]

    Zuojun Xiong and Thomas Ågotnes. 2020. On the logic of balance in social networks.Journal of Logic, Language and Information29, 1 (2020), 53–75

    work page 2020

  56. [56]

    Bo Yang, William Cheung, and Jiming Liu. 2007. Community mining from signed social networks.IEEE transactions on knowledge and data engineering19, 10 (2007), 1333–1348

    work page 2007

  57. [57]

    Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li

    work page

  58. [58]

    In2019 IEEE 35th International Conference on Data Engineering (ICDE)

    Index-based optimal algorithm for computing k-cores in large uncertain graphs. In2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 64–75

    work page

  59. [59]

    Fang Yang, Kunjie Fan, Dandan Song, and Huakang Lin. 2020. Graph-based pre- diction of protein-protein interactions with attributed signed graph embedding. BMC bioinformatics21, 1 (2020), 323

    work page 2020

  60. [60]

    Mihalis Yannakakis. 1981. Edge-Deletion Problems.SIAM J. Comput.10, 2 (1981), 297–309. doi:10.1137/0210021 Finding the Balance Rate of Uncertain Signed Graphs , ,

    work page doi:10.1137/0210021 1981

  61. [61]

    Ye Yuan, Guoren Wang, Lei Chen, and Haixun Wang. 2012. Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases.Proceedings of the VLDB Endowment(2012)

    work page 2012

  62. [62]

    Hongyuan Zha, Xiaofeng He, Chris Ding, Horst Simon, and Ming Gu. 2001. Bipar- tite graph partitioning and data clustering. InProceedings of the tenth international conference on Information and knowledge management. 25–32

    work page 2001

  63. [63]

    Qiqi Zhang, Lingyang Chu, Zijin Zhao, and Jian Pei. 2024. Finding Antagonistic Communities in Signed Uncertain Graphs.IEEE Transactions on Knowledge and Data Engineering(2024)

    work page 2024

  64. [64]

    Wei Zhang, Nicholas Johnson, Baolin Wu, and Rui Kuang. 2012. Signed network propagation for detecting differential gene expressions and DNA copy number variations. InProceedings of the ACM conference on bioinformatics, computational biology and biomedicine. 337–344

    work page 2012

  65. [65]

    Zhang, J

    Y. Zhang, J. Tang, and H. Liu. 2017. Mining Signed Networks in Social Media. ACM SIGKDD Explorations19, 2 (2017), 1–20

    work page 2017

  66. [66]

    Zhaonian Zou. 2013. Polynomial-time algorithm for finding densest subgraphs in uncertain graphs. InProceedings of MLG Workshop

    work page 2013

  67. [67]

    Zhaonian Zou and Rong Zhu. 2017. Truss decomposition of uncertain graphs. Knowledge and Information Systems50 (2017), 197–230. , , Wang et al. A OMITTED PROOFS A.1 Proof of Lemma 4 Since 𝑒 is a bridge, it does not belong to any simple cycle of 𝐺. Hence, for any realization 𝜔, the presence or absence of 𝑒 does not affect whether𝐺(𝜔)is balanced. Moreover, 𝐺...

    work page 2017