Graphes et marches aléatoires en Terminale maths expertes

Graphes et marches aléatoires en Maths expertes : cours complet

Les graphes modélisent toutes sortes de réseaux (sociaux, transports, internet). Les marches aléatoires sur ces graphes sont à la base de nombreux algorithmes (PageRank, recherche, simulation).

Vocabulaire des graphes

Graphe

Un graphe $G=(V,E)$G = (V, E) est constitué :

• d'un ensemble de sommets (ou nœuds) $V$V ;
• d'un ensemble d'arêtes $E$E reliant des sommets.

Graphe orienté ou non

• Non orienté : les arêtes ne sont pas dirigées (Facebook, métro).
• Orienté : les arêtes ont un sens (Twitter, Web).

Degré

Le degré d'un sommet est le nombre d'arêtes qui en partent (ou y arrivent).

Pondéré

Un graphe est pondéré si chaque arête a un poids (distance, capacité, probabilité).

Matrice d'adjacence

Définition

Pour un graphe à $n$n sommets, la matrice d'adjacence $A$A est de taille $n\times n$n × n :

$$A_{ij}=\{\begin{array}{ll}1& \text{s’il y a une areˆte de }i\text{ vers }j\\ 0& \text{sinon}\end{array}$$Aᵢⱼ = 1 & s'il y a une arête de i vers j ; 0 & sinon

Pour un graphe pondéré, $A_{ij}$Aᵢⱼ est le poids de l'arête (ou $0$0 s'il n'y a pas d'arête).

Propriété

• Graphe non orienté : $A$A est symétrique.
• Graphe orienté : $A$A n'est pas nécessairement symétrique.

Chemins et puissances de matrice

Théorème

Le nombre de chemins de longueur $k$k entre $i$i et $j$j est donné par $(A^k{)}_{ij}$(A^(k))ᵢⱼ.

Exemple

Pour un triangle avec sommets $1,2,3$1, 2, 3 :

$$A=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$$A = 0 & 1 & 1 ; 1 & 0 & 1 ; 1 & 1 & 0

$A^2$A² donne le nombre de chemins de longueur $2$2.

$$A^2=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right)$$A² = 2 & 1 & 1 ; 1 & 2 & 1 ; 1 & 1 & 2

(Chaque sommet peut revenir à lui-même en $2$2 pas via les $2$2 autres sommets.)

Marche aléatoire sur un graphe

Définition

Une marche aléatoire est un déplacement de sommet en sommet, où à chaque étape on choisit au hasard une arête sortante (parfois selon des probabilités pondérées).

Matrice de transition

Si le sommet $i$i a $d_i$dᵢ arêtes sortantes, on définit :

$$P_{ij}=\frac{1}{d_i}\text{(si areˆte de }i\text{ vers }j\text{)}$$Pᵢⱼ = 1/dᵢ (si arête de i vers j )

Évolution

Si ${\pi }_n$πₙ est la distribution de probabilité à l'étape $n$n (vecteur ligne) :

$${\pi }_{n+1}={\pi }_{n}P$$πₙ₊₁ = πₙ P

Plus généralement : ${\pi }_n={\pi }_0{P}^n$πₙ = π₀ Pⁿ.

Distribution stationnaire

Définition

Une distribution stationnaire $\pi$π vérifie :

$$\pi P=\pi$$π P = π

(C'est un vecteur propre à gauche pour la valeur propre $1$1.)

Existence

Pour un graphe connexe (tout sommet accessible) et apériodique, la distribution stationnaire existe et est unique.

Calcul

On résout le système $\pi P=\pi$π P = π avec $\sum {\pi }_i=1$Σ πᵢ = 1.

Théorème ergodique

Énoncé (informel)

Pour une marche aléatoire « gentille » sur un graphe :

$$\underset{n\to +\infty }{\lim }{\pi }_n=\pi \text{(distribution stationnaire)}$$lim_n → +∞ πₙ = π (distribution stationnaire)

Conséquence

À long terme, la probabilité d'être au sommet $i$i se stabilise indépendamment du point de départ.

PageRank

Principe

L'algorithme de PageRank de Google calcule l'importance d'une page web via une marche aléatoire sur le graphe du Web.

Idée

Une page est importante si beaucoup de pages importantes pointent vers elle. La distribution stationnaire d'une marche aléatoire sur le Web donne ce classement.

Variante avec téléportation

À chaque étape, le marcheur a une probabilité $\alpha$α de sauter sur n'importe quelle page au hasard (pour éviter de rester bloqué).

Exemple détaillé

Graphe à 3 sommets

$$P=\left(\begin{array}{ccc}0& 0,5& 0,5\\ 0,5& 0& 0,5\\ 0,5& 0,5& 0\end{array}\right)$$P = 0 & 0,5 & 0,5 ; 0,5 & 0 & 0,5 ; 0,5 & 0,5 & 0

Distribution stationnaire : par symétrie, $\pi =(1/3,1/3,1/3)$π = (1/3, 1/3, 1/3).

Vérification

$\pi P=(1/3\times 0+1/3\times 0,5+1/3\times 0,5,\dots )=(1/3,1/3,1/3)=\pi$π P = (1/3 × 0 + 1/3 × 0,5 + 1/3 × 0,5, …) = (1/3, 1/3, 1/3) = π ✓.

Applications

Réseaux sociaux

Identification d'utilisateurs influents, détection de communautés.

Internet

PageRank, recommandation, routage.

Biologie

Réseaux de protéines, propagation d'épidémies.

Économie

Réseaux commerciaux, transferts entre secteurs.

Transport

Optimisation de tournées, gestion du trafic.

Erreurs fréquentes à éviter

• Confondre $A$A et $P$P : $A$A est binaire (ou poids), $P$P est probabiliste.
• Mauvaise normalisation : la somme des lignes de $P$P doit faire $1$1.
• Confondre vecteur ligne et colonne dans les calculs.
• Croire qu'une distribution stationnaire existe toujours : il faut connexité et apériodicité.

FAQ — Graphes et marches aléatoires

À quoi sert l'étude des graphes ?

À modéliser des réseaux : sociaux, biologiques, informatiques, transports, électriques…

Comment Google utilise les marches aléatoires ?

L'algorithme PageRank classe les pages web par la probabilité stationnaire d'une marche aléatoire sur le Web.

Pourquoi la « téléportation » dans PageRank ?

Pour assurer que la marche ne reste pas piégée et que la distribution stationnaire existe.

À quelle vitesse converge une marche aléatoire ?

Cela dépend du « gap spectral » de la matrice $P$P : plus il est grand, plus la convergence est rapide.