Prelegent: Tomasz Wąs

PageRank is one of the most important measures of node importance. However, multiple methods of manipulating PageRank have been identified. Recently, Random Walk Decay centrality was introduced as a harder to manipulate alternative to PageRank. It has been shown that it retains a vast majority of properties of PageRank, but at the same time it does not depend on the links of the assessed node. To date, this new measure has been only studied theoretically. In this paper, we perform the first algorithmic and empirical analysis of Random Walk Decay centrality. We propose exact and approximation algorithms that enable us to compare PageRank and Random Walk Decay centrality on real networks. Our results allow for a better understanding of Random Walk Decay centrality, but also shed new light on the inner workings of PageRank.