Ranking robustly

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.