Introduction

In 1998 Larry Page and Sergey Brin described the PageRank algorithm: model a random surfer who follows links at random and occasionally teleports to any page on the web. The fraction of time the surfer spends on a page is its rank — popular pages that are linked from other popular pages naturally collect more visits.

The idea is elegant, but it treats every surfer as identical. A page about competitive chess strategy ranks the same whether the person searching is a grandmaster or a ten-year-old looking for the rules. The algorithm knows nothing about intent.

In 2002 Taher Haveliwala published Topic-Sensitive PageRank at the ACM World Wide Web conference. His insight was small but powerful: instead of teleporting uniformly to any page, bias the random walk so the surfer preferentially returns to pages inside a topic set — a curated collection of pages on a specific subject. The same link graph now yields a different vector of scores for each topic, and any query can be ranked by a weighted blend of those vectors based on the query's topic distribution.

The result is a family of rankings — one per topic — that can be combined at query time to personalize results without recomputing PageRank for every user.

Try It

The graph below has eight pages connected by links. Every page also belongs to one or two topics (Science, Tech, Sports). Choose a topic using the buttons, and the algorithm runs power iteration with the teleport distribution biased toward that topic's seed pages. Bar heights show the resulting rank scores.

<!-- Topic-Sensitive PageRank interactive demo -->
<p class="hint">Click a topic button to bias the random surfer toward that topic's seed pages, then watch how authority redistributes across the graph. Node size and bar height reflect rank score.</p>
<div class="topic-btns" id="topicBtns">
  <button data-topic="science" class="topic-btn active">Science</button>
  <button data-topic="tech" class="topic-btn">Tech</button>
  <button data-topic="sports" class="topic-btn">Sports</button>
  <button data-topic="global" class="topic-btn ghost">Global (unbiased)</button>
</div>
<div id="graphArea" class="graph-area"></div>
<div class="status" id="status"></div>
<div class="legend">
  <span class="dot science"></span>Science
  <span class="dot tech"></span>Tech
  <span class="dot sports"></span>Sports
</div>

/* Layout and color styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.topic-btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .7rem; }
.topic-btn { font: 600 13px system-ui; padding: .35rem .75rem; border: 1.5px solid #1d3557;
             background: #1d3557; color: #fff; border-radius: 20px; cursor: pointer; transition: all .15s; }
.topic-btn.ghost { background: #fff; color: #1d3557; }
.topic-btn.active { background: #e63946; border-color: #e63946; color: #fff; }
.graph-area { width: 100%; max-width: 560px; position: relative; height: 320px; margin: .3rem 0; }
svg.graph { width: 100%; height: 100%; overflow: visible; }
.node-circle { stroke-width: 2; cursor: default; }
.node-label { font: 600 11px system-ui; fill: #fff; pointer-events: none; text-anchor: middle; dominant-baseline: central; }
.bar-wrap { position: absolute; bottom: 0; left: 0; right: 0; display: flex; align-items: flex-end;
            justify-content: space-around; height: 80px; padding: 0 4px; }
.bar { flex: 1; margin: 0 2px; border-radius: 4px 4px 0 0; transition: height .4s ease; min-height: 2px; }
.bar-lbl { position: absolute; bottom: -18px; width: 100%; text-align: center; font: 600 9px system-ui; color: #555; }
.status { font-size: .85rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0 .1rem; color: #0a7d33; }
.legend { font-size: .8rem; color: #555; display: flex; gap: .8rem; align-items: center; margin-top: 2px; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-right: 3px; }
.dot.science { background: #2a7de1; }
.dot.tech    { background: #6a3d9a; }
.dot.sports  { background: #e69500; }
.edge { stroke: #bbb; stroke-width: 1.4; fill: none; marker-end: url(#arrow); }

/* Topic-Sensitive PageRank: replace uniform teleport with topic-biased teleport */
var i18nFmt = function(s, v) { return s.replace(/%(\w+)%/g, function(_, k) { return String(v[k] != null ? v[k] : ''); }); };
/* Eight pages: three topics (science, tech, sports) */
var PAGES = [
  { id: 0, label: 'Phys',  topic: 'science', x: 0.18, y: 0.15 },
  { id: 1, label: 'Chem',  topic: 'science', x: 0.40, y: 0.08 },
  { id: 2, label: 'Bio',   topic: 'science', x: 0.62, y: 0.18 },
  { id: 3, label: 'Code',  topic: 'tech',    x: 0.80, y: 0.42 },
  { id: 4, label: 'AI',    topic: 'tech',    x: 0.65, y: 0.58 },
  { id: 5, label: 'Foot',  topic: 'sports',  x: 0.38, y: 0.72 },
  { id: 6, label: 'Swim',  topic: 'sports',  x: 0.16, y: 0.56 },
  { id: 7, label: 'Stats', topic: 'tech',    x: 0.50, y: 0.40 }
];
/* Directed links between pages */
var EDGES = [
  [0,1],[1,2],[2,3],[3,4],[4,7],[7,0],[7,1],[7,5],[5,6],[6,0],[2,7],[4,5],[3,7],[1,7]
];
var N = PAGES.length;
/* Seed sets per topic (pages the surfer prefers to teleport back to) */
var SEEDS = {
  science: [0,1,2],
  tech:    [3,4,7],
  sports:  [5,6],
  global:  [0,1,2,3,4,5,6,7]
};
var TOPIC_COLORS = { science: '#2a7de1', tech: '#6a3d9a', sports: '#e69500', global: '#888' };
var D = 0.85; /* damping factor (probability of following a link vs teleporting) */
/* Build column-stochastic transition matrix from the edge list */
function buildTransMatrix() {
  var out = [];
  for (var ii=0;ii<N;ii++) { out.push(new Array(N).fill(0)); }
  var outDeg = new Array(N).fill(0);
  for (var ei=0;ei<EDGES.length;ei++) outDeg[EDGES[ei][0]]++;
  for (var ei=0;ei<EDGES.length;ei++) {
    var s=EDGES[ei][0],t=EDGES[ei][1];
    if (outDeg[s]>0) out[t][s] += 1/outDeg[s];
  }
  /* Handle dangling nodes (no outgoing links) by teleporting uniformly */
  for (var j=0;j<N;j++) if (outDeg[j]===0) for (var i=0;i<N;i++) out[i][j]=1/N;
  return out;
}
var M = buildTransMatrix();
/* Power iteration - run until convergence (80 steps is enough for this small graph) */
function pagerank(seeds) {
  var teleport = new Array(N).fill(0);
  for (var si=0;si<seeds.length;si++) teleport[seeds[si]] = 1/seeds.length;
  var r = new Array(N).fill(1/N);
  for (var iter=0; iter<80; iter++) {
    var next = new Array(N).fill(0);
    for (var i=0;i<N;i++) for (var j=0;j<N;j++) next[i] += M[i][j]*r[j];
    for (var i=0;i<N;i++) r[i] = D*next[i] + (1-D)*teleport[i];
  }
  return r;
}
/* Rendering helpers */
var currentTopic = 'science';
var area = document.getElementById('graphArea');
var W = 560, H = 240;
function px(page) { return { x: page.x * W, y: page.y * H }; }
function drawSVG(scores, topic) {
  var max = Math.max.apply(null, scores);
  var color = TOPIC_COLORS[topic];
  var svg = '<svg class="graph" viewBox="0 0 ' + W + ' ' + H + '" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arrow" markerWidth="6" markerHeight="6" refX="5" refY="3" orient="auto"><path d="M0,0 L6,3 L0,6 Z" fill="#bbb"/></marker></defs>';
  /* Draw directed edges */
  for (var ei=0;ei<EDGES.length;ei++) {
    var s=EDGES[ei][0],t=EDGES[ei][1];
    var sp=px(PAGES[s]),tp=px(PAGES[t]);
    var dx=tp.x-sp.x,dy=tp.y-sp.y,len=Math.sqrt(dx*dx+dy*dy);
    var rr=14,ex=tp.x-dx/len*rr,ey=tp.y-dy/len*rr;
    svg += '<line class="edge" x1="'+sp.x.toFixed(1)+'" y1="'+sp.y.toFixed(1)+'" x2="'+ex.toFixed(1)+'" y2="'+ey.toFixed(1)+'"/>';
  }
  /* Draw nodes - size proportional to rank score; seed pages colored, others gray */
  for (var i=0;i<N;i++) {
    var p=PAGES[i],pos=px(p);
    var nr=10+Math.round(scores[i]/max*14);
    var isSeed=SEEDS[topic].indexOf(i)>=0;
    var fill=isSeed?color:'#aaa';
    svg+='<circle class="node-circle" cx="'+pos.x.toFixed(1)+'" cy="'+pos.y.toFixed(1)+'" r="'+nr+'" fill="'+fill+'" stroke="'+color+'" opacity="'+(isSeed?1:.7)+'"/>';
    svg+='<text class="node-label" x="'+pos.x.toFixed(1)+'" y="'+pos.y.toFixed(1)+'">'+p.label+'</text>';
  }
  svg+='</svg>';
  /* Bar chart below the graph showing rank scores */
  var bars='<div class="bar-wrap">';
  for (var i=0;i<N;i++) {
    var h=Math.max(4,Math.round(scores[i]/max*68));
    var fill=TOPIC_COLORS[PAGES[i].topic];
    bars+='<div style="position:relative;flex:1;margin:0 2px;"><div class="bar" style="height:'+h+'px;background:'+fill+';"></div><div class="bar-lbl">'+PAGES[i].label+'</div></div>';
  }
  bars+='</div>';
  area.innerHTML=svg+bars;
}
function run(topic) {
  var seeds=SEEDS[topic];
  var scores=pagerank(seeds);
  drawSVG(scores,topic);
  var best=0;
  for (var i=1;i<N;i++) if (scores[i]>scores[best]) best=i;
  var topicLabel = topic === 'science' ? 'Science' : topic === 'tech' ? 'Tech' : topic === 'sports' ? 'Sports' : 'Global';
  document.getElementById('status').textContent=i18nFmt('Top page for %topic%: %page% (score %score%)',{topic:topicLabel,page:PAGES[best].label,score:(scores[best]*100).toFixed(1)});
}
document.getElementById('topicBtns').addEventListener('click',function(e){
  var btn=e.target;
  if (!btn.classList.contains('topic-btn')) return;
  var btns=document.querySelectorAll('.topic-btn');
  for (var i=0;i<btns.length;i++) btns[i].classList.remove('active');
  btn.classList.add('active');
  currentTopic=btn.getAttribute('data-topic');
  run(currentTopic);
});
run(currentTopic);
Result
Console

Notice that the same links produce very different authority distributions. A page that is deeply embedded in the Science cluster rises when you bias toward Science, even if it has fewer in-links overall. This is the core insight of Haveliwala (2002): a biased teleport turns a global rank into a topic-aware rank.

The Algorithm

Classic PageRank solves the eigenvector equation r=d⋅Mr+(1−d)⋅u\mathbf{r} = d \cdot M \mathbf{r} + (1-d) \cdot \mathbf{u}, where MM is the column-stochastic link matrix, d≈0.85d \approx 0.85 is the damping factor, and u\mathbf{u} is the uniform teleport vector — every page equally likely.

Topic-Sensitive PageRank replaces u\mathbf{u} with a biased teleport vector ut\mathbf{u}_t that concentrates probability on the seed pages of topic tt:

rt=d⋅Mrt+(1−d)⋅ut\mathbf{r}_t = d \cdot M \mathbf{r}_t + (1-d) \cdot \mathbf{u}_t

Each topic tt has its own seed set StS_t (pages strongly associated with that topic), so ut[i]=1/∣St∣\mathbf{u}_t[i] = 1/|S_t| if page i∈Sti \in S_t and 00 otherwise.

Precomputation. Haveliwala used the 16 top-level categories of the Open Directory Project (ODP) as topics. Offline, power iteration runs 16 times — once per topic — until the rank vector converges (typically 50–100 iterations). Each iteration costs O(∣E∣)O(|E|) where ∣E∣|E| is the number of links. The result is 16 vectors of nn scores, stored on disk.

Query time. Given a query qq, estimate how much qq belongs to each topic — call it λt(q)\lambda_t(q). The personalized score for page ii is simply ∑tλt(q)⋅rt[i]\sum_t \lambda_t(q) \cdot r_t[i], computed in O(k)O(k) per page, where k=16k = 16.

Why it scales. The expensive eigenvector computation happens entirely offline. Serving a ranked list at query time is a cheap dot product. Adding more topics costs one extra offline pass each — nothing touches the online path.

Compared to vanilla PageRank, the added cost is exactly k−1k-1 extra power-iteration runs — a fixed multiplier, not a function of the number of users or queries.

Where It Matters

Biasing the random walk with a topic vector is a general technique that appears far beyond web search:

  • Personalized web search: Google's early personalization research built directly on Haveliwala's work, computing per-user teleport distributions from browsing history.
  • Academic citation ranking: tools like Semantic Scholar weight citation authority toward a researcher's own field, so a chemistry paper is compared against chemistry norms, not physics or law.
  • Social network influence: given a seed set of domain experts, a biased random walk on the follower graph identifies the most authoritative accounts in that domain — the same math, a different graph.
  • Recommendation systems: biased PageRank on a user–item graph (users linked to items they liked) surfaces items popular among similar users, without explicit user clustering.
  • Anti-spam detection: spam farms typically lack strong topical coherence. Comparing a page's topic-sensitive rank to its global rank reveals anomalies a uniform score misses.

The deeper principle — that authority is context-dependent and a biased random walk captures that context — connects topic-sensitive PageRank to spectral graph theory and to the random walk literature at large.

Conclusion

Topic-Sensitive PageRank shows how a tiny algorithmic change — swapping the uniform teleport for a topic-concentrated one — unlocks a qualitatively richer notion of authority. The same web, the same links, but now the score of a page depends on what the asker cares about.

Haveliwala's 2002 paper precomputed 16 rank vectors offline and blended them at query time with no extra crawl or matrix factorization. That architecture — expensive eigenvector work done once, cheap personalization done per query — became a blueprint for scalable personalization across search, recommendation, and social ranking systems.

The random surfer, it turns out, becomes far more useful once it knows where it would rather spend its time.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pagerank-topic-sensitive/Content licensed under CC BY-NC 4.0.