Computing Absorbing-Frequency Centrality: Complexity, Estimators, and Scalable Algorithms for Stochastic Networks
In a stochastic network, where edges fail and weights may vary across realizations, the node of highest betweenness is itself random. Absorbing-frequency centrality (AFC) scores each node by how often it is reported as the node of highest betweenness: the reported betweenness maximizer traces an absorbing Markov chain, and AFC is the normalized expected pre-absorption occupancy. Computing it exactly is intractable: we prove that evaluating even a single transition probability of the AFC chain is #P-hard, by a reduction from two-terminal network reliability, and that the expected absorption…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.14743
curl -X POST /api/v1/records/arxiv/2605.14743/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.14743/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'