EPJ Data Sci. (2020) 9: 23
https://doi.org/10.1140/epjds/s13688-020-00240-z

Regular article

Efficient algorithm to compute Markov transitional probabilities for a desired PageRank

¹ Institute of Informatics, University of Szeged, Árpád tér 2., Szeged, Hungary
² SZTE-MTA Research Group on Artificial Intelligence, Tisza Lajos krt. 103., Szeged, Hungary

^* e-mail: berendg@inf.u-szeged.hu

Received: 22 July 2019
Accepted: 14 July 2020
Published online: 29 July 2020

Abstract

We propose an efficient algorithm to learn the transition probabilities of a Markov chain in a way that its weighted PageRank scores meet some predefined target values. Our algorithm does not require any additional information about the nodes and the edges in the form of features, i.e., it solely considers the network topology for calibrating the transition probabilities of the Markov chain for obtaining the desired PageRank scores. Our experiments reveal that we can reliably and efficiently approximate the probabilities of the transition matrix, resulting in the weighted PageRank scores of the nodes to closely match some target distribution. We demonstrate our findings on both quantitative and qualitative evaluations by reporting experimental results on web traffic (the English Wikipedia and a Hungarian news portal) and the bicycle sharing network of New York City.