PageRank: Ranking by Importance

Forty Million Results, and the Right One Is First

A few weeks before your Class 10 board exams, you search for something like "CBSE class 10 science sample paper with solutions." In under a second you get back tens of millions of matching pages. And yet the top two or three results are almost always genuinely useful: a current, well-organised set of solved papers, not a dead page from years ago and not something that simply repeats your search words fifty times. You click, you study, and you never think about how that ordering happened.

Stop and think about it for a moment. Out of tens of millions of pages that all technically match your query, how does a program decide, correctly and in a fraction of a second, which handful actually deserve to be at the top? The answer starts with an idea that has nothing to do with computers.

Think about how you actually decide whose advice to trust before an exam. If a classmate you barely know tells you a certain reference book is "the best one," you shrug and move on. If your school's topper — the student whose method three seniors before you already credit for their results — spends ten minutes explaining exactly why that book worked, you take it seriously. Not because the topper spoke louder, but because their opinion already carries the weight of other people's trust. One well-placed recommendation can outweigh fifty careless ones.

That, almost exactly, is the idea that let a search engine rank tens of millions of pages by genuine importance instead of by keyword-stuffing. It is called PageRank, and this chapter builds it from scratch, the same way its inventors did.

A Stanford Project Called BackRub

In 1996, Larry Page and Sergey Brin were computer science PhD students at Stanford University, working on a research project they named BackRub, because it analysed the "backlinks" pointing at a given web page. Most search engines of that era ranked pages mainly by matching keywords: if your query contained a word and a page contained that word many times over, the page ranked higher. It was a system built to be gamed, and it was gamed constantly, with pages stuffing in repeated or hidden keywords that had nothing useful to say.

Page and Brin borrowed an idea from outside computer science: academic citation analysis. A research paper cited by hundreds of other papers is usually more significant than one nobody cites, and a citation from a paper that is itself highly cited should count for more than a citation from a paper nobody reads. Their insight was to treat the entire web the same way: a hyperlink from one page to another is a vote of confidence, and votes from important pages should count more than votes from unimportant ones. In 1998, Brin and Page published this idea in a paper titled "The Anatomy of a Large-Scale Hypertextual Web Search Engine," and that same year founded a company to put it to work: Google. The algorithm itself, PageRank, is named for both the web page it ranks and for Larry Page.

Not All Links Are Equal

To turn "importance" into something calculable, first turn the web into a graph: a set of nodes (the pages) connected by directed edges (the links, each pointing from the page it sits on toward the page it links to). If page X has a hyperlink to page Y, draw an arrow from X to Y. For any page, its out-degree is how many outgoing links it has, and its incoming links are simply every edge that points at it.

The obvious first idea is to rank pages by how many incoming links they have: treat every link as one vote, and count votes. This beats pure keyword-matching, but it breaks almost immediately. Anyone can create fifty throwaway pages that all link to one target, manufacturing fifty "votes" it did not earn — a tactic spammers used constantly once link-counting became common knowledge, building networks of pages called link farms for exactly this purpose. And even ignoring deliberate abuse, plain link-counting treats a link from a page millions of people trust exactly the same as a link from a page nobody has ever visited. It measures popularity, not importance.

PageRank's fix is the same one you already use to weigh advice before an exam: a vote should count in proportion to the credibility of whoever casts it, and a page's credibility is itself just its own importance, the very thing being calculated in the first place.

Letting Importance Flow Through the Graph

Here is the refined rule. Every page distributes its own importance evenly across every page it links to. If page Y has importance PR(Y) and links out to L(Y) different pages, then each of those pages receives PR(Y) / L(Y) from Y. A page's own importance is simply the sum of everything it receives this way:

PR(X) = sum, over every page Y that links to X, of PR(Y) / L(Y)

A page linked to by two important, selective pages — pages that each link out to only a few other things — ends up ranked higher than a page linked to by fifty unimportant, indiscriminate ones. That is the "topper versus random classmate" intuition, written as arithmetic.

There is an obvious problem: the formula is circular. Computing PR(X) requires already knowing PR(Y) for every page linking to X, but PR(Y) itself depends on the importance of whatever links to Y, all the way around the graph. No single page's score can be computed first, in isolation.

The way out is to stop insisting on an exact answer immediately and instead approximate it, again and again, until the approximation stops changing. Start by giving every page in an N-page graph the same importance, 1/N. Recompute every page's score using last round's numbers and the formula above. Do it again. Each round, scores shift slightly as importance flows toward well-linked pages and away from poorly-linked ones. After enough rounds the numbers settle and stop moving in any decimal place that matters, a state called convergence, and whatever they have settled to is the answer.

The Random Surfer and the Damping Factor

One thing can break the process above: a page, or a small cluster of pages, that link only to each other and nowhere else. Once iteration starts pouring importance into that closed loop, it has no way out; the loop keeps absorbing more of the graph's total importance every round, and the system never settles. Real link graphs have plenty of small clusters like this, so the formula needs a way to escape them.

The fix Brin and Page used is called the damping factor, written d and set to 0.85 in their original paper. Picture a hypothetical "random surfer" clicking around the web forever. Most of the time — with probability d — the surfer clicks a random link on whatever page they are currently viewing. The rest of the time — with probability (1 - d), so 0.15 when d is 0.85 — the surfer ignores the links on the page entirely and jumps to a completely random page anywhere in the whole collection, the way you might type a fresh address into your browser instead of clicking through. PageRank, under this model, is the fraction of time the random surfer spends on each page over a very long session. Because there is always some chance of a random jump, the surfer can never get permanently trapped in a closed loop, and that is precisely what guarantees the iteration converges.

Written in full, with N pages in total, the formula becomes:

PR(X) = (1 - d)/N + d * (sum, over every page Y that links to X, of PR(Y) / L(Y))

The first term, (1 - d)/N, is a fixed amount every page receives regardless of how many links point at it: the random surfer's chance of landing there by a fresh jump. The second term is the flow of importance through actual links, scaled by d to leave room for that baseline. A page with zero incoming links does not score zero; it still receives the flat (1 - d)/N, because the random surfer might land there directly. That floor value matters in the worked example next. (Students who go on to study linear algebra will eventually meet this same computation under a different name: PageRank is the dominant eigenvector of a matrix built from the link graph, and the round-by-round approximation here is a standard technique called power iteration for finding it.)

Four Pages, Traced by Hand

Consider a tiny four-page slice of the web, all about the same exam topic:

• A, a coaching institute's blog post, which links to B and to C.
• B, a student's personal exam-prep blog, which links to C, citing it as a source.
• C, a widely used exam-reference page, which links back to A as the official source.
• D, a brand-new forum post nobody has discovered yet, which links to C, but which nothing else links to.

The out-degrees are L(A) = 2, L(B) = 1, L(C) = 1, L(D) = 1. There are N = 4 pages, and we will use the standard damping factor d = 0.85, which makes the flat term (1 - d)/N = 0.15 / 4 = 0.0375 for every page, every round.

Start every page at the same importance, 0.2500. Round 1, using the starting numbers throughout:

• Only C links to A, and C's out-degree is 1, so PR(A) = 0.0375 + 0.85 * (0.2500 / 1) = 0.0375 + 0.2125 = 0.2500.
• Only A links to B, and A's out-degree is 2, so PR(B) = 0.0375 + 0.85 * (0.2500 / 2) = 0.0375 + 0.10625 = 0.1438 (rounded).
• A, B, and D all link to C. A contributes 0.2500 / 2, B contributes 0.2500 / 1, D contributes 0.2500 / 1, so PR(C) = 0.0375 + 0.85 * (0.1250 + 0.2500 + 0.2500) = 0.0375 + 0.85 * 0.6250 = 0.0375 + 0.53125 = 0.5688 (rounded).
• Nothing links to D, so the incoming sum is zero: PR(D) = 0.0375 + 0.85 * 0 = 0.0375.

After round 1: A = 0.2500, B = 0.1438, C = 0.5688, D = 0.0375 — each shown rounded to four places, though the calculation itself keeps every digit underneath. Round 2 repeats the same process on those full-precision numbers: C's actual round-1 value is 0.56875, not the displayed 0.5688, so PR(A) = 0.0375 + 0.85 * 0.56875 = 0.5209. Working through all four pages the same way gives A = 0.5209, B = 0.1438, C = 0.2978, D = 0.0375. Round 3 gives A = 0.2906, B = 0.2589, C = 0.4130, D = 0.0375. Notice D never moves: since nothing links to it, its score is always exactly the flat baseline, round after round. A and C keep trading the lead for several more rounds, but the swings shrink each time.

By around the thirtieth round the numbers stop moving in any digit that matters: A = 0.3725, B = 0.1958, C = 0.3941, D = 0.0375. Add those four rounded figures by hand and you get 0.9999, not a clean 1.0000 — not an error, just what happens when four independently-rounded numbers are added back together. Carried to full precision they sum to exactly 1, which the formula guarantees for any graph: every unit of importance a page holds gets fully redistributed each round, either through its links or through the flat term, and none of it ever leaks out.

The result matches the earlier intuition exactly. C ends up most important: three pages link to it, and two of them, A and B, are themselves reasonably well-regarded. D ends up least important, and its score is not approximately low, it is exactly the floor value of 0.0375 that every page gets automatically. That D still has a nonzero score at all, despite being linked to by no one, is the damping factor doing its job: even the web's most obscure, unlinked pages remain reachable by a random jump.

Tracing the Algorithm in Code

Here is the same computation as a Python function, built to handle a graph of any size:

def pagerank(nodes, links, damping=0.85, iterations=50):
    N = len(nodes)

    # One pass over every page's outgoing links builds a reverse map:
    # incoming[X] ends up holding exactly the pages that link to X.
    incoming = {node: [] for node in nodes}
    for source in nodes:
        for target in links[source]:
            incoming[target].append(source)

    pr = {node: 1 / N for node in nodes}

    for _ in range(iterations):
        new_pr = {}
        for node in nodes:
            incoming_score = sum(
                pr[other] / len(links[other]) for other in incoming[node]
            )
            new_pr[node] = (1 - damping) / N + damping * incoming_score
        pr = new_pr

    return pr


pages = ['A', 'B', 'C', 'D']
outgoing_links = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A'],
    'D': ['C'],
}

scores = pagerank(pages, outgoing_links)
for page in pages:
    print(f"{page}: {scores[page]:.4f}")

links stores each page's outgoing edges directly, exactly as we listed them above. Before any PageRank arithmetic happens, the function builds incoming by walking every page's outgoing list once and recording, at the target end of each edge, who sent it. For our four-page graph this produces {'A': ['C'], 'B': ['A'], 'C': ['A', 'B', 'D'], 'D': []} — read directly off the arrows, nothing scanned or guessed. From that point on, the loop that recomputes scores never has to ask "does this page link to that one?" for every possible pair; for any node, incoming[node] already is the list of pages linking to it, so C's update walks exactly three entries, and D's walks zero.

Run this and it prints A: 0.3725, B: 0.1958, C: 0.3941, D: 0.0375 — matching the by-hand result exactly. Two small floating-point details are worth noticing if you inspect the unrounded numbers. First, D's raw value prints as 0.037500000000000006, not a clean 0.0375, on every single round; ordinary binary floating-point storage cannot represent 0.0375 exactly, the same reason 0.1 + 0.2 famously prints as 0.30000000000000004 in Python. Second, the two round-1 values that land exactly on a rounding boundary in decimal, B's 0.14375 and C's 0.56875, print as 0.1437 and 0.5687 if you round them in Python rather than the 0.1438 and 0.5688 you get rounding by hand — again because neither number has an exact binary form, so the value actually stored is a hair below the tidy decimal, and rounding acts on what is actually stored. Neither detail is a bug; both are ordinary floating-point behaviour worth recognising instead of mistaking for an error in the algorithm.

Now the efficiency question. Building incoming costs one pass over all N pages to create empty lists, plus one pass over every outgoing edge to file it under its target: with V pages and E links in total, that is O(V + E) work, done once. Each round afterward loops over all V pages, and for every page sums over exactly its incoming list. Added up across all V pages in a single round, those inner sums touch every edge exactly once, because every edge belongs to exactly one page's incoming list, so a full round also costs O(V + E): work that grows in proportion to the number of pages plus the number of links, not something steeper. Running k rounds to reach convergence costs O(k * (V + E)) in total.

That bound depends entirely on looking up real incoming edges directly, the way incoming[node] does. Picture the alternative: for every page, scan the entire list of pages and check whether each candidate links to it. That repeats V checks for every one of the V pages: O(V²) comparisons per round, regardless of how few links actually exist. On a graph with billions of pages, V² is billions of billions: computationally impossible, however fast the computer. The web, though, is sparse: an average page links out to a few dozen others at most, not to any meaningful fraction of the billions of pages that exist, so E stays far smaller than V². Precomputing the incoming-links map once, and afterward walking only edges that genuinely exist, is what turns an intractable calculation into one that scales to the size of the actual web.

Beyond a Single Search Engine

The same idea, importance flowing recursively through a network and weighted by the importance of whoever is linking, works on any directed graph, not only hyperlinks. Academic citation analysis, which predates PageRank and partly inspired it, ranks research papers this way. Social platforms use variants of it to estimate influence, weighting a share or a follow by the reach of whoever made it. Recommendation systems, and even some analyses of biological networks that rank proteins by how central they sit inside an interaction network, reuse the same recursive, iterative structure.

PageRank also changed the arms race it was meant to end. Once pure link-counting became public knowledge, link farms had already gamed it; once PageRank made the credibility of the linking page matter too, spammers built farms of pages designed to look credible to each other. In 2004, Stanford and Yahoo! researchers published TrustRank, a variant that starts by manually seeding a small set of pages already known to be trustworthy, then propagates that trust outward through links the same way PageRank propagates importance; pages reachable only through suspicious link patterns, far from any trusted seed, end up scored as likely spam. Google's own ranking system today weighs PageRank alongside a large number of other signals, including content quality, freshness, and how a page performs on mobile devices, because link structure alone, however carefully weighted, was never going to be the whole story.

Back to Your Search Bar

Return to that board-exam search from the start of this chapter. Behind it sits a graph of billions of pages, each one distributing its importance across everything it links to, round after round, until the numbers stop moving. The sample-paper page that lands first earned that position the way the school topper earned their credibility: not by shouting, and not by being linked to the most times by just anyone, but by being trusted, deliberately, by other pages that had already earned trust of their own. Count the votes, weigh each one by who cast it, let the weights flow until they settle — traced all the way through, that is the arithmetic sitting underneath the first result on your screen.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where pagerank: ranking by importance is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting pagerank: ranking by importance to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind pagerank: ranking by importance, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.