A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification

摘要

We give an improved algorithm for computing personalized PageRank vectors with tight error bounds which can be as small as Ω (n~p) for any fixed positive integer p. The improved PageRank algorithm is crucial for computing a quantitative ranking of edges in a given graph. We will use the edge ranking to examine two interrelated problems - graph sparsification and graph partitioning. We can combine the graph sparsification and the partitioning algorithms using PageRank vectors to derive an improved partitioning algorithm.