Page-rank

Another centrality measure

Recall centrality measures

Introduction to PageRank

  • PageRank is an algorithm used by Google Search to rank web pages in their search engine results.
  • Developed by Larry Page and Sergey Brin at Stanford University in 1996.
  • It measures the importance of web pages by analyzing the quantity and quality of links to them.
  • The core idea: A page is important if it is linked to by other important pages.
  • Hyperlink: A vote of confidence from one page to another.

Overview

  • Another node centrality measure for nodes in directed networks
  • Used to calculate importance, or prestige, or Web pages
  • Search engines need it to rank pages that seem equally relevant based on content

Source: DOI:10.1017/97811086539471

Intuition: The “Random Surfer” Model

PageRank was designed to fix the flaws of Eigencentrality in directed graphs (specifically “sinks” where influence gets trapped).

  • Recursive Logic: A node is important if it is linked to by other important nodes.

  • The Random Surfer: Models a user clicking links.

  • Clicking: With probability \(d\), the user follows a random link on the current page.

  • Teleporting: With probability \(1-d\), the user gets bored and jumps to a completely random page in the network.

  • Key Innovation: Unlike standard Eigencentrality, PageRank dilutes influence. If a page has many outgoing links, it passes less “authority” to each one.

The PageRank Equation

The score for node \(i\) is defined as:

\[PR(i) = \frac{1-d}{N} + d \sum_{j \in In(i)} \frac{PR(j)}{L(j)}\]

Definitions of Quantities:

  • \(PR(i)\): The PageRank score of node \(i\).
  • \(N\): Total number of nodes in the network.
  • \(d\): Damping Factor (typically \(0.85\)); the probability of continuing to click links.
  • \(1-d\): The probability of “teleporting” to a random node.
  • \(In(i)\): The set of nodes that point to node \(i\).
  • \(L(j)\): The out-degree of node \(j\) (the number of outgoing links from \(j\)).

Note that structurally the equation is similar to Katz centrality.

Katz vs PageRank: Same Idea, One Key Difference

  • Both answer “you are important if important nodes point to you,” and both cure the dead-source problem of plain eigenvector centrality by adding a baseline. They differ in one decisive move: how a node splits its importance among the nodes it points to.
Katz PageRank
Baseline term Constant \(\beta\) added to every node Teleport \(\tfrac{1-d}{N}\) to a random node
How score passes along an edge Full score sent down every out-link Score divided by out-degree \(L(j)\)
Tuning knob Attenuation \(\alpha\), must stay below \(1/\lambda_{max}\) Damping \(d\), fixed near \(0.85\), always valid
Interpretation Discounted count of incoming walks Long-run share of a random surfer’s time
Convergence Needs \(\alpha < 1/\lambda_{max}\) Guaranteed for any \(d < 1\)
  • The one difference that matters: out-degree normalization. In Katz, a node passes its full score along every outgoing edge, so a page that links to a thousand others is a thousand times as influential as one that links to a single page. PageRank divides by \(L(j)\) first, so each node has a fixed budget of influence to share, and a link from a selective page counts for more than a link from a spammy link-farm.

  • Why PageRank is easier to run. Dividing by out-degree turns the link matrix into a stochastic (column-sums-to-one) matrix, whose largest eigenvalue is exactly \(1\). That is why the damping factor can be any \(d < 1\) and always converges, while Katz must keep \(\alpha\) below the graph-dependent threshold \(1/\lambda_{max}\).

  • Bottom line: Katz is the natural choice when raw incoming volume should count; PageRank is the choice when influence should be a shared, conserved quantity, which is exactly what made it robust to web spam.

Matrix Formulation

To solve for the entire network vector \(\mathbf{r}\), we define the Google Matrix:

\[\mathbf{r} = \left( \frac{1-d}{N} \mathbf{E} + d \mathbf{M} \right) \mathbf{r}\]

  • \(\mathbf{r}\): The vector of PageRank scores.
  • \(\mathbf{M}\): The transition matrix, where \(M_{ij} = 1/L(j)\) if \(j \to i\) exists, else \(0\).
  • \(\mathbf{E}\): An \(N \times N\) matrix of all ones (representing the jump to any page).

Numerical Computation: Power Iteration

Since web-scale matrices are too large for direct inversion (\(O(N^3)\)), we use an iterative approach (\(O(m \cdot i)\)).

Iterative Calculation

  1. Initialize all pages with equal PageRank.
  2. Recalculate PageRank values iteratively using the formula.
  3. Continue until PageRank values converge to a stable value.
  4. Pseudocode:
Algorithm: Power Iteration for PageRank
Input: Adjacency Matrix A, damping factor d, tolerance epsilon
Output: PageRank Vector r

1. Initialize r = [1/N, 1/N, ..., 1/N]
2. while (change > epsilon):
3.     r_new = [(1-d) / N] * ones_vector
4.     for each node j:
5.         if L(j) > 0:
6.             for each neighbor i that j points to:
7.                 r_new[i] += d * (r[j] / L(j))
8.         else:  // Handle sinks (nodes with no out-links)
9.             r_new += d * (r[j] / N)
10.    change = ||r_new - r||
11.    r = r_new
12. return r

Toy Example (3-Node Network)

Graph Structure:

  • \(A \to B\)
  • \(A \to C\)
  • \(B \to C\)
  • \(C \to A\)

Initial Parameters:

  • \(N = 3\), \(d = 0.85\)
  • Initial scores: \(PR(A)=0.33, PR(B)=0.33, PR(C)=0.33\)
  • Teleportation constant: \((1-0.85)/3 = \mathbf{0.05}\)

Iteration 1 Calculation:

  1. \(PR(A)\): Receives from \(C\).
  • \(0.05 + 0.85 \cdot (PR(C)/1) = 0.05 + 0.85(0.33) = \mathbf{0.33}\)
  1. \(PR(B)\): Receives from \(A\) (which has 2 out-links).
  • \(0.05 + 0.85 \cdot (PR(A)/2) = 0.05 + 0.85(0.33/2) = \mathbf{0.19}\)
  1. \(PR(C)\): Receives from \(A\) and \(B\).
  • \(0.05 + 0.85 \cdot (PR(A)/2 + PR(B)/1) = 0.05 + 0.85(0.165 + 0.33) = \mathbf{0.47}\)

Observation: \(C\) becomes the most important because it pools the influence of \(B\) and half of \(A\). The scores will converge after a few more iterations.

How it works

  • Random surfer model: browse the Web at random
  • A random link is clicked from each page to get to the next
  • Random walk model modified with random jumps (teleportation)
  • At each step, with probability a, stop browsing and start new session form a random page
  • PageRank: how often will random surfer visit a page?
  • PageRank is conserved, neither created nor destroyed: \(\quad \sum R(i)=1\)

Source: DOI:10.1017/97811086539471

Example

PageRank vs in-degree

  • PageRank distribution is very skewed, similar to that of in-degree
  • PageRank is similar to in-degree to a first approximation (if all incoming links originate from pages with the same PageRank)
  • But links from more important pages bring more importance
  • Search engine optimization (SEO) companies try to boost a client website’s PageRank
  • Unscrupulous SEOs may use spamdexing but if caught by search engines, client can be de-listed

Source: DOI:10.1017/97811086539471

Motivating example: A Toy Google in Four Steps

  • Imagine a tiny web of just three pages, each linking to a couple of others. Here is the whole search engine, stripped to its bones:

  • 1. Crawl (go find the pages). Start at one page, follow its links to the next, and keep going until you have visited them all. Now you have a copy of every page.

  • 2. Index (make a word list). For each page, jot down which words it contains, then flip it around into a lookup table: "cat" -> [page 1, page 3], "dog" -> [page 2]. This is the part that lets you find pages instantly instead of re-reading the web every time.

  • 3. Rank (decide who is important). Count the links pointing at each page, and let important pages pass on their importance, the PageRank idea in one line. A page that many good pages link to floats to the top.

  • 4. Search (answer the query). A user types “cat.” Look up “cat” in the word list to get pages 1 and 3, then order them by their importance score and show the better one first.

  • That is Google in miniature: find the pages, list their words, score their importance, and at query time match the words and sort by score. Everything real Google adds (freshness, spam-fighting, language understanding, personalization) is refinement layered on top of these four moves.

Crawling

  • Crawling is the process by which Google discovers new and updated web pages.
  • Google uses bots called Googlebot to crawl the web.
  • Process:
    • Googlebot starts with a list of URLs from past crawls and sitemaps provided by webmasters.
    • It follows links on these pages to discover other pages.

Indexing

  • Indexing involves processing the crawled pages and adding them to Google’s index.
  • Steps:
    • Analyzing the content, including text, images, and video files.
    • Identifying the main topics and relevant keywords.
    • Storing this information in Google’s index, a large database of web content.
  • Ranking

  • Ranking is the process of ordering search results by relevance.
  • Google uses hundreds of factors to determine the relevance and quality of pages.
  • Key Factors:
    • Content Quality: Relevance, comprehensiveness, and freshness.
    • PageRank: The quantity and quality of backlinks.
    • User Experience: Page load speed, mobile-friendliness, and site architecture.
    • Semantic Understanding: Context and intent behind search queries.

Does google still use page rank?

  • PageRank is still used but is not the sole factor in search rankings.

  • PageRank remains a component but within a sophisticated, multifaceted ranking system.

  • Evolution of PageRank:

    • Initially foundational, now includes hundreds of ranking factors.
    • Refined over time to better handle spam and reflect page quality.
  • Other Ranking Factors:

    • Content Quality: Assessed for quality, relevance, and comprehensiveness.
    • User Experience: Factors like load speed, mobile-friendliness, and site architecture.
    • Backlinks: Consider context and relevance, not just quantity and quality.
    • User Engagement: Click-through rates, bounce rates, and time on site.
    • Semantic Understanding: Advances like BERT for understanding context and intent.
  • Algorithm Updates:

    • Frequent updates (Panda, Penguin, Hummingbird) improve quality and combat spam.
    • Increased use of machine learning and AI for refinement.

Query Understanding

  • Query Understanding involves interpreting the user’s search intent.
  • Google uses advanced natural language processing techniques.
  • Components:
    • Synonyms: Understanding different words with the same meaning.
    • Context: Using previous searches and user data to provide relevant results.
    • BERT: A deep learning algorithm for understanding the context of words in search queries.

Search Algorithms

  • Google’s search algorithms are a complex system of programs and processes.
  • Major Updates:
    • Panda: Focus on content quality.
    • Penguin: Targeting webspam and manipulative link practices.
    • Hummingbird: Enhancing semantic search capabilities.
    • RankBrain: Using machine learning to better understand search queries.

Personalization

  • Personalization tailors search results based on user-specific data.
  • Factors:
    • Search history.
    • Location.
    • Device used.
    • User preferences and behavior.

How Google Search Works

What Google Search Does

  • Google Search is the most widely used search engine, handling billions of queries per day.
  • The job is deceptively simple to state: given a few words, return the most relevant pages from the entire web in a fraction of a second.
  • It does this not by searching the live web at query time, but by consulting a precomputed index built ahead of time, then ranking the matches.

The Pipeline at a Glance

  • Search runs as a pipeline, and every result you see is the end of four stages:
    • Crawling: discover what pages exist on the web.
    • Indexing: read those pages and organize them into a searchable database.
    • Ranking: when a query arrives, order the matching pages by relevance and quality.
    • Query understanding: interpret what the user actually meant before ranking.
  • The first two stages happen continuously in the background. The last two happen live, in the moment you press enter.

Building the Index

Crawling: Discovering Pages

  • Crawling is how Google finds new and updated pages, carried out by automated bots collectively called Googlebot.
  • The crawler starts from a list of known URLs (from previous crawls and from sitemaps that site owners submit) and then follows the links on each page to discover more.
  • The web is a directed graph, so crawling is essentially a traversal of that graph: each page is a node, each hyperlink is an outgoing edge to follow.
  • Pages are revisited on a schedule, so that frequently changing sites stay fresh in the system while stable pages are recrawled less often.

Indexing: Organizing What Was Found

  • Indexing turns a pile of raw crawled pages into a structured, searchable database.
  • For each page, Google analyzes the content: the text, and signals from images and video, to work out what the page is about.
  • It identifies the main topics and the key terms, then records which pages contain which terms.
  • The core data structure is an inverted index: instead of “page to words,” it stores “word to the list of pages that contain it,” which is what makes lookup fast at query time.

Ranking Results

Ranking: Ordering by Relevance

  • Once a query matches many pages, ranking decides their order, since users rarely look past the first few results.
  • Google combines hundreds of signals, which fall into a few broad families:
    • Content quality: relevance to the query, comprehensiveness, and freshness.
    • Link signals: the quantity and quality of pages linking in, the idea behind PageRank.
    • User experience: page load speed, mobile-friendliness, and clean site structure.
    • Semantic match: how well the page fits the meaning and intent behind the query, not just the literal words.
  • No single signal decides the outcome; the final order is a weighted blend of all of them.

Does Google Still Use PageRank?

  • Yes, but it is now one signal among hundreds rather than the whole story.
  • Evolution: PageRank was foundational early on, and over time it was refined to resist link spam and to better reflect genuine page quality, then folded into a much larger ranking system.
  • The original PageRank patent has expired, but its core principle, that link structure encodes importance, still influences how modern ranking works.
  • The takeaway for this course: PageRank is best understood as the link-based component of ranking, a clean graph idea that still matters even though the production system around it is far more complex.

Understanding the Query

Query Understanding: Intent, Not Just Words

  • Before ranking, Google tries to interpret what the user really wants, since the same words can mean different things.
  • It handles synonyms, recognizing that different words can carry the same meaning.
  • It uses context, including signals like location and prior activity, to disambiguate.
  • Modern systems use deep-learning language models (such as BERT) to read a query as a whole sentence, capturing how word order and small words like “to” or “for” change the meaning.

Major Algorithm Updates

  • Google’s ranking is a large, evolving system, shaped by a series of named updates:
    • Panda: rewards high-quality content and demotes thin or low-value pages.
    • Penguin: targets web spam and manipulative link-building schemes.
    • Hummingbird: strengthens semantic search, matching meaning rather than keywords.
    • RankBrain: applies machine learning to better interpret unfamiliar or ambiguous queries.
  • The broad trend across these updates is steadily more machine learning and language understanding, and steadily less reliance on any single hand-tuned rule.

Personalization: Tailoring Results

  • Personalization adjusts results based on signals specific to the individual user.
  • The main factors include search history, location, the device in use, and observed preferences and behavior.
  • The effect is that two people entering the same query can see somewhat different results, each tuned to their likely intent and context.
1.
Menczer, F., Fortunato, S. & Davis, C. A. A first course in network science. (Cambridge University Press, 2020).