Pivotality of nodes in reachability problems using avoidance and transit hitting time metrics

Reachability is crucial to many network operations in various complex networks. More often than not, however, it is not sufficient simply to know whether a source node s can reach a target node t in the network. Additional information associated with reachability such as how long or how many possible ways node s may take to reach node t. In this paper we analyze another piece of important information associated with reachability - which we call pivotality. Pivotality captures how pivotal a role that a node k or a subset of nodes S may play in the reachability from node s to node t in a given network. We propose two important metrics, the avoidance and transit hitting times, which extend and generalize the classical notion of hitting times. We show these metrics can be computed from the fundamental matrices associated with the appropriately defined random walk transition probability matrices and prove that the classical hitting time from a source to a target can be decomposed into the avoidance and transit hitting times with respect to any third node. Through simulated and real-world network examples, we demonstrate that these metrics provide a powerful ranking tool for the nodes based on their pivotality in the reachability.