Key Concepts in Graph Theory
Nodes and Edges
- Nodes (Vertices) : Represent webpages.
- Edges (Links) : Represent hyperlinks between pages.
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.
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.
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).
