204
15 Renforcement
peuvent aller de 1 à n, on tire alors une boule au hasard, et si k est sa couleur, on remet dans l’urne 2 boules de couleur k ainsi qu’une boule nouvelle de
couleur n + 1 ce qui correspond à renforcer le site de couleur k et à introduire
un nouveau site de couleur n + 1, autrement dit le graphe gagne un sommet
(n + 1) et une arête (k ↔ n + 1).
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Fig. 15.2. Réalisation d’un graphe à attachement préférentiel de Barabási-Albert.
Si l’on omet l’arête reliant 1 à lui-même, le graphe à attachement préférentiel de Barabási-Albert n’a pas de cycles : c’est un arbre.
Théorème 15.6 (Loi de puissance). Fixons k 1. Soit d n,k le degré du site
k dans le graphe aléatoire à attachement préférentiel de Barabási-Albert à n
sites avec n k. Alors la proportion d n,k /(d n,1 + · · · + d n,k ) converge presque
sûrement quand n → ∞ vers une variable aléatoire de loi Beta de paramètre
(1, 2k − 1) sur [0, 1] de densité u ∈ [0, 1] → (2k − 1)(1 − x)
2(k−1) .
La loi de puissance qui apparaît dans ce modèle à attachement préférentiel
correspond bien aux réseaux sociaux réels, et diffère du comportement sousexponentiel de la loi de Poisson des modèles de graphes aléatoires de ErdősRényi à attachement non préférentiel
2 .
2. Dans un graphe de Erdős-Rényi de paramètre (n, p), chaque sommet possède
un nombre de voisins aléatoire de loi binomiale Bin(n − 1, p), qui converge vers