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

Golshan Golnari, Yanhua Li, Zhi Li Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationWWW 2015 Companion - Proceedings of the 24th International Conference on World Wide Web
PublisherAssociation for Computing Machinery, Inc
Pages1073-1078
Number of pages6
ISBN (Electronic)9781450334730
DOIs
StatePublished - May 18 2015
Event24th International Conference on World Wide Web, WWW 2015 - Florence, Italy
Duration: May 18 2015May 22 2015

Publication series

NameWWW 2015 Companion - Proceedings of the 24th International Conference on World Wide Web

Other

Other24th International Conference on World Wide Web, WWW 2015
CountryItaly
CityFlorence
Period5/18/155/22/15

Bibliographical note

Funding 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.

Keywords

  • Hitting time
  • Pivotality
  • Reachability

Fingerprint Dive into the research topics of 'Pivotality of nodes in reachability problems using avoidance and transit hitting time metrics'. Together they form a unique fingerprint.

Cite this