Ranking nodes in general networks: a Markov multi-chain approach

Joost Berkhout*, Bernd F. Heidergott

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

70 Downloads (Pure)


The basis of Google’s acclaimed PageRank is an artificial mixing of the Markov chain representing the connectivity structure of the network under study with a maximally connected network where every node is connected to every other node. The rate with which the original network is mixed with the strongly connected one is called damping factor. The choice of the damping factor can influence the ranking of the nodes. As we show in this paper, the ranks of transient nodes, i.e., nodes not belonging to a strongly connected component without outgoing links in the original network, tend to zero as the damping factor increases. In this paper we develop a new methodology for obtaining a meaningful ranking of nodes without having to resort to mixing the network with an artificial one. Our new ranking relies on an adjusted definition of the ergodic projector of the Markov chain representing the original network. We will show how the new ergodic projector leads to a more structural way of ranking (transient) nodes. Numerical examples are provided to illustrate the impact of this new ranking approach.

Original languageEnglish
Pages (from-to)3-33
Number of pages31
JournalDiscrete Event Dynamic Systems
Issue number1
Early online date27 May 2017
Publication statusPublished - Mar 2018


  • Google’s PageRank
  • Markov multi-chains
  • Random surfer
  • Ranking nodes in networks


Dive into the research topics of 'Ranking nodes in general networks: a Markov multi-chain approach'. Together they form a unique fingerprint.

Cite this