Absorbing random-walk (ARW) centrality
Absorbing random-walk (ARW) centrality
[2] measures the importance of nodes as
absorbing states
with respect to a set of query nodes \(Q \subseteq \mathcal{N}\). The goal is to select \(C \subseteq \mathcal{N}\) of size \(k\) that minimizes the expected number of steps for random walks starting from \(Q\) to reach any node in \(C\).
Let \(D \subseteq \mathcal{N}\) be candidate nodes, and \(s\colon Q \to [0,1]\) a probability distribution over \(Q\) (\(\sum_{q \in Q} s(q)=1\)). At each step, a random walk from a transient node \(i \in T = \mathcal{N} \setminus C\) either moves uniformly to a neighbor with probability \(1-α\) or restarts at a query node sampled from \(s\) with probability \(α\), where \(α \in [0,1]\). Nodes in \(C\) are absorbing: the walk terminates upon reaching them. For candidate set \(C \subseteq D\), let the transition matrix be
\[
P = \begin{pmatrix} P_{TT} & P_{TC} \\ 0 & I \end{pmatrix},
\]
with \(P_{TT}\) for transient-to-transient and \(P_{TC}\) for transient-to-absorbing transitions. The fundamental matrix is \(F = (I - P_{TT})^{-1}\), and the expected absorption times are
\[
L_C = \begin{pmatrix} F \\ 0 \end{pmatrix} \mathbf{1}_T.
\]
The ARW centrality of nodes in \(C\) is
\[
c_{ARW}(C) = s^\top L_C = \sum_{q \in Q} s(q) (L_C)_q.
\]
Selecting the optimal \(k\) nodes is NP-hard [2]. A greedy algorithm iteratively adds the node that maximally decreases \(c_{ARW}(C)\). This naturally favors diverse selections, as absorbing nodes placed in different graph regions intercept walks from multiple query nodes efficiently.