Abstract: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 time and AFC scores inherit this hardness. We develop a matrix estimator that builds the kernel row-wise and solves one linear system, and a parallelizable episode estimator over absorption trajectories that is strongly consistent and asymptotically normal, with finite-sample guarantees tied to the empirical error decay. A computational study reports scalability on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert graphs, and a monitor placement experiment in which AFC's advantage over pooled counting generally grows with reliability heterogeneity.
From: Chrysafis Vogiatzis [view email]
[v1]
Thu, 14 May 2026 12:11:03 UTC (16,653 KB)
[v2]
Fri, 15 May 2026 19:00:27 UTC (16,653 KB)
[v3]
Tue, 16 Jun 2026 12:49:06 UTC (17,303 KB)
[v4]
Sun, 9 Aug 2026 19:43:49 UTC (3,841 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。