Considerable attention has been made for processing graph data in recent years. Efficient method on how to compute node proximity is one of the most challenging problems for many applications such as recommendation systems and social networks. Regarding large-scale, mutable datasets and user queries, top-k query processing gains much interest. This paper presents a novel method to find top-k answers in node proximity search based on the well-known measure, Personalized PageRank (PPR). First, we introduce Distribution State Transition Graph (DSTG) to depict iterative steps of solving the PPR equation. Second we propose a weight distribution model of DSTG to capture the states of intermediate PPR scores and their distribution. Using DSTG, we can selectively follow and compare the multiple random paths with different lengths to find the most promising nodes. Moreover, we prove the results of our method are equivalent to the PPR results. The comparative performance studies using two real data sets clearly show that our method is practical and accurate.
展开▼
