PageRank revisited: On the relationship between node degrees and node significances in different applications?

Jung Hyun Kim, Kasim Candan, Maria Luisa Sapino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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 implied 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.

Original languageEnglish (US)
Title of host publicationCEUR Workshop Proceedings
StatePublished - 2016
EventWorkshops of the EDBT/ICDT 2016 Joint Conference, EDBT/ICDT 2016 - Bordeaux, France
Duration: Mar 15 2016 → …


OtherWorkshops of the EDBT/ICDT 2016 Joint Conference, EDBT/ICDT 2016
Period3/15/16 → …

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'PageRank revisited: On the relationship between node degrees and node significances in different applications?'. Together they form a unique fingerprint.

Cite this