Personalizes the PageRank computation per user by biasing the random-walk teleportation vector toward documents the user has visited, producing per-user authority scores rather than a single global ranking.
Patent Overview
- Inventor
- Prabhakar Raghavan
- Assignee
- Excalibur IP, LLC
- Filed
- 2006-03-22
- Granted
- 2009-11-24
- Application Number
- US 11/386,517
The Challenge
Global PageRank Treats Every User The Same
Classic PageRank produces a single authority score per document that the entire user population shares. The same web page is treated as equally authoritative to a casual searcher and to a domain expert. Real authority is contextual: a paper is authoritative to a researcher in that field, not to a tourist looking for travel tips. The system needs an authority computation that respects the user's context, history, and interests so the ranking reflects what is authoritative to them specifically.
- One Score Fits All Users Poorly — Global PageRank cannot distinguish authority for different audiences. A page that is canonical for a niche audience competes against generic pages on the same global authority scale, usually losing.
- User Sessions Carry Signal — Each user has a history of visits, ratings, and behaviors that reveal what they consider authoritative. Ignoring these signals throws away the strongest indicator of per-user relevance.
- Teleportation Is The Lever — PageRank's random walk includes a teleportation step where the walker jumps to a uniformly random page. Biasing teleportation toward user-preferred pages is the mathematically clean way to inject personalization without breaking convergence.
- Need Stable Convergence — The personalized walk must still converge to a stable authority distribution. Naive biasing can produce ill-behaved walks; the patent has to define biasing that preserves convergence guarantees.
- Compute Cost At Web Scale — Recomputing PageRank per user is infeasible. The system needs a structure that allows fast per-user personalization without re-running the full eigenvalue computation for every visitor.
Innovation
Decompose Authority Into User-Influenced Components
The patent decomposes the authority value into three components: a structural component from outbound links, a starting-points component from documents that represent potential session starting points (often user-history-derived), and a user-likelihood component reflecting the probability that a population of users initiates sessions from particular pages. Combining the three components yields a personalized authority score that can be tuned per user without recomputing the entire graph.
- Build The Link Graph — Construct the directed graph of documents and hyperlinks as in standard PageRank. The graph is shared across users; what differs is how authority flows through it.
- Compute Outbound Link Component — For each document, compute the first authority component based on its outbound links. This is the structural PageRank backbone that all users share.
- Identify Session Starting Points — Identify a set of documents that represent likely session starting points. Sources include user history, browser homepage, bookmarks, recent visits, or topic preferences.
- Compute Starting-Point Component — Generate the second authority component as a function of the session starting points. Documents close to (linked from) starting points receive higher contribution to this component.
- Compute User-Likelihood Component — Generate the third component representing the probability that a user initiates sessions from any document. This component captures the aggregate user-base behavior pattern.
- Combine The Three — Combine the structural, starting-point, and user-likelihood components into a single per-document authority score. The combination weights are tunable per user or per user segment.
- Apply To Ranking — The personalized authority score replaces global PageRank in the ranking pipeline for the user. Documents that are authoritative to that user's typical sessions rank higher than under the global score.
Personalization Through Biased Teleportation
The mathematical contribution is biasing the random-walk teleportation vector toward user-relevant pages rather than uniform random pages. The biasing preserves the convergence properties of the original PageRank algorithm while injecting per-user signal at the place where the math is most amenable to it.
Three Components, One Authority
The authority value is no longer a single quantity. It is the combination of three independently computed components that can each be influenced by user signals.
- Structural Component — Computed from outbound links exactly like classic PageRank. Identical across users.
- Starting-Point Component — Computed from the user's typical session starting points (history, bookmarks, preferred topics). Per-user signal.
- User-Likelihood Component — Aggregate population behavior of where users typically begin sessions. Captures global usage patterns.
Personalization is implemented as biased eigenvalue computation, not as a post-hoc reranking.
<\/section>Technical Foundation
The Mathematical Decomposition
The authority computation is grounded in the standard Markov-chain interpretation of PageRank, with the teleportation vector decomposed to admit per-user biasing.
- Random-Walk Model — A walker traverses the link graph by following outbound links most of the time and teleporting to another page with small probability. The stationary distribution of this walk is the authority score.
- Teleportation Vector — The probability distribution over pages that the walker uses when teleporting. Uniform teleportation gives classic PageRank; biased teleportation gives personalized authority.
- Per-User Bias — The bias vector encodes the user's preferences: heavier weight on pages from history, bookmarks, or topical interests. The walk concentrates authority near those pages.
- Convergence Preservation — Standard PageRank's convergence guarantees hold for any well-formed teleportation vector. The biased version inherits these guarantees.
Quality Metrics
- Personalized Authority Score — Identical structure to classic PageRank with the bias vector replacing uniform teleportation. The damping factor c controls how much personalization contributes versus link structure.
PR_u(d) = (1-c) * sum( PR_u(d') / out(d') for d'->d ) + c * bias_u(d)
Key Insight: Personalization in IR is usually applied as a reranking step on top of global scores. The patent's contribution is doing it inside the eigenvalue computation itself by biasing the teleportation vector. This produces personalization that is mathematically coherent across all documents simultaneously, not just on the top-k that a reranker can reach.
<\/section>The Process
From User Signals To Personalized Ranking
The personalization pipeline runs in two stages: offline graph computation and per-user bias application.
- Graph Construction — Build and maintain the directed link graph over the document corpus. Same for all users.
- User Signal Collection — Gather per-user signals: visit history, ratings, bookmarks, topical preferences. Each signal feeds into the bias vector.
- Bias Vector Construction — Combine signals into a personalized teleportation distribution. Heavier weight on user-preferred pages.
- Iterative Authority Computation — Run the random-walk iteration with the personalized bias vector until authority scores converge.
- Apply To Live Ranking — Use the converged scores as the authority feature in the user's ranking pipeline. The same query produces different rankings for different users with different bias vectors.
What This Means for SEO
What This Means for SEO
Personalized PageRank shapes what every user actually sees on Google today. Knowing the mechanics changes how to think about authority, user behavior, and the relationship between your audience and your rankings.
- Authority Is Per-User, Not Global — There is no single 'rank' your page holds. Your authority varies by user, weighted by how aligned their behavior is with your content's topic and audience. Audience-defined SEO matters more than chasing the absolute global ranking.
- Visit History Compounds Authority — When users return to your pages, your pages become more authoritative for those users. Repeat visitors raise your effective rank in their personalized graph, not just your traffic count.
- Bookmarks And Direct Visits Are Authority Signals — Pages users bookmark or visit directly are weighted as session starting points in their personal bias vector. Direct traffic compounds with personalization, not against it.
- Topical Audiences Stack Per-User Authority — If your content serves a specific topical audience consistently, every user in that audience contributes their personalization bias toward your pages. Niche authority compounds within the audience even when global authority looks moderate.
- Brand Searches Build Personalized Ranking — Branded queries lead users to your pages, those visits enter their personal bias vector, and subsequent non-branded searches benefit from the personalized authority boost. Brand investment pays off through this mechanism beyond direct traffic.
- Per-User Differences Are Real, Not Noise — When two SEO professionals see different rankings for the same query, that is the personalization layer working. Track rankings from clean sessions (incognito, fresh accounts) for baseline measurement and accept that real-user experience varies.
- Long-Term Engagement Beats Acquisition Spikes — A traffic spike that does not produce return visits adds nothing to per-user authority. Sustained engagement is what feeds the personalization signal that compounds over time.