Computing Absorbing-Frequency Centrality: Complexity, Estimators, and Scalable Algorithms for Stochastic Networks

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.