$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Les mathématiques de Google

  Lorsqu'il répond à une requête, Google n'affiche pas les résultats dans n'importe quel ordre. Il essaie d'afficher d'abord les pages les plus pertinentes, celles qui font référence par rapport à la requête formulée. Pour cela, il affecte à chaque page un nombre, le pagerank, qui quantifie l'importance d'une page. Plus le pagerank est élevé, plus la page est importante. Voyons comment est calculé ce pagerank.

  Google voit le web comme un "graphe", c'est-à-dire un ensemble de sommets, les pages, et un ensemble d'arêtes entre les sommets, qui modélisent les liens allant d'une page vers l'autre. S'il y a un lien entre la page A et la page B, alors il y a une arête entre le sommet A et le sommet B. Chaque arête est affectée d'un poids. Le poids de l'arête "page A->Page B" correspond à la probabilité qu'on a, lorsqu'on quitte la page A par un lien situé sur cette page, d'aller vers la page B. Si d'une page part 4 liens, chaque arête est donc affectée d'un poids 1/4. Prenons l'exemple suivant (où le web comporte 5 pages) :
Dans cet exemple, il est raisonnable de penser que la "Page 4" est la plus importante car c'est vers cette page que le plus d'autres pages pointent. Ensuite, on penser que la "Page 5" est plus importante que la "Page 2", car si elles ont chacun un lieu entrant, celui de la "Page 5" vient de la page la plus importante, etc...

  Le point de départ du PageRank est de donner des valeurs numériques à l'importance d'une page modélisant le phénomène précédent. L'idée est d'associer à chaque page la probabilité qu'on a, lorsqu'on visite le web, d'être à cette page donnée. Ceci peut se faire à l'aide de l'algorithme suivant. On introduit la matrice de transition du graphe, qui s'écrit
Le coefficient ai,j représente la probabilité, étant sur la page j, d'aller sur la page i. On introduit aussi le vecteur initial
qui représente l'état initial : on a autant de chances d'être sur n'importe quel page. On itère ensuite la matrice A par la relation
Le vecteur Xn représente la probabilité d'être sur chaque page lorsqu'on a suivi n liens. Il se trouve que la suite (Xn) converge - en réalité, il faut tricher un peu, ce n'est pas le cas ici... Les termes de la limite donnent le poids de chaque page, le "Pagerank".