Key Concepts in Graph Theory
Nodes and Edges
- Nodes (Vertices) : Represent webpages.
- Edges (Links) : Represent hyperlinks between pages.
Note
Edges can be directed (one-way links) or undirected (mutual links).
Degree of a Node
- In-Degree : Number of incoming links to a page.
- Out-Degree : Number of outgoing links from a page.
Example
A page with a high in-degree is often considered important or popular.
Paths and Connectivity
- Path: A sequence of edges connecting two nodes.
- Connected Graph: A graph where there is a path between every pair of nodes.
Note
The web is a directed graph, so connectivity is often studied in terms of strongly connected components.
Applications of Graph Theory in Web Connectivity
Search Engine Algorithms
- PageRank : Google's original algorithm uses graph theory to rank pages based on their link structure.
- HITS Algorithm : Identifies hubs (pages with many outgoing links) and authorities (pages with many incoming links).
Example
PageRank assigns higher scores to pages that are linked by other high-ranking pages.
Web Crawling
- Breadth-First Search (BFS): Crawlers use BFS to systematically explore the web.
- Depth-First Search (DFS): Used for deeper exploration of specific sections of the web.
Hint
BFS is preferred for web crawling because it ensures that all pages are discovered in the shortest path possible.
Community Detection
- Graph theory helps identify clusters or communities of related pages.
- These communities are used for personalized search and recommendation systems.
Example
Social media platforms use community detection to suggest friends or groups.
Challenges in Web Connectivity
Scale and Complexity
- The web contains billions of pages, making graph analysis computationally intensive.
- Dynamic Nature: The web is constantly changing, with new pages added and old ones removed.
Spam and Manipulation
- Link Farms: Artificially created networks of pages to manipulate search rankings.
- Spam Detection: Graph algorithms are used to identify and filter out spammy links.
