Fast Algorithm for Top-k Personalized PageRank Queries with Layered Graphs

Abstract

In recent years, an efficient method of performing analyses and computations on graph networks, regarding recent and up-to-date data, has been needed due to continuous growth of datasets. Per- sonalized PageRank is one of the most well-known computation methods for graphs. Personalized PageRank computes the relative importance or relevance with respect to a set of given nodes, called start nodes or bookmark. However, the online computation of Personalized PageRank on a massive size of datasets is infeasible due to its huge computational cost. So many applications have considered the way of precomputing Personalized PageRank for all or some nodes, keeping them in a secondary storage, and reading the results on demand. This method, though, has two problems; it requires an enormous size of storages and it is difficult to adopt up-to-date data to affect the results. For applications that cope with frequent updates to data such as search logs or social networks, the precomputation is not a suitable method. In this paper, we suggest a novel algorithm, ProbScoring, an approximate method of finding the top-k nodes at query time, that leverages the advantages of layered graphs. ProbScoring is far from those issues, and it is empirically verified that ProbScoring is a fast and accurate method.