Module forward_push 

Forward Push solver for Personalized PageRank (Andersen-Chung-Lang).

Computes approximate PPR from a single source vertex in O(1/epsilon) time, independent of graph size. The algorithm maintains two sparse vectors:

• estimate: accumulated PPR values (the output).
• residual: probability mass yet to be distributed.

At each step a vertex whose residual exceeds epsilon * degree(u) is popped from a work-queue and its mass is “pushed” to its neighbours.

References

Andersen, Chung, Lang. Local Graph Partitioning using PageRank Vectors. FOCS 2006.

Structs

ForwardPushSolver

Forward Push solver for Personalized PageRank.

Functions

forward_push_with_residuals

Compute the estimate and residual vectors simultaneously.