Web Crawling and PageRank

Graph Theory · Axiom Academy

REAL WORLD Web Crawling and PageRank How Directed Graphs Power Search Engines and the Modern Internet Every time you use Google, you're querying one of the most impressive graph structures ever created: the entire World Wide Web represented as a directed graph. Nodes: Over 1.8 billion websites (as of 2024) Edges: Trillions of hyperlinks connecting pages Direction: Each hyperlink is a directed edge from one page to another Dynamic: Constantly changing as pages are created, updated, and deleted But how does a search engine make sense of this massive directed graph? How does Google know which pages are most important? The answer lies in graph theory . Web Crawlers: Graph Traversal at Scale Before Google can rank pages, it needs to discover them. This is where web crawlers come in - automated programs that traverse the web graph by following links. Start with seed URLs: Begin with a known set of important websites Fetch the page: Download the HTML content Extract links: Parse the page to find all outgoing hyperlinks (edges) Add to queue: Store discovered URLs to visit later Repeat: Continue traversing until millions of pages are indexed Breadth-First Search (BFS): Explore all neighbors before going deeper - ensures important pages close to seed URLs are found quickly Depth-First Search (DFS): Follow chains of links deeply - can get stuck in one part of the web Priority-Based: Crawl pages estimated to be more important first (using PageRank-like scores)

This is the written version of the interactive lesson above. See the full Graph Theory course.