We consider the problem of approximating the PageRank of a target node using only local information provided by a link server. We prove that local approximation of PageRank is feasible if and only if the graph has low in-degree and admits fast PageRank convergence. While natural graphs, such as the web graph, are abundant with high in-degree nodes, making local PageRank approximation too costly, we show that  reverse  natural graphs tend to have low indegree while maintaining fast PageRank convergence. It follows that calculating  Reverse PageRank  locally is frequently more feasible than computing PageRank locally. Finally, we demonstrate the usefulness of Reverse PageRank in five different applications.
['Ziv Bar-Yossef', 'Li-Tal Mashiach']
Local approximation of PageRank and reverse PageRank