TY - JOUR

T1 - Ranking nodes in general networks

T2 - a Markov multi-chain approach

AU - Berkhout, Joost

AU - Heidergott, Bernd F.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Google’s PageRank

KW - Markov multi-chains

KW - Random surfer

KW - Ranking nodes in networks

UR - http://www.scopus.com/inward/record.url?scp=85019683099&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019683099&partnerID=8YFLogxK

U2 - 10.1007/s10626-017-0248-7

DO - 10.1007/s10626-017-0248-7

M3 - Article

AN - SCOPUS:85019683099

VL - 28

SP - 3

EP - 33

JO - Discrete Event Dynamic Systems

JF - Discrete Event Dynamic Systems

SN - 0924-6703

IS - 1

ER -