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.