KDD Papers

FORA: Simple and Effective Approximate Single-Source Personalized PageRank

Sibo Wang (Nanyang Technological University);Renchi Yang (Nanyang Technological University);Xiaokui Xiao (Nanyang Technological University);Zhewei Wei (Renmin University of China);Yin Yang (Hamad Bin Khalifa University)


Given a graph G ,a source node s and a target node t, the Personalized PageRank (PPR) of t with respect to s is the probability that a random walk starting from s terminates at t . A single-source PPR (SSPPR) query enumerates all nodes in G , and returns the top-k nodes with the highest PPR values with respect to a given source node s . SSPPR has important applications in web search and social networks, e.g., in Twiter