Ranking robustly

Is the ranking induced by PageRank robust with respect to factors that, intuitively, should have little weight? Motivated by a large and growing number of applications of PageRank as a ranking algorithm, we investigate this problem theoretically and experimentally along two complementary research lines. The first research line explores to what extent the PageRank-induced ranking of the nodes of a graph depends on an arbitrary, graph-independent, user-model parameter -- the damping factor. We prove that, on some graphs, the ranking depends totally on the damping factor and that, in these cases, sampling the rank of a node on any finite set of damping factors gives very little information about its overall stability. The novel tool of lineage analysis bypasses the problem and allows to check if the rank of a node is stable for all (even time-variant) damping factors. We introduce the notions of strong rank and weak rank, which measure the rank robustness of a graph's nodes, and derive two new ranking metrics that benchmark the performance of ranking algorithms with respect to different scenarios. Experimental results show that, in real-world graphs, ranking is relatively robust, and suggest ideal damping factors for PageRank in different application domains. The second research line investigates whether it is possible to compute the relative PageRank-induced ranking of a node visiting only a small nearby subgraph. We answer negatively: to provide a correct ranking any algorithm must visit a number of nodes that is proportional to the size of the graph, if deterministic, or to its square root, if randomized. These results hold even when ranking the top nodes in the graph, even when the gap between their PageRank scores is large. Indeed our experiments show that, in some real-world cases, any algorithm must visit large number of nodes, even when inferring ranking through efficient local approximations of the PageRank scores. Therefore, ranking seems definitely not robust with respect to the removal of nodes from the graph. In a nutshell, this work asks how much "information" a graph contains about the PageRank-induced importance of its nodes and whether this information is local or distributed -- aiming at a full understanding of the robustness of PageRank as a ranking algorithm. It turns out, that, in terms of variations of the damping factor and of variations of the link structure in "remote" areas of the graph, PageRank is not very robust -- neither in theory nor, in many cases, in practice.

Il ranking indotto da PageRank è robusto rispetto a fattori che, intuitivamente, dovrebbero avere poco peso? Motivati da un ampio e crescente numero di applicazioni di PageRank come algoritmo di ranking, investighiamo questo problema teoricamente e sperimentalmente lungo due linee di ricerca complementari. La prima linea di ricerca esplora quanto il ranking indotto da PageRank sui nodi di un grafo dipenda da un parametro del modello sottostante, arbitrario e indipendente dal grafo -- il damping factor. Mostriamo che, in alcuni grafi, il ranking dipende totalmente dal damping factor a che, in questi casi, campionare il rank di un nodo per qualsiasi insieme finito di damping factor dà pochissima informazione sulla sua stabilità complessiva. Il nuovo strumento della lineage analysis supera il problema e permette di verificare se il rank di un nodo è stabile per tutti i damping factor, anche tempo-varianti. Introduciamo le nozioni di strong rank e weak rank, che misurano la robustezza dei rank dei nodi di un grafo, e deriviamo due nuove metriche che misurano le prestazioni degli algoritmi di ranking rispetto a differenti scenari. I risultati sperimentali mostrano che, nei grafi reali, il ranking è relativamente robusto, e suggeriscono damping factor ideali per PageRank in diversi domini applicativi. La seconda linea di ricerca investiga se sia possibile calcolare il ranking relativo (indotto da PageRank) di un nodo visitando solo un piccolo sottografo circostante. Rispondiamo negativamente: per fornire un ranking corretto, ogni algoritmo deve visitare un numero di nodi che è proporzionale alla taglia del grafo, nel caso deterministico, e proporzionale alla sua radice quadrata, se randomizzato. Questi risultati valgono anche quando si fornisce il ranking dei nodi più importanti del grafo e la differenza tra i loro punteggi PageRank è ampia. In effetti i nostri esperimenti mostrano che, in alcuni grafi reali, ogni algoritmo deve visitare un grande numero di nodi, anche se utilizza approssimazioni efficienti del punteggio PageRank. Quindi, il ranking sembra essere non robusto rispetto alla rimozione di nodi dal grafo. In breve, questo lavoro si chiede quanta "informazione" contiene un grafo circa l'importanza (data da PageRank) dei suoi nodi e se questa informazione sia localizzata o distribuita -- mirando a una piena comprensione della robustezza di PageRank come algoritmo di ranking. Si scopre che, in termini di variazioni del damping factor e di variazione nella struttura in aree "remote" del grafo, PageRank non è molto robusto -- né in teoria né, in molti casi, in pratica.