Analysis of Markov influence graphs

Research output: Contribution to JournalArticleAcademicpeer-review

485 Downloads (Pure)


The research presented in this paper is motivated by the growing interest in the analysis of networks found in the World Wide Web and of social networks. In this paper, we elaborate on the Kemeny constant as a measure of connectivity of the weighted graph associated with a Markov chain. For finite Markov chains, the Kemeny constant can be computed by means of simple algebra via the deviation matrix and the ergodic projector of the chain. Using this fact, we introduce a new decomposition algorithm for Markov chains that splits the graph the Markov chain is defined on into subgraphs, such that the connectivity of the chain measured by the Kemeny constant is maximally decreased. We discuss applications of our decomposition algorithm to influence ranking in social networks, decomposition of a social network into subnetworks, identification of nearly decomposable chains, and cluster analysis.

Original languageEnglish
Pages (from-to)892-904
Number of pages13
JournalOperations Research
Issue number3
Early online date3 Apr 2019
Publication statusPublished - May 2019


  • Deviation matrix
  • Kemeny decomposition algorithm
  • Markov influence graphs
  • Markov multichains
  • Nearly decomposable Markov chains
  • Social networks


Dive into the research topics of 'Analysis of Markov influence graphs'. Together they form a unique fingerprint.

Cite this