Web Crawling, Web Graphs and PageRank

URLs are messier than they look

Are https://example.org/page, https://example.org/page/, https://example.org/page#section and https://EXAMPLE.org/page four different documents? Maybe. Maybe not. This introduces URL normalization and canonicalization.

• Normalization steps: lowercase the hostname, remove URL fragments, resolve relative URLs, remove default ports, normalize path components (https://example.org/a/../page → https://example.org/page).
• ❗ Normalization must be conservative. Different URLs can genuinely represent different resources: /page and /page/ may differ, and so may ?id=1 and ?id=2.

Try it: normalize a URL

Each step shows what it changed. The last three are not safe in general: turn them on to see what an aggressive crawler would merge.

Why duplicate URLs matter

Without duplicate handling, with links A → B, A → C, B → C, C → A, the crawler keeps rediscovering A, B, C, A, B, C, … At minimum, maintain visited_urls = set(). But there is a second problem: different URLs → the same or nearly identical content: printer-friendly pages, tracking-parameter variants, mobile/desktop versions, mirrored pages, session-specific URLs. So we distinguish a URL duplicate from a content duplicate.

import hashlib

fingerprint = hashlib.sha256(
    text.encode("utf-8")
).hexdigest()

Near duplicates: two pages may differ only slightly: the same article with a different navigation bar, timestamp or ad. Exact hashes will not detect this. Large crawlers use approximate techniques such as shingling, MinHash and SimHash. We do not derive them here; the point is that duplicate detection is an IR systems problem, not merely a storage problem.

Try it: exact vs near duplicates

SHA-256 of both texts (computed in your browser), and, as a preview of shingling, the Jaccard overlap of their word 3-grams. One changed character changes the whole hash.

💡 This happens on real sites. The polite crawler of Part VII fetched 50 pages of quotes.toscrape.com and found 7 pairs of byte-identical pages, like /tag/love/ and /tag/love/page/1/: 14% of the crawl budget spent on copies.

PageRank

PageRank can be explained with a random surfer browsing the Web. At each page: with probability \(d\), follow one outgoing link chosen at random; with probability \(1 - d\), jump to a random page. The long-run probability of being on a page is its PageRank.

• Incoming PageRank: a page receives score from the pages that link to it, \(\sum_{v \in B_u} PR(v) / L(v)\).
• Outgoing-link division: if page A has PageRank 0.8 and links to four pages, it distributes 0.2 to each before damping. A page does not give its full score independently to every outgoing link.
• Damping: the \(1 - d\) component means the surfer can jump rather than follow links forever. This helps avoid problems caused by graph structure and gives a stable stochastic interpretation.
• Computing it: start with \(PR = 1/N\) everywhere and apply the formula to every page again and again (power iteration) until the values stop changing.

Try it: a PageRank playground

Node size shows PageRank. Click a node to see its formula with the numbers plugged in; click one node and then another to add or remove a link. Step through the power iteration, or send a random surfer and compare its visit frequencies with PageRank. The last column is the converged value, the same as nx.pagerank(G, alpha=d).

PageRank is query-independent

TF-IDF and BM25 compute \(score(q, d)\). PageRank computes something closer to \(importance(d)\), without knowing the user's query: BM25 is a query-dependent relevance signal, PageRank a query-independent authority / popularity signal. They measure different things. For the query python sorting algorithm, a globally important world news page should not rank highly merely because it has a high PageRank: textual relevance still matters.

The live demo with NetworkX

A small deterministic graph, not the live Web. Before running it: which node do you expect to get the largest score? Then compare the in-degree ranking with the PageRank ranking.

# pip install networkx scipy
import networkx as nx

G = nx.DiGraph()
G.add_edges_from([
    ("A", "B"),
    ("A", "C"),
    ("B", "C"),
    ("C", "A"),
    ("D", "C"),
    ("D", "A"),
])

list(G.edges())
# [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A'), ('D', 'C'), ('D', 'A')]
dict(G.in_degree())
# {'A': 2, 'B': 1, 'C': 3, 'D': 0}

pr = nx.pagerank(G, alpha=0.85)
for page, score in sorted(pr.items(), key=lambda x: x[1], reverse=True):
    print(page, round(score, 4))
# C 0.3839
# A 0.3797
# B 0.1989
# D 0.0375

💡 NetworkX's pagerank uses alpha=0.85 by default (docs) and needs SciPy: with pip install networkx alone it fails with No module named 'scipy'. Are the two rankings identical? Here the order is: C, A, B, D both ways. But C has 3 in-links and A only 2, and A ends only 0.004 behind: A's one link from C carries C's whole score, while C's three links come from pages that split theirs.

Dangling nodes

A dangling node has no outgoing links: A → B → C → nothing. In the random-surfer model the surfer would get stuck at C. Practical implementations redistribute this probability mass, usually uniformly over all pages (NetworkX does; the playground shows the extra term). Load Dangling node in the playground: C = 0.4744, B = 0.3412, A = 0.1844.

Link farms and manipulation

Once links affect rankings, people have incentives to manipulate links, e.g. artificial networks of pages created to amplify authority. Load Link farm: five farm pages and a target S that link to each other push S (0.2838) above C (0.1536), although no real page links to any of them. This illustrates a broader IR principle: a ranking feature can change user and publisher behaviour once people know it matters. Link analysis is useful, but it is not an unquestionable measure of quality.

PageRank on real graphs

A tiny crawler on a controlled site: one domain, at most 50 pages, one request at a time. It stores the URL, the page title and the outgoing links, builds the directed graph and calculates PageRank.

# pip install requests beautifulsoup4 networkx scipy
import hashlib
import time
from collections import deque
from urllib.parse import urljoin, urldefrag, urlparse
from urllib.robotparser import RobotFileParser

import networkx as nx
import requests
from bs4 import BeautifulSoup

SEED = "https://quotes.toscrape.com/"
AGENT = "IRCourseBot/0.1 (student lab crawler)"
MAX_PAGES, DELAY = 50, 1.0

def normalize(base, href):
    url = urldefrag(urljoin(base, href)).url          # resolve relative, drop #fragment
    p = urlparse(url)
    return p._replace(netloc=p.netloc.lower()).geturl()

robots = RobotFileParser()
r = requests.get(urljoin(SEED, "/robots.txt"), headers={"User-Agent": AGENT}, timeout=10)
robots.parse(r.text.splitlines() if r.status_code == 200 else [])   # 404: no rules, all allowed

host = urlparse(SEED).netloc
frontier, seen = deque([SEED]), {SEED}                 # BFS frontier + URL-duplicate check
G, pages, fingerprints = nx.DiGraph(), {}, {}

while frontier and len(pages) < MAX_PAGES:
    url = frontier.popleft()
    if not robots.can_fetch(AGENT, url):
        continue
    r = requests.get(url, headers={"User-Agent": AGENT}, timeout=10)
    time.sleep(DELAY)                                  # politeness: one request at a time
    if r.status_code != 200 or "text/html" not in r.headers.get("Content-Type", ""):
        continue
    soup = BeautifulSoup(r.text, "html.parser")
    pages[url] = soup.title.get_text(strip=True) if soup.title else ""
    fp = hashlib.sha256(r.text.encode("utf-8")).hexdigest()   # exact-duplicate fingerprint
    fingerprints.setdefault(fp, []).append(url)
    G.add_node(url)
    for a in soup.find_all("a", href=True):
        link = normalize(url, a["href"])
        if urlparse(link).netloc != host:              # stay on one domain
            continue
        G.add_edge(url, link)
        if link not in seen:
            seen.add(link)
            frontier.append(link)

G = G.subgraph(pages)                                  # keep only fetched pages
print(len(pages), "pages,", G.number_of_edges(), "links,", len(frontier), "URLs still in the frontier")
dupes = [urls for urls in fingerprints.values() if len(urls) > 1]
print(len(dupes), "groups of identical pages, e.g.", [u.replace(SEED, "/") for u in dupes[0]])

pr = nx.pagerank(G, alpha=0.85)
indeg = dict(G.in_degree())
for url, score in sorted(pr.items(), key=lambda x: -x[1])[:8]:
    print(f"{score:.4f}  in={indeg[url]:>2}  {url.replace(SEED, '/')}")
# 50 pages, 785 links, 99 URLs still in the frontier
# 7 groups of identical pages, e.g. ['/tag/inspirational/page/1/', '/tag/inspirational/']
# 0.1316  in=50  /
# 0.1316  in=50  /login
# 0.0343  in=40  /tag/truth/
# 0.0343  in=40  /tag/life/
# ...                                   (the ten "Top Ten tags" pages tie at 0.0343)

The winners are / and /login: every page's header links to them. Inside one site, PageRank mostly measures the navigation template, not content quality; the ten sidebar tag pages tie for the same reason. The run took about 75 seconds, almost all of it the politeness delay.

A pre-existing web graph, without live crawling: the Stanford web graph from SNAP, pages of stanford.edu (2002) as nodes and hyperlinks as directed edges: 281,903 nodes, 2,312,497 edges (an 8.9 MB file). PageRank on the whole graph takes a few seconds; do not try to visualize the whole graph.

# download web-Stanford.txt.gz from https://snap.stanford.edu/data/web-Stanford.html
import networkx as nx

G = nx.read_edgelist("web-Stanford.txt.gz", create_using=nx.DiGraph, nodetype=int, comments="#")
print(G.number_of_nodes(), G.number_of_edges())
# 281903 2312497

pr = nx.pagerank(G, alpha=0.85)
indeg = dict(G.in_degree())
by_indeg = sorted(indeg, key=indeg.get, reverse=True)
indeg_rank = {n: r for r, n in enumerate(by_indeg, start=1)}

for node, score in sorted(pr.items(), key=lambda x: -x[1])[:10]:
    print(f"node {node:>6}  PageRank {score:.5f}  in-degree {indeg[node]:>6} (rank {indeg_rank[node]})")

On a real graph the two rankings clearly differ: the top PageRank page is only 12th by in-degree, and the 2nd page by in-degree (21,920 in-links) is 9th by PageRank. Which pages link matters, not only how many.

Exercises

For the graph A → B, A → C, B → C, C → A, D → C, D → A (Outline graph in the playground). Answer first, then verify in the playground or with nx.pagerank(G, alpha=0.85).