Deciding which kind of visit accumulates high-quality pages more quickly is one of the most often debated issue in the design of web crawlers. It is known that breadth-first visits work well, as they tend to discover pages with high PageRank early on in the crawl. Indeed, this visit order is much better than depth first, which is in turn even worse than a random visit; nevertheless, breadth-first can be superseded using an omniscient visit that chooses, at every step, the node of highest PageRank in the frontier. This paper discusses a related, and previously overlooked, measure of effectivity for crawl strategies: whether the graph obtained after a partial visit is in some sense representative of the underlying web graph as far as the computation of PageRank is concerned. More precisely, we are interested in determining how rapidly the computation of PageRank over the visited subgraph yields relative ranks that agree with the ones the nodes have in the complete graph; ranks are compared using Kendalls . We describe a number of large-scale experiments that show the following paradoxical effect: visits that gather PageRank more quickly (e.g., highest-quality-first) are also those that tend to miscalculate PageRank. Finally, we perform the same kind of experimental analysis on some synthetic random graphs, generated using well-known web-graph models: the results are almost opposite to those obtained on real web graphs.
Do your worst to make the best: Paradoxical effects in PageRank incremental computations / M. Santini, P. Boldi, S. Vigna - In: Algorithms and Models for theWeb-Graph : Third InternationalWorkshop,WAW 2004, Rome, Italy, October 16, 2004 : Proceeedings / [a cura di] S. Leonardi. - Berlin : Springer, 2004. - ISBN 9783540234272. - pp. 168-180 (( Intervento presentato al 3. convegno International Workshop on Algorithms and Models for the Web-Graph tenutosi a Rome, Italy nel 2004.
|Titolo:||Do your worst to make the best: Paradoxical effects in PageRank incremental computations|
SANTINI, MASSIMO (Primo)
BOLDI, PAOLO (Secondo)
VIGNA, SEBASTIANO (Ultimo)
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/b101552|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|