Markov fundamental tensor and its applications to network analysis

Golshan Golnari, Zhi-Li Zhang, Daniel L Boley

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We first present a comprehensive review of various Markov metrics used in the literature and express them in a consistent framework. We then introduce the fundamental tensor – a generalization of the well-known fundamental matrix – and show that classical Markov metrics can be derived from it in a unified manner. We provide a collection of useful relations for Markov metrics that are useful and insightful for network studies. To demonstrate the usefulness and efficacy of the proposed fundamental tensor in network analysis, we present four important applications: 1) unification of network centrality measures, 2) characterization of (generalized) network articulation points, 3) identification of network's most influential nodes, and 4) fast computation of network reachability after failures.

Original languageEnglish (US)
Pages (from-to)126-158
Number of pages33
JournalLinear Algebra and Its Applications
StatePublished - Mar 1 2019

Bibliographical note

Funding Information:
The research was supported in part by US DoD DTRA grants HDTRA1-09-1-0050 and HDTRA1-14-1-0040 , and ARO MURI Award W911NF-12-1-0385 . We would also like to thank our colleagues, Amir Asiaei and Arindam Banerjee, who helped us with the results reported in Section 7 .

Publisher Copyright:
© 2018 Elsevier Inc.


  • Articulation points
  • Centrality measures
  • Fundamental tensor
  • Influence maximization
  • Markov chain
  • Network analysis
  • Network reachability
  • Random walk


Dive into the research topics of 'Markov fundamental tensor and its applications to network analysis'. Together they form a unique fingerprint.

Cite this