Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push
Hao Wu, Junhao Gan, Zhewei Wei, Rui Zhang
Abstract
Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph G with n nodes and m edges; and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for answering two variants of SSPPR queries: (i) high-precision queries and (ii) approximate queries.
Topics & Concepts
PageRankComputer scienceGraphTheoretical computer scienceNode (physics)Expressive powerPower iterationAlgorithmIterative methodStructural engineeringEngineeringGraph Theory and AlgorithmsData Management and AlgorithmsComplex Network Analysis Techniques