Learn Before
Concept

PageRank-Style Propagation on Graphs

PageRank-style propagation is a family of graph scoring rules in which node importance is defined as the stationary distribution of a random walk on the graph that, at each step, either follows an outgoing edge with probability 1α1-\alpha or teleports to a seed distribution with probability α\alpha (the damping/restart term). The original PageRank (Brin & Page, 1998) uses a uniform teleport over all nodes, while personalized PageRank (Jeh & Widom, 2003) and topic-sensitive PageRank (Haveliwala, 2002) replace the teleport with a seed-specific distribution, so the stationary score concentrates near the seeds. Local/approximate personalized PageRank (Andersen, Chung & Lang, 2006) computes the same seed-localized stationary scores efficiently via push-style updates without touching the whole graph. The common structural feature across all variants is that a node's score is an aggregate over infinitely many walks weighted by damping, rather than a function of any single shortest or best path.

0

1

Updated 2026-05-18

Contributors are:

Who are from:

Tags

Science

Auditable Strict-Parity Evaluation of Prerequisite-Graph Retrieval for RAG under Leakage Controls