\input zb-basic
\input zb-ioport
\iteman{io-port 05505866}
\itemau{Bressan, Marco; Peserico, Enoch}
\itemti{Choose the damping, choose the ranking?}
\itemso{Avrachenkov, Konstantin (ed.) et al., Algorithms and models for the web-graph. 6th international workshop, WAW 2009, Barcelona, Spain, February 12--13, 2009. Proceedings. Berlin: Springer (ISBN 978-3-540-95994-6/pbk). Lecture Notes in Computer Science 5427, 76-89 (2009).}
\itemab
Summary: 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\rightarrow 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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-95995-3\_7}
\end