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

Abstract

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
JournalDiscrete Event Dynamic Systems
Volume28
Issue number1
DOIs
Publication statusPublished - 2018

    Fingerprint

Keywords

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

Cite this