{"id":"arxiv/2605.14743","url":"https://arxiv.org/abs/2605.14743","tags":["cs.SI","math.OC"],"score":0,"title":"Computing Absorbing-Frequency Centrality: Complexity, Estimators, and Scalable Algorithms for Stochastic Networks","domain":"cs.SI","source":"arxiv","authors":["Wencheng Bao","Eleftheria Kontou","Chrysafis Vogiatzis"],"reviews":0,"subject":"cs.SI","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-14","reactions":{}}