Link Analysis: PageRank and HITS

Link Analysis: PageRank and HITS

14.1 Web as Graph and Good-Bad Propagation

14.1.1 Nodes, Edges, Inlinks and Outlinks

How can a messy pile of pages become something a computer can rank? The first move is to stop seeing pages as isolated texts and start seeing them as a network.

A node (one page or article that can be ranked, written $D$) is a single document in the collection. An edge (a directed connection from one document to another, written $i\to j$) is one hyperlink that carries meaning from its source to its target. Direction matters here. A link from $A$ to $B$ is not the same as a link from $B$ to $A$.

An outlink (a link that leaves the current page) points from the current document to some other document. An inlink (a link that arrives at the current page) points from some other document into the current document. For a page $D$, the count of outlinks is the out-degree (how many pages $D$ points to, written $outdeg(D)$), which might be $outdeg(D)=2$ when $D$ points to two pages. The count of inlinks is the in-degree (how many pages point to $D$, written $indeg(D)$), which might be $indeg(D)=5$ when five pages point to $D$.

This view unlocks the full network toolkit. Once documents and links form a graph, it becomes possible to ask for the most significant nodes, the most significant edges, tightly linked groups inside a huge network, and connected components that behave as one unit. A triangle of three pages that all point to each other carries a different weight than three isolated single links, because the triangle traps a walker inside while isolated links let the walker leave. At web scale, with thousands or millions of nodes, those small shapes add up to structure. Connected components, clusters, and hub centres all emerge from the same node-and-edge base.

Picture the shape with axes in mind. Put page index on the horizontal axis and link count on the vertical axis. Most pages sit low, with zero, one, or two inlinks. A few pages spike high, with hundreds of inlinks. That skewed curve, low for most and tall for a few, is the first visual hint of importance. The takeaway in one line: link shape already separates the few central pages from the many side pages.

Social networks, recommendation networks, and road networks all reuse the same node-and-edge view. In a social network the goal includes finding the importance of a node and closely linked groups inside a big network. In a road network the goal includes finding the best possible route between two places. In a document network the goal includes finding the rank of a node and the rank of an edge. The shared maths lets one toolkit serve all three settings.

One-line recap: pages as nodes plus hyperlinks as directed edges turn ranking into a network problem. That map leads straight to the good-bad labelling puzzle, where link direction alone hints at quality.

14.1.2 Good Nodes, Bad Nodes and Two Propagation Rules

Suppose a few pages are already known to be good and a few are known to be bad, while the rest are unknown. Can link shape alone colour each unknown node as good or bad?

Take a node $X$ with out-degree two, where $X$ points to one good document and one bad document. A tiny working assumption helps here, stated in words as good nodes never point to bad nodes. In symbols, if $X$ is good then none of its out-neighbours is bad:

$$X\text{ good }\Rightarrow \text{ no out-neighbour of }X\text{ is bad}$$

That assumption fails for $X$ here, because $X$ does point to a bad node. The fix is to label $X$ as bad. The logic is one step of elimination: the single bad outlink rules out the good label under this strict rule.

Carry the same idea forward in two directions. The first rule looks at outlinks. Verbal form: if you point to a bad node, you are bad. The second rule looks at inlinks. Verbal form: if a good node points to you, you are good. With those two rules, labels spread step by step. A node pointed to by a good node becomes good. A node that points to a bad node becomes bad. After a few rounds, the whole small network gets a label. In symbols, for any pages $u$ and $v$ with a link $u\to v$:

$$v\text{ bad }\wedge (u\to v\text{-neighbour bad})\Rightarrow u\text{ bad},u\text{ good }\wedge (u\to v)\Rightarrow v\text{ good}$$

This simple spread is useful for spam detection and related tasks. It gives a first way to turn a bare web graph into a labelled graph before any scoring starts. Spam hosts often link to each other and to compromised pages, while trusted pages rarely link to known spam, so the two rules push labels outward from the known seeds.

Describe the spread as a picture. Put iteration number on the horizontal axis and count of newly labelled nodes on the vertical axis. The curve rises fast in early rounds as neighbours of seeds get coloured, then flattens as the frontier runs out of unknowns. The takeaway: a few seeds can colour a connected neighbourhood in a handful of passes.

One-line recap: two one-way label rules turn a few known good and bad pages into a fully coloured neighbourhood. The same neighbour-tells-about-you idea then widens into guilt by association.

14.1.3 Guilt by Association

The good-bad spread is one instance of a broader network idea often called guilt by association (the behaviour or label of neighbours tells us about a node, so a node near many bad nodes looks bad and a node near many good nodes looks good).

One everyday version comes from a school classroom. Suppose a study group has six members. Two members copy in an exam. The other four never copy and never join any malpractice. Outsiders still call the whole group a bad group that copies. The four are judged by association with the two, not by their own acts. The mapping is direct: the group is the neighbourhood, copying is the bad label, and membership is the link. The break point: unlike web links, group membership is undirected and gives the four no way to cut the link, while a page can remove an outlink.

The same pattern runs in the other direction. Think of a very popular lead actor in older ensemble films. Wherever that lead appears, a cluster of supporting actors, villains, dancers, and crew appears with them, film after film. At time $T_0$ one cluster is seen in one film. At a later film $T_N$ much of the same cluster returns. The group travels together because of one central node. A director can play the same central role. The full crew follows the director from film to film. That repeated co-appearance is association at work: the central good node pulls its neighbours into the same orbit.

For document networks, the lesson is direct. Good tends to stay near good. Bad tends to pull neighbours toward bad. Link shape alone already hints at quality, because co-linking and repeated co-appearance expose shared origin even when page text hides it.

For search, this idea later hardens into concrete scores. Spam detection keeps the bad-spreads-backward half. Hub and authority scoring keeps the good-stays-with-good half but splits it across two roles. Citation similarity keeps the co-appearance half: two papers cited together by many third papers look similar in topic.

14.1.4 Student Questions and Answers

The distinction matters because the maths changes with the goal. Route finding minimises path cost. Importance ranking accumulates endorsement weight. Both live on the same graph, but they optimise different quantities.

Several students pressed the same doubt in different words, so one canonical answer covers the repetition: the early rules teach direction of spread, the later scores teach amount of spread.

14.2 Search Flow and Ranking Goal

14.2.1 From Query to Ranked List

Why does a search engine show one page first and another tenth when both contain the query words? The answer starts with the flow from query to ordered list.

A typical search flow has a small set of stages. A user types a query. The engine looks in the index, pulls back a relevant set of documents, and then must order that set. The open question is what decides that one document appears first, another second, and so on.

That ordering is the job of ranking. A ranking (an ordering of the retrieved documents from highest score to lowest, written as $d_{(1)},d_{(2)},\dots ,d_{(k)}$) puts the highest scoring document at the top, the next highest second, and so on. The score behind the order blends several inputs. Pure document scores matter, such as text match and link strength. User data matters too, such as past search interest, location, and related signals. The present focus is narrower: for a given query, how are documents ranked by their own link and content signals alone, before user-specific adjustments are layered on top.

Large web engines combine document-only scores with freshness, relevance, and user-specific scores at display time, with strong weight on link-based rank. Freshness lifts recent pages for breaking topics. Relevance ties the query words to page and anchor words. User signals adjust for place and history. The lecture isolates the document-only slice so link maths can be studied without personalisation noise.

Picture the blend as a stacked bar per document. The bottom block is text match, the middle block is link strength, the top block is freshness plus personal signals. The total bar height sets the order. The takeaway: link strength is one large block, never the whole bar.

One-line recap: retrieval pulls the candidate trolley, ranking stacks it by blended score. The next question is why link shape alone deserves a large block in that stack.

14.2.2 Why Link Shape Alone Can Rank

What does a bare pointer know that page text does not? It knows who vouched for whom.

A bare hyperlink already says a lot. If document $A$ points to document $B$, that pointer is a vote of attention from $A$ to $B$. Add up those votes across the web, weight them by who is voting, and an ordering emerges. That is the core bet of link analysis for ranking: use hyperlinks between documents to score web search results. A vote from a strongly endorsed page counts more than a vote from an unknown page, which is why later methods weight votes instead of counting them raw.

Think of class representatives voting for a school captain. Every ballot is a link. A ballot from a representative who won by a large margin carries more weight than a ballot from a narrow winner. The analogy breaks where links are forced: template footers and paid links are ballots stuffed without real endorsement, so they must be discounted.

One-line recap: hyperlinks are weighted votes, and adding those votes gives an order before any personal data is used. That vote idea becomes concrete once anchor words are added to the pointer.

14.3 Anchor Text, Doorway Pages and Google Bomb

14.3.1 Anchor Text as Description of the Target

A link points, but the clickable words describe. That description often summarises the target better than the target describes itself.

A hyperlink has two parts. One part is the pointer itself. The other part is the anchor text (the clickable words the reader sees, written $a$). In page source the pattern looks like an anchor open tag, the visible words, a reference to the target, and an anchor close tag. A reader sees only the visible words, such as student results or click here, while the pointer sits underneath.

Anchor text helps predict the target. Suppose page $A$ links to page $B$ with the visible words you can find cheap cars here. While ranking $B$, those four words suggest that $B$ should hold information about cheap cars. The link says the pages connect. The anchor words say what the target is about. The engine can therefore index $B$ under cheap and cars even when $B$ itself uses different wording.

More cases make the point. A book note might say an Information Retrieval book can be ordered at a local bookstore, where the bookstore name acts as anchor text. A university name or a course name can act the same way. A well known case is a query about IBM. Many pages match the letters IBM, including copyright pages, encyclopedia pages, and home pages. Anchor text plus the query can guide the engine straight to the intended IBM page, because many independent authors point to the IBM home page with the word IBM or computer. On a news-style page, a line such as IBM acquires a firm carries a link that should land on the parent IBM page. A line about new IBM optics should land there too. In each case the anchor words describe the target better than the bare pointer.

Anchor text is routinely indexed alongside links because it is often a better short summary of the target page than the target title alone. Corporate home pages are the textbook case: at the time of writing of the reference book, the IBM home page did not contain the word computer and the Yahoo home page did not contain the word portal, yet anchors pointing to them did, so only anchor indexing connected those queries to the right targets. Image-heavy pages behave the same way: the crawler sees no useful words inside the image, but anchors from other pages supply them.

Picture the fix with two columns. The left column lists words on the IBM page itself, with no computer entry. The right column lists anchor words from inlinks, with computer tallied many times. The horizontal axis is term frequency, and the anchor column spikes on the missing word. The takeaway in one line: outside words fill the gap left by inside wording.

One-line recap: anchors add human-written labels to bare pointers, and those labels often rescue queries that page text alone cannot answer. The maths of that addition comes next.

14.3.2 Mathematical View of Anchor Weight

How much should outside words count? Enough to move the order, not so much that they drown page text.

There is no single fixed equation for anchor use, but the working form discussed here can be written in direct form. Let $q$ be the query term set, let $a$ be the anchor word set on an inlink to page $B$, and let $w$ be a weight that favours anchor matches. The anchor-aware score for $B$ rises when $q$ overlaps $a$. Described in words as add extra weight when query words match anchor words on inlinks, one simple form is:

$$s(B)=s_{base}(B)+w\cdot overlap(q,a)$$

Here $s_{base}(B)\in \mathbb{R}$ is the base text score of page $B$, $overlap(q,a)$ counts shared terms between query $q$ and anchor set $a$, and $w\in \mathbb{R}$ with $w\ge 0$ sets how much anchor matches count. The point is not the exact $w$. The point is that anchor evidence is added on top of page text.

Take numbers to fix ideas. Suppose $s_{base}(B)=1.2$, query $q=\{\text{cheap},\text{cars}\}$, anchor $a=\{\text{cheap},\text{cars},\text{here}\}$, so $overlap(q,a)=2$, and $w=0.5$. Then $s(B)=1.2+0.5\times 2=2.2$. A rival page $C$ with stronger base $s_{base}(C)=2.0$ but no anchor overlap stays at $2.0$, so $B$ overtakes $C$ on this query because of outside words.

Picture weight tuning as a line. Put $w$ on the horizontal axis and ranking quality on held-out queries on the vertical axis. Quality rises as $w$ leaves zero, peaks at a middle value, then falls as anchor spam takes over. The takeaway: some anchor weight helps, too much invites attack.

Machine-learned scoring sets the real weights from many features at once, not from this one-line sketch alone. The sketch teaches the direction of effect. The trained system teaches the amount.

One-line recap: a small additive term lets outside words lift the right target. That same lift is what attackers later exploit.

14.3.3 Misuse, Doorway Pages and Google Bomb

A signal strong enough to help honest ranking is strong enough to attract attack once its weight is known.

A better signal invites misuse. If engines give high regard to anchor words, a writer with malicious intent can craft noble anchor words that point to unrelated targets. Readers who trust the visible words land where the writer wants, not where the words promise.

One named form is the doorway page pattern raised in discussion. A doorway page (a page or anchor whose visible words promise one topic but whose pointer delivers an unrelated target) uses a single word or short phrase that carries a link redirecting readers to a different target page than the words suggest. Since the clickable words live inside the anchor element, that trick is part of anchor handling in page source. The visible words promise one thing and the pointer delivers another.

A larger coordinated form was called a Google bomb (a coordinated anchor campaign in which many writers use the same chosen anchor words to favour documents of their choice, so a search returns deliberately bad or misleading results). A search returns deliberately bad or misleading results because many writers manipulate anchor text on purpose to favour documents of their choice. The anchor text might look noble, for example free learning, while the linked targets are not good documents. That gap pushed a large engine to add a different weighing function around 2007. The fix reduced the attack quickly but did not wipe out malicious anchor use at its root. Later coordinated queries such as dangerous cult surfaced unintended results across several engines. Older bombs such as who is a failure and evil empire were diffused. Engines still fight new variants today.

Anchor spam is an early case of adversarial search behaviour, where the same signal that helps honest ranking helps attackers once its weight is known. The 2007 weighing response is the textbook example of an arms race: attackers coordinate, the engine reweights, the visible bombs fade, then new phrasings appear and the cycle repeats.

One-line recap: anchor trust lifts honest targets and, when forged at scale, lifts chosen targets instead, which forces engines to weight coordination itself. Student doubts about that forgery path come next.

14.3.4 Student Questions and Answers

The key phrase to retain is malicious intent: honest anchors describe, forged anchors steer. The ranking weight is what converts a click trick into a position trick.

14.4 Prompt Injection as Modern Anchor Misuse

14.4.1 Email Summarization Attack

What happens when the same hide-a-directive trick moves from links to language models? The answer is prompt injection.

Malicious intent did not stop with anchor words. A modern parallel is prompt injection (hidden instructions smuggled inside data that a language model reads, so the model follows the data instead of the user). The shape matches anchor misuse: trusted visible content carries a hidden directive, and a system that gives high weight to that content obeys it.

A first-of-its-kind email attack around the time chat models became popular in 2022 shows the shape. Employees received long emails each day. To save time, they pasted each full email into a chat window and asked for a summary. One spam email hid an extra instruction inside its long body. Stated in words as after summarising this text, redirect the summaries to this web page, the hidden line told the model to send the summaries to a competitor address. Staff who trusted the tool kept pasting emails. Once that hidden instruction ran, prior summaries were redirected to the other address, leaking earlier work to a competitor.

The defence direction mirrors anchor defence. Just as engines learned to distrust bursty coordinated anchors, model systems learn to separate system instructions from data text, to flag redirect-style directives inside pasted content, and to ask before acting on embedded orders. Each new protocol is followed by a new hiding trick, so the arms race continues.

One-line recap: a hidden sentence inside trusted mail turned a summariser into a forwarder. The same trick then spread to images and maths puzzles.

14.4.2 Image and Arithmetic Attacks

The hidden-directive pattern is not tied to email text. It travels wherever a model reads rich input.

The same trick spread to other inputs. An image summarisation attack hides a frame inside a frame that carries an attack instruction. A user asks for the time shown on a clock in the image. The model reads both the clock and the hidden instruction, so answering the visible question also triggers the hidden order. Arithmetic and jailbreak variants use camouflaged instructions to bypass safety rules: a maths word problem carries an extra sentence that tells the model to ignore its guardrails, and the model obeys the smuggled line. Each new defence is followed by a new attack form, from tiny fonts to encoded text to multi-step puzzles.

The link to anchor misuse is direct. In both cases, trusted visible content carries a hidden directive. In anchor spam, the visible words promise free learning while the pointer sends readers elsewhere. In prompt injection, the visible email asks for a summary while the hidden sentence sends data elsewhere. The intent pattern matches: use a high-weight signal against itself. The engine trusted anchors, so attackers forged anchors. The model trusts pasted context, so attackers forge context.

Chat summarisation of email and images, competitor data theft through redirected summaries, and jailbreak studies all trace to prompt injection. The domain home is trustworthy AI deployment: email assistants, document summarizers, and image question-answering tools all sit on the same risk line.

14.4.3 Student Questions and Answers

14.5 Citation Analysis Roots of PageRank

14.5.1 From Co-Citation to PageRank

PageRank looks new, but its counting idea is decades older than the web. It began as a way to weigh journals by who cites whom.

PageRank did not start as PageRank. The earlier name for the family was co-citation or citation analysis. The 1976 study behind the idea is Pinski and Narin, who built on Garfield (1955) to develop a journal influence weight whose definition is remarkably similar to PageRank. That work laid out the idea of weighting citations by the standing of the citing source and then sat largely unused until about 1990. It became widely known only after the same link-counting thought was adopted for web ranking by Larry Page and Sergey Brin, published as Brin and Page (1998) and Page et al. (1998), the team behind a major search company.

The core transfer is simple. A scientific citation is a link. A web hyperlink is a link. Methods that score papers by who cites whom can score pages by who links to whom. Co-citation similarity between articles, where two papers cited together by many third papers look similar in topic, becomes co-link similarity between pages. Influence weight for journals becomes rank for pages.

Why did the 1976 idea wait until about 1990 to spread? Citation graphs were small and hand-curated, so raw counts sufficed for most library uses. The web removed that comfort: hyperlinks arrived at huge scale, with spam, boilerplate, and wildly uneven quality, so weighted flow became necessary rather than optional.

Citation counts, co-citation similarity between articles, and web PageRank share one ancestor idea. That shared root explains why the same eigenvector maths appears in library science and in web search under different names.

One-line recap: journal influence maths became web rank maths once links replaced citations. The citation-as-link mapping comes next.

14.5.2 Citation as Outlink

How exactly does a bibliography entry become a graph edge? By reading citing as pointing out and cited as pointed into.

Take a sentence such as Miller has shown that physical activity alters metabolism to estrogens, published in 2001. That sentence cites the work by Miller. In graph terms, the current scientific document holds text and gives an outlink to the Miller document. The citing page points out. The cited page receives an inlink. The visible sentence is the anchor, the bibliography entry is the pointer, and the Miller paper is the target.

One document can cite many others. One paper can be cited by many. That web of pointers lets us study co-citation similarity between articles. Two papers cited together by many third papers look similar in topic, because independent authors grouped them for the same reason. The 1976 paper explored exactly that link-based similarity with journal weights. Later, the same counting logic, scaled to the web with teleporting and normalisation, became PageRank.

Think of two recipes that always appear together in many cookbooks. Even without reading either recipe, the repeated co-appearance signals shared cuisine. Co-citation works the same way for papers and, by transfer, for pages. The analogy breaks where co-appearance is forced by one editor rather than chosen by many independent citers.

14.5.3 PageRank Scoring Sketch

What is the simplest link-only score before random walks enter? A binary table of who links to whom.

PageRank is a scoring measure based on link structure of web pages. A rough first sketch, not the final score, works like this. If document $D_1$ links to document $D_2$, set the pair score to 1. If document $D_1$ has no link to document $D_3$, set that pair score to 0. In symbols, let $L_{ij}\in \{0,1\}$ be the link entry from page $i$ to page $j$. Described in words as one if an outlink exists and zero otherwise, the rule is:

$$L_{ij}=1\text{ if }i\text{ links to }j,\text{ else }{L}_{ij}=0$$

Here $i$ and $j$ range over page indices, with $i,j\in \{0,\dots ,N-1\}$ for $N$ pages, and $L_{ij}$ is a scalar in $\{0,1\}$. A search engine takes this link signal, combines it with relevance, freshness, similarity, and user-specific attributes, and then orders the list. PageRank carries major weight in that blend, but it is not the only input.

Work the sketch on two pairs. If $D_1\to D_2$ exists, $L_{12}=1$. If $D_1\nrightarrow D_3$, $L_{13}=0$. Row $D_1$ therefore reads $[0,\dots ,1,0,\dots ]$ with a single one under its target. Column $D_2$ collects ones from all its citers. The full table is mostly zeros on the real web, which is why sparse handling matters later.

One-line recap: ones and zeros record the graph, and later steps turn that record into rank. The first question that record raises is who built the method.

14.5.4 Student Questions and Answers

14.6 Link Matrix and Transition Probability Matrix

14.6.1 Random Walk and Random Surfer

Why imagine a person wandering the web when the goal is a number per page? Because long-run visit share is that number.

Any network with nodes and edges shows random-walk behaviour. A method from network science called the walk-trap idea starts from one hunch. Stated in words as a random walker tends to reuse the same links more often than other links, the hunch is that traffic concentrates on a few busy paths. A peak-hour car moves more often on a few busy roads than on far side streets, because those roads connect more places. The same concentration appears for a web surfer: popular pages with many inlinks get revisited often, while side pages are rarely touched.

PageRank uses that behaviour through a random surfer picture. A random surfer (an imaginary walker who starts at a random page and at each step leaves along one of the current outlinks chosen at random, written as state $X_k$ at step $k$) keeps walking without a destination. Start at a random page. At each step, leave the current page along one of its outlinks. Keep walking. After many steps, each page settles to a long-term visit rate. That steady rate is the PageRank of the page. In words: the long-term fraction of time a random surfer spends on a page is its rank.

The walk-trap hunch explains why communities emerge: the walker stays long inside a dense cluster and rarely crosses to another cluster, just as a driver circles busy downtown streets before taking a rare highway out. That trapping is both a discovery tool for groups and a warning for ranking, since traps without teleporting would lock the surfer in.

14.6.2 Markov Chain With Pages as States

How can endless clicking be written as maths that guarantees a steady answer? With a Markov chain whose states are pages.

The walk is modelled as a Markov chain (a discrete-time random process that moves in steps where the next state depends only on the current state, written with transition chances $P_{ij}$). In the classic form the steps are times $T_0,T_1,T_2,T_3$, with a network state at each time. For ranking, the same frame is reused with a small change. Instead of times as labels, the states are documents $D_0,D_1,D_2,D_3$. At each step the surfer is on exactly one page. If the surfer is on $D_1$ at step $T_0$ and stays on $D_1$ at $T_1$ through a self-loop, the transition chance from $D_1$ to $D_1$ in that move is 1.

The object that stores all one-step chances is the transition probability matrix (a table $P$ whose entry $P_{ij}$ gives the chance of moving from page $i$ to page $j$ in one step, with each $P_{ij}\in [0,1]$). Each row sums to 1 because the surfer must go somewhere next, including possibly staying by a self-loop. A stochastic matrix (a non-negative matrix whose rows each sum to $1$) is the formal name for such a table, and its largest eigenvalue is $1$, which later yields the steady state.

Think of a board game where the next square depends only on the current square and one dice throw. The board squares are pages, the dice weights are row probabilities, and the history of how the token arrived does not change the next throw. The analogy breaks where web walkers use back buttons or memory, which would violate the history-free property, but the basic surfer obeys it.

One-line recap: pages as states plus one-step chances as rows give a Markov chain, and that chain is the machine that later produces steady ranks.

14.6.3 Link Matrix Construction on Seven Documents

How does a diagram of seven pages become a table of ones and zeros? By scanning each row for outlinks.

The first concrete step is a link matrix, also called a transition link matrix. A link matrix (the $N\times N$ table $L$ with $L_{ij}=1$ where an outlink $i\to j$ exists and $0$ elsewhere) records existence only. Use the same $L_{ij}$ rule from above: 1 where an outlink exists, 0 elsewhere. Anchor words such as car brand names that appear next to links in the demo network are noted but not used for PageRank scoring here. They describe targets for anchor indexing, but the PageRank pass reads only the pointer, not the words.

In the seven-document demo, labelled $D_0$ through $D_6$, the rows are built from outlinks only:

• From $D_0$ there is only one outlink, to $D_2$. Mark that cell 1. The rest of the row is 0, so row $D_0$ is $[0,0,1,0,0,0,0]$.
• From $D_1$ there are two outlinks: a self-loop to $D_1$ and a link to $D_2$. Mark $L_{11}=1$ and $L_{12}=1$, so row $D_1$ is $[0,1,1,0,0,0,0]$.
• The same row scan continues for $D_2$ through $D_6$, marking 1 for each outlink and 0 elsewhere. In particular $D_2$ links to $D_0$, $D_2$, and $D_3$, giving three ones in that row.

Read along a row to see outlinks. Read down a column to see inlinks. For example, inlinks to $D_3$ arrive from $D_2$, from $D_3$ itself through a self-loop, and from $D_6$. The matrix therefore holds both views at once even though it was built row by row from outlinks. Column $D_3$ shows three ones exactly at rows $D_2$, $D_3$, $D_6$.

Described in words as mark one for each outlink in the row and zero elsewhere, the construction rule in symbols is the same $L_{ij}$ definition above, with $i$ the row page and $j$ the column page.

14.6.4 Probability Matrix With Worked Fractions

How do counts become chances? By sharing each row equally among its outlinks.

Divide each row by its out-degree to turn counts into chances. Let $outdeg(i)$ be the out-degree of page $i$, a positive integer. Let $P_{ij}\in [0,1]$ be the one-step chance from $i$ to $j$. Described in words as link entry divided by out-degree of the row page, the rule is:

$$P_{ij}=\frac{L_{ij}}{outdeg(i)}$$

For $D_1$, which can go to either $D_1$ or $D_2$, each target gets half the chance:

$$P_{11}=0.5,P_{12}=0.5$$

The arithmetic is $L_{11}/2=1/2$ and $L_{12}/2=1/2$, with the other five entries $0/2=0$. The row reads $[0,0.5,0.5,0,0,0,0]$ and sums to $1$.

For a page such as $D_2$ with three out-targets $D_0$, $D_2$, and $D_3$, each gets one third:

$$P_{20}=P_{22}=P_{23}=\frac{1}{3}\approx 0.33$$

Here $1/3\approx 0.33$ per target, and $3\times (1/3)=1$, so the row again sums to one. The steps so far are only bookkeeping: link matrix first, then transition probability matrix. That table is the input for steady-state study with teleporting.

Picture one row as a pie. For $D_1$ the pie has two equal slices of $0.5$. For $D_2$ it has three equal slices of about $0.33$. The takeaway: out-degree sets slice count, division sets slice size.

14.6.5 Sparseness of Real Matrices

Why does size change the algorithm, not just the wait? Because real link tables are almost all zeros.

Two facts dominate real use. First, dimensions are huge, with millions of rows and columns on the web. Second, most real matrices are sparse, meaning zeros outnumber nonzeros by far. A page links to a handful of targets out of millions, so each row holds a few ones among millions of zeros. Even the tiny six- or seven-document demo looks sparse, with far more zeros than ones. Any ranking method must handle that sparseness wisely rather than assuming dense tables.

Picture the seven-by-seven grid with ones inked. Only a scattering of cells is filled. Now stretch that picture to a million by a million with the same handful per row: the ink becomes dust. The takeaway: dense storage and dense multiplies are impossible, sparse passes are mandatory.

14.6.6 Student Questions and Answers

14.7 Dead Ends, Ergodic Condition and Teleporting

14.7.1 Why Long-Term Visits Need More Than a Plain Chain

What stops the surfer from getting stuck? Nothing in the plain chain, which is why the plain chain is not enough.

The goal is a long-term visit rate for a page $D$ (the steady fraction of steps the surfer spends on $D$ over many steps, written $\pi (D)\in [0,1]$). That rate is not a single visit but a settled share, such as spending $31$ percent of all steps on one page. A plain Markov chain is not enough on web graphs because of dead ends and traps.

Picture four pages where $A$, $B$, and $C$ all point to $D$ and $D$ points nowhere. A surfer who reaches $D$ gets stuck, with no outlink to follow and no row that sums to one. On the real web the same shape arises naturally. Many pages may point to one famous article while that article points to few or none, such as a widely cited reference that itself cites nobody. Without a fix, no steady rate exists, because mass piles into the trap and never leaves.

The fix uses ergodic chains. An ergodic chain (a Markov chain in which every page can reach every other page by some path and the walk is not locked into a fixed repeating cycle) guarantees a unique steady state. A chain counts as ergodic when it is both irreducible and aperiodic. Irreducible (every page can reach every other page by some path, with positive chance after enough steps) means no isolated corner or dead end survives. Aperiodic (the walker is not forced into a fixed repeating cycle) means the walk is free to leave a loop such as $A$ to $B$ to $C$ to $A$ and visit elsewhere. A triangle $A$ to $B$, $B$ to $C$, $C$ to $A$ is welcome as local shape, but the walker must not be locked into visiting those partitions in strict rotation forever.

Imagine a theme park with one exit-free dead-end alley and one three-ride loop that forces ride order $A$, $B$, $C$, $A$. Visitors jam the alley or spin the loop forever. Adding free shuttle jumps to any ride breaks both jams. Teleporting is that shuttle.

14.7.2 Teleporting With Damping Factor Alpha

How does a single number unstick every trap at once? By giving the surfer a small jump chance on every step.

Teleporting gives the walker a way out. The everyday sense of the word applies: jump without following a path. Let $\alpha \in [0,1]$ be the damping factor (the chance of following a real outlink, here $\alpha =0.86$). Let $1-\alpha$ be the teleport chance (the chance of jumping elsewhere, here $0.14$). Let $N$ be the total page count, a positive integer, here $N=7$. Described in words as alpha times actual probability plus one minus alpha divided by N, the updated entry $P_{ij}^{\prime }\in [0,1]$ from page $i$ to page $j$ is:

$$P_{ij}^{\prime }=\alpha P_{ij}+\frac{1-\alpha }{N}$$

Here $P_{ij}$ is the old row probability from the probability matrix, and $P_{ij}^{\prime }$ is the new teleport-adjusted chance. Each row still sums to 1 because $\alpha \times 1+N\times (1-\alpha )/N=\alpha +(1-\alpha )=1$.

With teleporting in place, the walker cannot get stuck at one end, because every row gains a positive jump to every page. The adjusted table can then meet the irreducibility and aperiodicity needs for a steady rate: every page reaches every other page in one jump, and self-teleport breaks strict cycles.

Note on notation for readers of the reference book: the book writes teleport chance as its own parameter and link-following chance as one minus that parameter, with a typical teleport value $0.1$. The lecture flips the name, calling link-following chance $\alpha$ with a typical value $0.86$. The maths matches once names are mapped: lecture $\alpha$ equals book $1-\text{teleport-prob}$, and lecture $1-\alpha$ equals book teleport-prob. Keep the lecture form for exam answers.

14.7.3 Worked Teleport Numbers on Seven Documents

Numbers fix the rule better than words. With $\alpha =0.86$ and $N=7$, every entry can be computed by hand.

Take $\alpha =0.86$ with $N=7$ documents $D_0$ through $D_6$. Described in words as one minus alpha divided by N, the per-target teleport share is:

$$\frac{1-0.86}{7}=\frac{0.14}{7}=0.02$$

For $D_0$ to $D_2$, where a direct link exists with $P_{02}=1$, the new entry adds both shares:

$$P_{02}^{\prime }=0.86\times 1+0.02=0.86+0.02=0.88$$

Where $D_0$ has no link, with $P_{ij}=0$, only teleport remains:

$$P_{ij}^{\prime }=0.86\times 0+0.02=0.02$$

Row $D_0$ is therefore $[0.02,0.02,0.88,0.02,0.02,0.02,0.02]$, which sums to $0.88+6\times 0.02=0.88+0.12=1$.

For a row such as $D_1$ where the old chance was $0.5$ on two targets, the update is:

$$P_{1j}^{\prime }=0.86\times 0.5+0.02=0.43+0.02=0.45$$

Row $D_1$ becomes $[0.02,0.45,0.45,0.02,0.02,0.02,0.02]$, summing to $0.45+0.45+5\times 0.02=1$. For $D_2$ with three old thirds of about $0.333$, each linked entry becomes $0.86\times 0.333+0.02\approx 0.287+0.02\approx 0.307$, shown as $0.31$ in the reference table, while unlinked entries stay $0.02$.

Repeat for every row. The result is a full teleport matrix where every entry is positive and each row sums to 1. That full positivity is exactly irreducibility in numbers: every page can now reach every other page in one step.

A common mix-up is whether to divide by six or seven when a link already exists to one target. The answer used here is seven. All documents count, including the linked one, because teleport can land anywhere, even on the current page itself with chance $1/N$.

14.7.4 Textbook Form With Outlinks in the Denominator

Why do two books show different teleport equations for the same numbers? Because they start from different input tables.

Some books write the same update from the link matrix directly. Let $L_{ij}\in \{0,1\}$ be the link entry and $outdeg(i)$ the out-degree. Described in words as alpha times link entry over out-degree plus teleport share, the book form is:

$$P_{ij}^{\prime }=\alpha \frac{L_{ij}}{outdeg(i)}+\frac{1-\alpha }{N}$$

For $D_1$, the two ones divided by out-degree two give $0.5$ each, which is exactly the $P_{ij}$ used above:

$$\alpha \frac{1}{2}+0.02=0.86\times 0.5+0.02=0.45$$

The two forms match. One starts from link counts and divides by out-degree inside the equation. The other starts from the probability matrix where that division is already done. Do not treat the missing denominator as an error. It reflects which table is used as input.

Picture the pipeline as three trays. Tray one holds $L$ with zeros and ones. Tray two holds $P$ with row fractions. Tray three holds $P^{\prime }$ with teleport added. The book form jumps from tray one to tray three in one line. The lecture form steps from tray two to tray three. The takeaway: match the equation to the tray you were given.

14.7.5 Student Questions and Answers

14.8 Power Method and Steady-State PageRank Computation

14.8.1 State Vector, Next State and Pi Vector

The teleport table is built. How does a table become a rank per page? By flowing probability through it until the flow stops changing.

Only the matrix exists so far. The next goal is the steady state. Let $X=[x_1,x_2,\dots ,x_N]$ be a row state vector (one probability per document with entries in $[0,1]$ that sum to 1, written $X_k$ at step $k$). Let $P^{\prime }$ be the $N\times N$ teleport matrix with entries $P_{ij}^{\prime }\in [0,1]$. Described in words as next distribution equals current vector times probability matrix, the one-step update is:

$$X_{k+1}=X_k{P}^{\prime }$$

Here $X_k$ is the distribution at step $k$ and $X_{k+1}$ is the distribution at the next step. Each row of $P^{\prime }$ says where the surfer can be next and with what chance. Multiplying the current share vector by the table pushes shares forward one step: entry $j$ of $X_{k+1}$ sums over all $i$ the mass $x_i$ times the jump chance $P_{ij}^{\prime }$.

Repeat the multiply: $X$, then $X{P}^{\prime }$, then $(X{P}^{\prime })P^{\prime }$, and so on through $k$ steps, which is $X_k=X_0(P^{\prime }{)}^k$. When step $k-1$ and step $k$ no longer differ within tolerance, stop. That frozen vector is the steady-state vector, written $\pi =[{\pi }_1,\dots ,{\pi }_N]$. A steady-state vector (the distribution that no longer changes under the update, with each ${\pi }_i\in [0,1]$ and ${\sum }_i{\pi }_i=1$) satisfies:

$$\pi =\pi P^{\prime }$$

Each entry ${\pi }_i\in [0,1]$ is the long-term visit rate of document $i$. Higher means higher rank. This repeated multiply-until-frozen method is the power method. It works regardless of the starting vector, because the matrix keeps reshaping the scores toward the same steady point when the chain is ergodic. In eigenvector language, $\pi$ is the principal left eigenvector of $P^{\prime }$ for eigenvalue $1$.

Visualise convergence with iteration on the horizontal axis and each ${\pi }_i$ trace on the vertical axis. Early steps swing widely. Later steps flatten toward horizontal lines. The takeaway: differences shrink each round until all traces run flat.

One-line recap: push a share vector through the fixed teleport table until it freezes, and the frozen shares are the ranks. The two-page hand run makes that concrete.

14.8.2 Two-Document Worked Computation in Full

Hand arithmetic cements the method. Two pages and a fixed table are enough to see every multiply and add.

Use a tiny teleport matrix $P^{\prime }$ for documents $D_1$ and $D_2$:

$$\begin{array}{ccc}& D_1& D_2\\ D_1& 0.1& 0.9\\ D_2& 0.3& 0.7\end{array}$$

Described in words as probability 0.1 from document one to itself, 0.9 from one to two, 0.3 from two to one, and 0.7 from two to itself, this table is already teleport-adjusted. Each row sums to $1$: $0.1+0.9=1$ and $0.3+0.7=1$.

Pick a starting vector $X_0=[0,1]$. This is a valid distribution with entries in $[0,1]$ summing to $1$; it places all mass on $D_2$ at the start. A one-by-two vector times a two-by-two matrix gives a one-by-two vector.

First iteration, described in words as zero times 0.1 plus one times 0.3 for the first entry, and zero times 0.9 plus one times 0.7 for the second:

$$X_1=[0\times 0.1+1\times 0.3,0\times 0.9+1\times 0.7]=[0.3,0.7]$$

Step by step: $0\times 0.1=0$, $1\times 0.3=0.3$, sum $0.3$ for $D_1$. For $D_2$, $0\times 0.9=0$, $1\times 0.7=0.7$, sum $0.7$. Check: $0.3+0.7=1$. Ranks after step one are 0.3 for $D_1$ and 0.7 for $D_2$, so $D_2$ leads.

Second iteration, described in words as 0.3 times first column plus 0.7 times first column for entry one, and the same mix on the second column for entry two:

$$X_2=[0.3\times 0.1+0.7\times 0.3,0.3\times 0.9+0.7\times 0.7]$$

Work the numbers. For entry one, $0.3\times 0.1=0.03$ and $0.7\times 0.3=0.21$, so $0.03+0.21=0.24$. For entry two, $0.3\times 0.9=0.27$ and $0.7\times 0.7=0.49$, so $0.27+0.49=0.76$. Hence:

$$X_2=[0.24,0.76]$$

Check: $0.24+0.76=1$. The vector moved from $[0.3,0.7]$ toward $[0.24,0.76]$, with $D_2$ still ahead.

Keep multiplying the fresh vector by the same fixed matrix. The teleport matrix never changes. Only the state vector changes. After step two the vector is $[0.24,0.76]$. After step three and later steps the values keep adjusting by small amounts, closing toward $[0.25,0.75]$. After $k$ steps the $k-1$ and $k$ vectors match within tolerance. The frozen result here is:

$$\pi =[0.25,0.75]$$

Verify the freeze directly:

$$[0.25,0.75]P^{\prime }=[0.25\times 0.1+0.75\times 0.3,0.25\times 0.9+0.75\times 0.7]=[0.025+0.225,0.225+0.525]=[0.25,0.75]$$

Both entries reproduce, so $\pi =\pi P^{\prime }$ holds. So $D_1$ has long-term rate 0.25 and $D_2$ has 0.75. Show $D_2$ first and $D_1$ second, because higher score means better rank.

14.8.3 Practice Matrix for Home Use

A second tiny teleport matrix is set for home practice:

$$\begin{array}{ccc}& D_1& D_2\\ D_1& 0.7& 0.3\\ D_2& 0.2& 0.8\end{array}$$

Described in words as 0.7 self-loop on document one, 0.3 from one to two, 0.2 from two to one, and 0.8 self-loop on document two, this table already includes damping, so no extra alpha step is needed. Each row sums to $1$.

Try the first step from $[1,0]$ to fix the pattern: $[1\times 0.7+0\times 0.2,1\times 0.3+0\times 0.8]=[0.7,0.3]$. From $[0,1]$ the first step is $[0.2,0.8]$. Continue with the same fixed table until successive vectors agree. The freeze must satisfy $\pi =\pi P^{\prime }$ with entries summing to $1$.

14.8.4 Student Questions and Answers

14.9 Seven-Document PageRank Result, Query Timing and Limits

14.9.1 Thirteen Iterations to a Frozen Vector

What does the full seven-page run produce after the teleport table is iterated to stillness? One frozen share per page.

Return to the seven-document network. The probability matrix was built first from out-degree division. The teleport matrix with damping $\alpha =0.86$ was built next with $0.02$ added to every cell. The power method then ran on that teleport matrix from a valid start, reusing the same $P^{\prime }$ each round.

It took 13 iterations to freeze. From iteration 11 to 12 only one document value changed within tolerance. From iteration 12 to 13 nothing changed. The frozen $\pi$ vector, in order $D_0$ through $D_6$, is:

$$\pi =[0.05,0.04,0.11,0.25,0.21,0.04,0.31]$$

The order makes sense against link shape. Document $D_6$ has three inlinks and two outlinks. Many pages point to it and it points onward, so a random surfer lands there often and can also leave, which keeps its share high without trapping. Pages with few inlinks sit at the bottom, because the surfer rarely arrives except by teleporting. The reference table for teleportation rate $0.14$ reports the identical vector, which confirms the hand-built $P^{\prime }$ before iteration.

Picture the result as bars. Put document index $D_0$ to $D_6$ on the horizontal axis and steady share on the vertical axis. The bar at $D_6$ stands tallest at $0.31$. Bars at $D_1$ and $D_5$ are stubs at $0.04$. The takeaway: inlink-rich plus well-connected pages dominate the skyline.

One-line recap: thirteen passes turn the teleport table into a settled order topped by the well-linked $D_6$. That order is computed before any query arrives.

14.9.2 Query-Independent Scoring and Final Blend

When is PageRank computed: before the user types or after? Before, on a schedule, then blended after.

PageRank is computed before any query arrives. It is query-independent link analysis: the same $\pi$ serves every query until the next refresh. The engine refreshes page ranks on a schedule, stores them, pulls back documents relevant to the new query through the text index, and then re-ranks that relevant set. The re-rank blends PageRank with query-document relevance, freshness, user-specific scores, and related signals, with strong weight on PageRank. The ranked list the user sees reflects that blend, not PageRank alone.

Think of restaurant ratings printed monthly in a guide plus daily specials chosen per diner. The guide rating is PageRank: stable and shared. The final plate order adds hunger, season, and taste. The analogy breaks where freshness dominates: a breaking-news query flips the blend toward recency even when the guide still crowns an old page.

One-line recap: slow global ranks plus fast per-query blending give the displayed list. Link-only shares then hit two clear limits.

14.9.3 Limits of Link-Only Scoring

What can link counts never know? What is new and what the words mean.

Two limits motivate the next method. First, scores do not reflect current events. Suppose a major earthquake happened a day or a week ago. A fresh article from ten minutes, one hour, or ten days ago should outrank a five-year-old article on an older quake. But the old page has lived on the web longer and gathered many inlinks, so link-only scoring favours the old page over the fresh, more needed one. Age accumulates endorsement while recency starts near zero, so history beats urgency without a freshness correction.

Second, link shape cannot read natural-language queries. A query such as why is my laptop battery draining quickly asks about cause, linking draining to background apps or ageing cells. A query about latest updates asks about recency. Pure link counts carry no reading of draining, latest, or why, because arrows record that pages connect, not what the asker wants from them. Link structure is highly useful but not sufficient alone.

Freshness boosts for breaking news and language-aware matching sit alongside PageRank to cover these gaps in production. The earthquake case gets a recency lift that outweighs stale inlink mass. The battery-draining query gets intent matching that links cause-words to fix-words even when the best page has modest in-degree.

14.9.4 Student Questions and Answers

14.10 HITS Hubs Authorities Root Base Sets and Update Rules

14.10.1 Hubs and Authorities in Words and Symbols

What if one score cannot serve two needs: finding the best source and finding the best guide to sources? Then keep two scores.

The next method is HITS, short for Hyperlink-Induced Topic Search. It keeps two scores per page instead of one. A hub score rates a page as a pointer to good sources, written $hub(p)$. An authority score rates a page as a source worth pointing to, written $auth(p)$. For any query the method returns two ranked lists: one by hubs, one by authorities.

Two lines hold the whole idea. Stated in words as a good hub page for a topic links to many good authority pages, the hub view looks at outlinks. Stated in words as a good authority page for a topic is linked by many good hub pages, the authority view looks at inlinks. In a tiny ABCD sketch, if $A$, $B$, and $C$ all point to $D$, then $A$, $B$, and $C$ act as hubs and $D$ acts as the authority, because three guides agree on one maker.

Let $hub(p)\in \mathbb{R}$ with $hub(p)\ge 0$ be the hub score of page $p$. Let $auth(p)\in \mathbb{R}$ with $auth(p)\ge 0$ be the authority score of page $p$. Described in words as hub score is the sum of authority scores of its out-neighbours, and authority score is the sum of hub scores of its in-neighbours, the mutual updates are:

$$auth(p)=\sum _{q\to p}hub(q)$$

$$hub(p)=\sum _{p\to r}auth(r)$$

In matrix terms with adjacency $A$ where $A_{ij}=1$ for $i\to j$, the updates are $h=Aa$ and $a=A^{T}h$, which combine to $h=A{A}^{T}h$ and $a=A^{T}Aa$. Iteration therefore seeks the principal eigenvectors of $A{A}^T$ for hubs and $A^{T}A$ for authorities, which is why the scores settle when the chain of reinforcement stabilises.

A hand-compiled list of leukemia resources illustrates the split. The National Cancer Institute page on leukemia is an authority: it holds the content. A patient-group page that lists ten such sources with short notes is a hub: it holds the pointers. Ranking only authorities would hide the guide. Ranking only hubs would hide the source. Keeping both serves broad-topic searches such as learning about leukemia, where the asker needs entry points and destinations.

One-line recap: two mutually reinforcing sums separate guides from sources. Those sums run on a query-specific neighbourhood built next.

14.10.2 Root Set and Base Set

Where do hub-authority scores run? Not on the whole web, but on a small query-focused neighbourhood grown from text search.

HITS runs after the query, so it is query-dependent. The steps are:

1. Run a regular web search for the query and take the returned pages as the root set (the starting answer pool from text matching, often about $200$ pages in practice). Call this set $R$.
2. Grow the root set by adding all pages linked to by the root set and all pages that link to the root set, covering both out-degree and in-degree sides. Call this larger pool the base set (the root set plus its one-step in- and out-neighbours, written $S$). That expansion captures authorities that lack query words and hubs that point to them.
3. Compute hub and authority scores iteratively on the base set, normalising after each round, and output the top hubs and top authorities.

In one demo, $A$, $B$, and $C$ are the three root nodes. The wider network adds $D$, $E$, $F$, $G$, and $H$ through inlinks and outlinks around those roots. Pages $A$ through $H$ together form the base set on which iteration runs. A later textbook demo uses six documents with the same root-then-base idea and shows how weighting by query-word anchors shifts the same structure.

Picture the growth as rings. The inner ring holds roots $A,B,C$. The outer ring adds every page one arrow away in either direction. The takeaway: one-step expansion in both directions is enough to recover missing makers and guides without crawling the web.

A useful side effect is cross-language retrieval without translation: top hubs and authorities sometimes sit in other languages than the query, drawn in purely through links from the root neighbourhood. The link structure bridges languages that share no words.

One-line recap: text search seeds the roots, one-step link growth builds the base, and scoring stays inside that focused pool. Normalisation keeps that scoring comparable across rounds.

14.10.3 Normalization Each Round

Why divide after every round instead of letting scores grow? To compare shapes rather than sizes and to spot the freeze by stability rather than size.

After each scoring pass, divide each authority score by the total authority sum, and each hub score by the total hub sum. Let $S_{auth}={\sum }_{p}auth(p)$ and $S_{hub}={\sum }_{p}hub(p)$ over the base set. Described in words as divide each score by its column total, the normalised forms are:

$$aut{h}_{norm}(p)=\frac{auth(p)}{S_{auth}},hu{b}_{norm}(p)=\frac{hub(p)}{S_{hub}}$$

With all-one starts, the first authority pass yields in-degrees and the first hub pass yields out-degrees, with totals $15$ and $15$ in the $A$-through-$H$ demo. Dividing by $15$ gives the round-one shares. The next round weights the same neighbour sums by those shares, with totals $35/15$ and $45/15$, and dividing again gives round-two shares such as $4/35$ and $2/45$. Without the division, raw totals would climb each round and mask the settling order.

Some presentations normalise by the maximum or by Euclidean length instead of by sum. The lecture uses sum normalisation, so column totals are the divisors. The settled order is robust to the choice, but the numbers differ, so match the lecture divisor on exam tasks.

14.10.4 Student Questions and Answers

14.11 HITS Worked Iterations, Convergence and K-Means Contrast

14.11.1 First Iteration From All Ones

What do hub-authority updates give on round one when nothing is known yet? Simple degree counts.

Start all hub and authority values at 1 for pages $A$ through $H$, since no old scores exist yet. New authority for a page sums hub values of its in-neighbours. New hub for a page sums authority values of its out-neighbours. With all ones, the first pass simply counts degrees: authority equals in-degree, hub equals out-degree.

For page $A$, inlinks arrive from $C$, $G$, and $H$, so:

$$auth(A)=1+1+1=3$$

For page $C$, five inlinks arrive, so $auth(C)=5$. For page $A$ on the hub side, only one outlink leaves, so $hub(A)=1$. For page $B$ with two outlinks, $hub(B)=2$. For page $C$ with one outlink, $hub(C)=1$. The same count repeats for the rest: each authority is its in-degree, each hub its out-degree.

Totals after round one are 15 for authorities and 15 for hubs. The authority total $S_{auth}=15$ is the edge count counted by heads. The hub total $S_{hub}=15$ is the same edge count counted by tails. Described in words as running sums that reach fifteen, the normalisation divides every authority score by 15 and every hub score by 15. So $aut{h}_{norm}(A)=3/15$, $aut{h}_{norm}(C)=5/15$, $hu{b}_{norm}(A)=1/15$, $hu{b}_{norm}(B)=2/15$, and similarly for the rest.

Picture round one as two bar charts. Authority bars match in-degree heights, tallest at $C$ with $5$. Hub bars match out-degree heights, tallest at the page with four outlinks. The takeaway: structure alone, without prior reputation, already separates likely makers from likely guides.

One-line recap: ones turn the first pass into degree counting. Weighted sums take over from round two.

14.11.2 Second Iteration With Weighted Sums

How does round two differ? Same neighbour sets, but neighbours now carry unequal shares.

Round two uses the normalised round-one scores as weights. For $A$, inlinks still come from $C$, $G$, and $H$, but now their hub weights are $1/15$, $2/15$, and $1/15$. Described in words as sum of hub shares of in-neighbours, the new authority is:

$$auth(A)=\frac{1}{15}+\frac{2}{15}+\frac{1}{15}=\frac{4}{15}$$

For $B$, inlinks come from $E$ and $D$. Pull hub shares, not authority shares, giving $4/15$ plus $2/15$ style terms that total $6/15$. So $auth(B)=6/15$ before normalisation. For $C$ with five in-neighbours, the hub shares add to $12/15$. So $auth(C)=12/15$ raw. The same pattern covers the rest: list in-neighbours, look up their hub shares, add.

Hub updates flip the source. For $A$ with one outlink, take the authority share of its target, which is $2/15$. So $hub(A)=2/15$ raw. For $B$ with its out-neighbours, add authority shares such as $5/15$ plus $1/15$ to reach $6/15$. So $hub(B)=6/15$ raw. Repeat for all pages: list out-neighbours, look up their authority shares, add.

Now normalise again. The authority total this round is $35/15$. Described in words as each raw authority divided by thirty-five over fifteen, an example is:

$$aut{h}_{norm}(A)=\frac{4/15}{35/15}=\frac{4}{35}\approx 0.114$$

The division cancels the $15$: $(4/15)\times (15/35)=4/35$. Numerically $4÷35\approx 0.114$.

The hub total is $45/15$. Described in words as each raw hub divided by forty-five over fifteen, an example is:

$$hu{b}_{norm}(A)=\frac{2/15}{45/15}=\frac{2}{45}\approx 0.044$$

Again $(2/15)\times (15/45)=2/45\approx 0.044$. Every other page follows the same divide-by-total step, giving per-role shares that sum to $1$.

One-line recap: round two replaces unit votes with share-weighted votes, then rescales to shares again. Those shares still need many rounds to settle.

14.11.3 Convergence, Cost and Final Ranks

When can iteration stop? Only when the full tables stop moving, not when a few entries pause.

After two rounds the scores have not frozen. Authority and hub tables at round four and round six show gradual settling. By round six, pages $D$, $E$, $F$, $G$, and $H$ look stable, with repeated values such as 0.6 style entries and 0.111111 style entries on one side, while $A$, $B$, and $C$ still move on the authority side and $C$, $E$, and $F$ still move on the hub side. Freezing only part of the table is not convergence. The process must continue until the full tables stop changing within tolerance for both roles.

Convergence does arrive, around the twelfth iteration in the extended trace for node $B$ and its peers. Both hub and authority columns settle at that point. The method stays fast because each step is only addition along edges. Described in words as sum hubs for authorities and sum authorities for hubs, the per-round cost is linear in edge count $O(|E|)$, so many rounds remain cheap and the turnaround stays quick even in a notebook that loops repeatedly. No matrix inversion or dense multiply is needed.

Final ranks split by role. On authority, node $C$ stands highest because the most inlinks point to it, with five in-neighbours feeding it the largest weighted sum, and $B$ comes next. On hubs, node $E$ stands highest because it carries four outlinks, more than any peer, so it accumulates the largest authority-weighted sum. If the need is the best authoritative source, rank by authority and place $C$ first. If the need is the best pointer page that links to many authorities, rank by hubs and place $E$ first. The split is deliberate: keep the two lenses separate and choose based on the task.

The six-document textbook trace tells the same story from the other side. Document six carries the top PageRank and lines up with hub strength, while its authority score stays low. Document three carries high authority through many inlinks. PageRank alone would crown document six. An authority need would crown document three instead, which proves one score cannot serve both needs.

Picture convergence with iteration on the horizontal axis and share on the vertical axis for nodes $A$, $B$, $C$. Early rounds swing. Middle rounds narrow. Late rounds run flat after about twelve passes. The takeaway: patience to round twelve buys stability that round two cannot show.

One-line recap: iterate weighted sums to full stillness around round twelve, then read makers and guides from separate lists. A different iterative loop clarifies what is shared and what is not.

14.11.4 K-Means Contrast

Why compare link iteration with clustering? Because both loop until nothing changes, yet update nothing alike.

A question linked HITS iterations to cluster finding. The shared trait is real: both loop until nothing changes. The mechanics differ. HITS sums neighbour scores along links. K-means measures distances to centres and averages coordinates.

K-means works like this on a toy set with points $A$, $B$, $C$, $D$, and $E$ and two centres $C_1$ in blue and $C_2$ in green:

1. Pick random points as starting centroids $C_1$ and $C_2$.
2. For each data point, measure distance to $C_1$ and to $C_2$, written $d(C_1,A)$ versus $d(C_2,A)$, and assign the point to the closer centre. Suppose round one gives cluster one as $\{A,B\}$ and cluster two as $\{C,D,E\}$.
3. Recompute each centroid as the mean of its members. Let $(x_1,y_1)$ and $(x_2,y_2)$ be member coordinates in a flat Cartesian plane. Described in words as average of x plus average of y, the new blue centre over two points is:

$$C_1^{new}=\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$$

For three members divide by three. The fresh $C_1$ lands between $A$ and $B$. The fresh $C_2$ lands among $C$, $D$, and $E$. Round one ends only after both assignment and centroid refresh; half a round does not count.

Round two remeasures from the new centres. Point $C$ may now sit closer to the blue centre, giving $\{A,B,C\}$ versus $\{D,E\}$. Refresh means again: sum the three for $C_1$ and divide by three, sum the two for $C_2$ and divide by two. Round three remeasures. If assignments no longer shift, centroids no longer shift either. With $C_1$ holding $\{A,B,C\}$ and $C_2$ holding $\{D,E\}$ unchanged from the prior round, stop and call the clusters final.

HITS sums neighbour scores along links. K-means measures distances to centres and averages coordinates. Both stop at no-change, but the update math and the data shape are different: graph reinforcement versus spatial regrouping.

14.11.5 Student Questions and Answers

Exam Guidance Summary

• Expect a short matrix task: build a link matrix with $L_{ij}=1$ for outlink and $0$ elsewhere, divide rows by out-degree to get $P_{ij}=L_{ij}/outdeg(i)$, then apply $P_{ij}^{\prime }=\alpha P_{ij}+(1-\alpha )/N$ with a given $\alpha$ such as $0.86$ and $N=7$ giving $0.02$ per target, $0.88$ for single-link rows, and $0.45$ for half-split rows. Check every row sums to $1$.

• Expect two or three power-method steps on a two-by-two teleport matrix such as rows $[0.1,0.9]$ and $[0.3,0.7]$ from start $[0,1]$, reaching $[0.3,0.7]$, then $[0.24,0.76]$, and freezing at $\pi =[0.25,0.75]$ with $D_2$ ranked first. Show every multiply and add, verify $\pi =\pi P^{\prime }$, and never start from $[0,0]$ or $[1,1]$.

• Expect a home-style twin with rows $[0.7,0.3]$ and $[0.2,0.8]$ from starts $[1,0]$ and $[0,1]$, asking for iteration count $k$ to freeze within a stated tolerance. Report both $k$ and the frozen pair, which must match across starts.

• Expect HITS one-round counts on the $A$ through $H$ base: authority equals in-degree, hub equals out-degree, totals $15$ and $15$, then normalised shares over $15$. Second round for $A$, $B$, and $C$ with $4/15$, $6/15$, and $12/15$ style authority sums and $35/15$ normalisation giving $4/35$, $6/35$, $12/35$, plus $2/15$ style hub terms with $45/15$ normalisation giving $2/45$.

• Expect a contrast question: PageRank is query-independent and computed before the query over the whole graph, then used in per-query re-ranking with relevance, freshness, and user signals. HITS is query-dependent and computed after the query on root-then-base sets with iteration and normalisation.

• Expect anchor-text reasoning: why anchor words help ranking, with cheap-cars pointers and IBM home-page disambiguation (copyright, encyclopedia, home, IBM acquires a firm, IBM optics), plus how misuse yields Google bomb cases such as free learning, dangerous cult, who is a failure, and evil empire, and the 2007 weighing response that reduced but did not remove the attack.

• Expect limits of PageRank: stale highly linked pages outrank fresh breaking pages such as earthquake updates from ten minutes to ten days ago versus five-year-old pages, and link counts cannot read natural-language queries such as why battery drains quickly with draining, latest, and why.

• Expect lineage naming: Garfield (1955) to Pinski and Narin (1976) journal influence weight to Brin and Page (1998) and Page et al. (1998) with Larry Page and Sergey Brin, plus the Miller 2001 metabolism citation as an outlink example and co-citation similarity as joint citation by third papers.

Use the row-sum rule as a free arithmetic check on every matrix task before iterating.

Hand tasks reward one clean round over many rushed rounds, so practise normalisation until the divide-by-total step is automatic.

Key Industry Applications

• Web search ranking blends PageRank $\pi$ with relevance, freshness, similarity, and user-specific signals, with strong weight on the link score. The slow offline PageRank clock plus the fast per-query blended re-rank is the production pattern behind every displayed list.

• Anchor text indexing improves target description, seen in cheap-cars pointers, bookstore and university anchors, and IBM query disambiguation across copyright, encyclopedia, and home pages plus IBM acquires a firm and IBM optics lines. Outside description fills gaps where page text uses marketing wording or image-only content.

• Adversarial search covers Google bomb anchor manipulation with noble words such as free learning, doorway single-word redirects that promise one topic and deliver another, and the 2007 weighing response that cut coordinated bombs quickly without ending malicious anchor use, with residual cases such as dangerous cult plus diffused cases who is a failure and evil empire.

• Prompt injection in chat models mirrors anchor spam, seen in 2022 email summarisation theft that redirected summaries to a competitor address through a hidden line, plus image frame-in-frame clock attacks and arithmetic jailbreak variants that bypass safety rules. Role separation between instructions and data is the shared defence direction.

• Citation and co-citation analysis from Garfield (1955) through Pinski and Narin (1976) underlies both paper similarity and web ranking, seen in the Miller 2001 metabolism citation case where the citing paper gives an outlink and the Miller paper gains an inlink. Joint citation by third papers signals topic closeness.

• Random-walk and walk-trap thinking links peak-hour road use, social network groups, recommendation networks, and surfer models for ranking. Traffic concentration on busy paths is the shared observation; group discovery versus page scoring is the split in use.

• Sparse-matrix handling is required because real link tables are huge and mostly zero, even in tiny seven-document demos. Adjacency lists with edge-linear power iteration replace dense grids at web scale.

• HITS two-score design serves different needs, with authority best for source pages such as node $C$ with five inlinks and hub best for pointer pages such as node $E$ with four outlinks, plus the six-document split where document six leads PageRank and hubs while document three leads authorities. Broad-topic search such as leukemia needs both lists.