PageRank Revisited: On the Relationship between Node Degrees and Node Significances in Different Applications

Random-walk based techniques, such as PageRank, encode the structure of the graph in the form of a transition matrix of a stochastic process from which significances of the graph nodes can be inferred. Recommendation systems leverage such node significance measures to rank the objects in the database. Context-aware recommendation techniques complement the data graph with additional data that provide the recommendation context. However, despite their wide-spread use in many graph-based knowledge discovery and recommendation applications, conventional PageRank-based measures have various shortcomings. As we experimentally show in this paper, one such shortcoming is that PageRank scores are tightly coupled with the degrees of the graph nodes, whereas in many applications the relationship between the significance of the node and its degree in the underlying network may not be as im- plied by PageRank-based measures. In fact, as we also show in the paper, in certain applications, the significance of the node may be negatively correlated with the node degree and in such applications a naive application of PageRank may return poor results. To address these challenges, in this paper, we propose degree decoupled PageRank (D2PR) techniques to improve the effectiveness of PageRank based knowledge discovery and recommendation systems. These suitably penalize or (if needed) boost the transition strength based on the degree of a given node to adapt the node significances based on the network and application characteristics.