A Course on the Web Graph
The web graph is a directed graph whose vertices are web pages and whose oriented edges are links between the pages. The book is a readable and up-to-date exposition of the mathematical theory of web graphs and related real-world self-organizing networks. After some preliminaries, the classical Erdös-Rényi theory of random graphs is briefly introduced in chapter 3, together with the main probabilistic techniques used later on. Chapter 4 presents several stochastic models of the development of a web graph. The models usually start with an initial seed graph, and new vertices and edges are added according to some probabilistic rules. The objective is to capture statistical properties of the web graph, namely the power law degree distribution and the small world property. Chapter 5 exposes the mathematics behind search engines, e.g. the Google ranking algorithms PageRank and the Stochastic Approach for Link Structure Analysis (SALSA). The theory is based on Markov chains and associated matrices. Computational aspects are involved since graphs are huge. Chapter 6 describes an interaction between infinite graph theory and the web graph models. Chapter 7 presents three topics for web graph research: spectra of power law graphs, modelling viruses on the Web and domination in web graph models.