Fast and Exact Top-K Algorithm for PageRank
Abstract
To obtain high PageRank score nodes, the original approach iteratively computes the Page-Rank score of each node until convergence by using the whole graph. If the graph is large, this approach is infeasible due to its high computational cost. The goal of this study is to find top-k Page\-Rank score nodes efficiently for a given graph without sacrificing accuracy. Our solution, F-Rank, is based on two ideas: (1) It iteratively estimates lower/upper bounds of Page\-Rank scores, and (2) It constructs subgraphs in each iteration by pruning unnecessary nodes and edges to identify top-k nodes. Our theoretical analysis shows that F-Rank guarantees result exactness. Experiments show that F-Rank finds top-k nodes much faster than the original approach.
Cite
Text
Fujiwara et al. "Fast and Exact Top-K Algorithm for PageRank." AAAI Conference on Artificial Intelligence, 2013. doi:10.1609/AAAI.V27I1.8454Markdown
[Fujiwara et al. "Fast and Exact Top-K Algorithm for PageRank." AAAI Conference on Artificial Intelligence, 2013.](https://mlanthology.org/aaai/2013/fujiwara2013aaai-fast/) doi:10.1609/AAAI.V27I1.8454BibTeX
@inproceedings{fujiwara2013aaai-fast,
title = {{Fast and Exact Top-K Algorithm for PageRank}},
author = {Fujiwara, Yasuhiro and Nakatsuji, Makoto and Shiokawa, Hiroaki and Mishima, Takeshi and Onizuka, Makoto},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2013},
pages = {1106-1112},
doi = {10.1609/AAAI.V27I1.8454},
url = {https://mlanthology.org/aaai/2013/fujiwara2013aaai-fast/}
}