document: Efficient pagerank approximation via graph aggregation We present a framework for approximating random-walk based probability distributions over Web pages using graph aggregation . We ( 1 ) partition the Web 's graph into classes of quasi-equivalent vertices , ( 2 ) project the page-based random walk to be approximated onto those classes , and ( 3 ) compute the stationary probability distribution of the resulting class-based random walk . From this distribution we can quickly reconstruct a distribution on pages . Inparticular , our framework can approximate the well-known PageRank distribution by setting the classes according to the set of pages on each Web host . We experimented on a Web-graph containing over 1.4 billion pages , and were able to produce a ranking that has Spearman rank-order correlation of 0.95 with respect to PageRank . A simplistic implementation of our method required less than half the running time of a highly optimized implementation of PageRank , implying that larger speedup factors are probably possible .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O