Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes <inline-formula><tex-math notation="LaTeX">$\boldsymbol{s}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">s</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq1-3376000.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\boldsymbol{t}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">t</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq2-3376000.gif"/></alternatives></inline-formula>, the PPR value <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\pi }_{s}(t)}$</tex-math><alternatives><mml:math><mml:mrow><mml:msub><mml:mi>π</mml:mi><mml:mi mathvariant="bold">s</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi mathvariant="bold">t</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="yang-ieq3-3376000.gif"/></alternatives></inline-formula> equals the probability that an <inline-formula><tex-math notation="LaTeX">$\boldsymbol{\alpha }$</tex-math><alternatives><mml:math><mml:mi>α</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq4-3376000.gif"/></alternatives></inline-formula>-discounted random walk from <inline-formula><tex-math notation="LaTeX">$\boldsymbol{s}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">s</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq5-3376000.gif"/></alternatives></inline-formula> terminates at <inline-formula><tex-math notation="LaTeX">$\boldsymbol{t}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">t</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq6-3376000.gif"/></alternatives></inline-formula> and reflects the importance between <inline-formula><tex-math notation="LaTeX">$\boldsymbol{s}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">s</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq7-3376000.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\boldsymbol{t}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">t</mml:mi></mml:math><inline-graphic xlink:href="yang-ieq8-3376000.gif"/></alternatives></inline-formula> in a bidirectional way. As a generalization of Google's celebrated PageRank centrality, PPR has been extensively studied and has found multifaceted applications in many fields, such as network analysis, graph mining, and graph machine learning. Despite numerous studies devoted to PPR over the decades, efficient computation of PPR remains a challenging problem, and there is a dearth of systematic summaries and comparisons of existing algorithms. In this paper, we recap several frequently used techniques for PPR computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective. We classify these approaches based on the types of queries they address and review their methodologies and contributions. We also discuss some representative algorithms for computing PPR on dynamic graphs and in parallel or distributed environments.
Paper
References (100)
Scroll for more · 38 remaining