15.2 Graphe de Barabási-Albert
205
Démonstration. Comme dans la remarque 15.5, on code l’évolution de la suite
des degrés (sans souci de la structure de graphe sous-jacente) par un modèle
d’urne. Au temps k, on décide d’une coloration parallèle : les 2k − 1 boules
de couleur inférieure à k sont blanches tandis que la 2k-ième est argentée. Au
temps n > k, on ne suit que l’évolution des boules de ces couleurs là. Elle
correspond à une urne de Pólya avec une composition initiale de a = 1 et
b = 2k − 1. On peut utiliser alors le théorème 15.2.
Théorème 15.7 (Loi de puissance à degré fixé). Pour tous n, d 1, si
N (n, d) désigne le nombre de sites de degré d au temps n dans le graphe
aléatoire à attachement préférentiel de Barabási-Albert à n sites, alors
lim
n→∞
E
N (n, d)
n
=
4
d(d + 1)(d + 2)
.
Ainsi, dans un très grand graphe à attachement préférentiel (n 1), la
probabilité qu’une arête soit de degré d a une décroissance polynomiale en
d
−3 quand d → ∞. La queue lourde de la loi du degré moyen est liée à la
présence, due au renforcement, de sites fortement connectés.
Démonstration. La suite (N (n, ·)) n1 est une chaîne de Markov. Conditionnellement à N (n, ·), pour créer un nouveau site de degré d, il faut ajouter une arête à un site de degré d − 1, ce qui se produit avec probabilité
(d − 1)N (n, d − 1)/(2n), tandis qu’un site de degré d disparaît si on lui ajoute
une arête, ce qui se produit avec probabilité dN (n, d)/(2n). Enfin, un site de
degré 1 est créé à chaque étape par construction. Aussi, le nombre moyen
m n (d) := E(N (n, d)) de sites de degré d au temps n vérifie une équation de
récurrence linéaire, qualifiée d’équation maîtresse par Dorogovstev, Mendes,
et Samukhin : pour tout n, d 1 :
m n+1 (d) − m n (d) = −
d
2n
m n (d) +
d − 1
2n
m n (d − 1) + 1 d=1 ,
avec pour condition initiale m 1 = 1 d=2 . Pour d = 1, l’équation s’écrit
m n+1 (1) = c +
1 −
b
n
m n (1) avec c = 1 et b = 1/2,
ce qui donne
m n+1 (1) = c +
1 −
b
n
c +
1 −
b
n
1 −
b
n − 1
m n−1 (1)
= c
n
k=1
n
j=k+1
1 −
b
j
+ m 1 (1)
=0
n
k=1
1 −
b
k
.
la loi de Poisson Poi(λ) si np → λ quand n → ∞. Or si X ∼ Poi(λ) alors on a
P(X r) C exp(−cr log(r)) pour r 1 où c > 0 et C > 0 sont des constantes.
205
Démonstration. Comme dans la remarque 15.5, on code l’évolution de la suite
des degrés (sans souci de la structure de graphe sous-jacente) par un modèle
d’urne. Au temps k, on décide d’une coloration parallèle : les 2k − 1 boules
de couleur inférieure à k sont blanches tandis que la 2k-ième est argentée. Au
temps n > k, on ne suit que l’évolution des boules de ces couleurs là. Elle
correspond à une urne de Pólya avec une composition initiale de a = 1 et
b = 2k − 1. On peut utiliser alors le théorème 15.2.
Théorème 15.7 (Loi de puissance à degré fixé). Pour tous n, d 1, si
N (n, d) désigne le nombre de sites de degré d au temps n dans le graphe
aléatoire à attachement préférentiel de Barabási-Albert à n sites, alors
lim
n→∞
E
N (n, d)
n
=
4
d(d + 1)(d + 2)
.
Ainsi, dans un très grand graphe à attachement préférentiel (n 1), la
probabilité qu’une arête soit de degré d a une décroissance polynomiale en
d
−3 quand d → ∞. La queue lourde de la loi du degré moyen est liée à la
présence, due au renforcement, de sites fortement connectés.
Démonstration. La suite (N (n, ·)) n1 est une chaîne de Markov. Conditionnellement à N (n, ·), pour créer un nouveau site de degré d, il faut ajouter une arête à un site de degré d − 1, ce qui se produit avec probabilité
(d − 1)N (n, d − 1)/(2n), tandis qu’un site de degré d disparaît si on lui ajoute
une arête, ce qui se produit avec probabilité dN (n, d)/(2n). Enfin, un site de
degré 1 est créé à chaque étape par construction. Aussi, le nombre moyen
m n (d) := E(N (n, d)) de sites de degré d au temps n vérifie une équation de
récurrence linéaire, qualifiée d’équation maîtresse par Dorogovstev, Mendes,
et Samukhin : pour tout n, d 1 :
m n+1 (d) − m n (d) = −
d
2n
m n (d) +
d − 1
2n
m n (d − 1) + 1 d=1 ,
avec pour condition initiale m 1 = 1 d=2 . Pour d = 1, l’équation s’écrit
m n+1 (1) = c +
1 −
b
n
m n (1) avec c = 1 et b = 1/2,
ce qui donne
m n+1 (1) = c +
1 −
b
n
c +
1 −
b
n
1 −
b
n − 1
m n−1 (1)
= c
n
k=1
n
j=k+1
1 −
b
j
+ m 1 (1)
=0
n
k=1
1 −
b
k
.
la loi de Poisson Poi(λ) si np → λ quand n → ∞. Or si X ∼ Poi(λ) alors on a
P(X r) C exp(−cr log(r)) pour r 1 où c > 0 et C > 0 sont des constantes.