Markov fundamental tensor and its applications to network analysis

Golshan Golnari, Zhi-Li Zhang, Daniel L Boley

Research output: Contribution to journalArticle

Abstract

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
Volume564
DOIs
StatePublished - Mar 1 2019

Keywords

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

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

  • Cite this