TY - JOUR
T1 - Ranking nodes in general networks
T2 - a Markov multi-chain approach
AU - Berkhout, Joost
AU - Heidergott, Bernd F.
PY - 2018/3
Y1 - 2018/3
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
SN - 0924-6703
VL - 28
SP - 3
EP - 33
JO - Discrete Event Dynamic Systems
JF - Discrete Event Dynamic Systems
IS - 1
ER -