PageRank vs. Random Walk Decay Centrality

Prelegent(ci)

Tomasz Wąs

Afiliacja

Instytut Informatyki UW

Termin

12 listopada 2020 10:15

Pokój

p. 4050

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

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.

---