Pith Number

pith:YC7UBC43

pith:2026:YC7UBC43HJQ27BDAOS3F7MPFIV

not attested not anchored not stored refs resolved

Finding the Balance Rate of Uncertain Signed Graphs

Can Wang, Jiawei Chen, Jingbang Chen, Kudria Sergei, Xiaodong Luo, Xinyu Wang, Zeyu Wang

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

arxiv:2605.17492 v1 · 2026-05-17 · cs.DS

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{YC7UBC43HJQ27BDAOS3F7MPFIV}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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... 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.

C2weakest assumption

The uncertainty model for signed edges permits a graph decomposition into spanning trees whose balance contributions can be Rao-Blackwellized to yield an unbiased estimator whose variance is controlled by the structural properties invoked in the proof.

C3one line summary

Balance rate quantifies stability in uncertain signed graphs; exact computation is NP-hard but a Rao-Blackwellized spanning-tree estimator achieves near-linear time per sample with Delta-method intervals.

References

67 extracted · 67 resolved · 0 Pith anchors

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

[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 2005

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

[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 2020

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

Receipt and verification

First computed	2026-05-20T00:04:42.011921Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

c0bf408b9b3a61af846074b65fb1e5455fd88fcbf196f5331a3c2a794f0ede41

Aliases

arxiv: 2605.17492 · arxiv_version: 2605.17492v1 · doi: 10.48550/arxiv.2605.17492 · pith_short_12: YC7UBC43HJQ2 · pith_short_16: YC7UBC43HJQ27BDA · pith_short_8: YC7UBC43

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/YC7UBC43HJQ27BDAOS3F7MPFIV \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: c0bf408b9b3a61af846074b65fb1e5455fd88fcbf196f5331a3c2a794f0ede41

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "1580b882ed249cd76abaf93e187bad3ae08a8abddb6c4fc8db1a2c6b35f5d9a8",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-17T15:01:11Z",
    "title_canon_sha256": "e8406c219b8da20c9190a2283e6cb91a9dc4afc9d533b91c77fa35ef9ae4360d"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.17492",
    "kind": "arxiv",
    "version": 1
  }
}