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.
|Original language||English (US)|
|Title of host publication||WWW 2015 Companion - Proceedings of the 24th International Conference on World Wide Web|
|Publisher||Association for Computing Machinery, Inc|
|Number of pages||6|
|State||Published - May 18 2015|
|Event||24th International Conference on World Wide Web, WWW 2015 - Florence, Italy|
Duration: May 18 2015 → May 22 2015
|Name||WWW 2015 Companion - Proceedings of the 24th International Conference on World Wide Web|
|Other||24th International Conference on World Wide Web, WWW 2015|
|Period||5/18/15 → 5/22/15|
Bibliographical noteFunding Information:
This research was supported in part by DTRA grants HDTRA1-09-1-0050, HDTRA1-14-1-0040, DoD ARO MURI Award W911NF-12-1-0385, and NSF grants CNS-10171647 and CRI-1305237.
- Hitting time