To what extent can changes in PageRank's damping factor affect node ranking? We prove that, at least on some graphs, the top k nodes assume all possible k! orderings as the damping factor varies, even if it varies within an arbitrarily small interval (e.g. [0.84999, 0.85001]). Thus, the rank of a node for a given (finite set of discrete) damping factor(s) provides very little information about the rank of that node as the damping factor varies over a continuous interval. We bypass this problem introducing lineage analysis and proving that there is a simple condition, with a "natural" interpretation independent of PageRank, that allows one to verify "in one shot" if a node outperforms another simultaneously for all damping factors and all damping variables (informally, time variant damping factors). The novel notions of strong rank and weak rank of a node provide a measure of the fuzziness of the rank of that node, of the objective orderability of a graph's nodes, and of the quality of results returned by different ranking algorithms based on the random surfer model. We deploy our analytical tools on a 41M node snapshot of the .it Web domain and on a 0.7M node snapshot of the CiteSeer citation graph. Among other findings, we show that rank is indeed relatively stable in both graphs; that "classic" PageRank (d∈=∈0.85) marginally outperforms Weighted In-degree (d→0), mainly due to its ability to ferret out "niche" items; and that, for both the Web and CiteSeer, the ideal damping factor appears to be 0.8∈-∈0.9 to obtain those items of high importance to at least one (model of randomly surfing) user, but only 0.5∈-∈0.6 to obtain those items important to every (model of randomly surfing) user.

Choose the damping, choose the ranking? / M. Bressan, E. Peserico (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Algorithms and models for the web-graph / [a cura di] K. Avrachenkov, D. Donato, N. Litvak. - [s.l] : Springer, 2009. - ISBN 978-3-540-95994-6. - pp. 76-89 (( Intervento presentato al 6. convegno WAW tenutosi a Barcelona nel 2009 [10.1007/978-3-540-95995-3_7].

Choose the damping, choose the ranking?

M. Bressan;
2009

Abstract

To what extent can changes in PageRank's damping factor affect node ranking? We prove that, at least on some graphs, the top k nodes assume all possible k! orderings as the damping factor varies, even if it varies within an arbitrarily small interval (e.g. [0.84999, 0.85001]). Thus, the rank of a node for a given (finite set of discrete) damping factor(s) provides very little information about the rank of that node as the damping factor varies over a continuous interval. We bypass this problem introducing lineage analysis and proving that there is a simple condition, with a "natural" interpretation independent of PageRank, that allows one to verify "in one shot" if a node outperforms another simultaneously for all damping factors and all damping variables (informally, time variant damping factors). The novel notions of strong rank and weak rank of a node provide a measure of the fuzziness of the rank of that node, of the objective orderability of a graph's nodes, and of the quality of results returned by different ranking algorithms based on the random surfer model. We deploy our analytical tools on a 41M node snapshot of the .it Web domain and on a 0.7M node snapshot of the CiteSeer citation graph. Among other findings, we show that rank is indeed relatively stable in both graphs; that "classic" PageRank (d∈=∈0.85) marginally outperforms Weighted In-degree (d→0), mainly due to its ability to ferret out "niche" items; and that, for both the Web and CiteSeer, the ideal damping factor appears to be 0.8∈-∈0.9 to obtain those items of high importance to at least one (model of randomly surfing) user, but only 0.5∈-∈0.6 to obtain those items important to every (model of randomly surfing) user.
Ranking Algorithm; Score Vector; Outgoing Link; Random Jump; Continuous Interval
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Bressan2009WAW.pdf

solo utenti autorizzati

Tipologia: Publisher's version/PDF
Dimensione 317.3 kB
Formato Adobe PDF
317.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/922278
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact