15.2 Graphe de Barabási-Albert
203
Remarque 15.4 (Matrice de remise). Soit A = (a i,j ) 1i,jk une matrice
k × k de nombres entiers. Considérons une urne de Pólya généralisée à k
couleurs qui évolue comme suit : on tire une boule au hasard dans l’urne, on
repère sa couleur, notée i, puis on remet dans l’urne a i,j boules de couleur j
pour tout 1 j k. On dit que A est la matrice de remise de l’urne. Pour
l’urne de Pólya standard que nous avons étudiée on a k = 2 et A = 2I 2 .
15.2 Graphe de Barabási-Albert
Les graphes aléatoires permettent de modéliser un certain nombre de phénomènes naturels, comme les structures d’amitié dans les réseaux sociaux, les
structures des liens entre pages dans le World Wide Web, les structures de
collaboration dans les productions artistiques et scientifiques, les structures de
régulation entre protéines, les liaisons entre machines dans le réseau Internet,
etc. Les arbres de type Galton-Watson du chapitre 3 constituent un modèle de
graphe aléatoire adapté aux structures de filiations. Le modèle le plus célèbre
et le plus simple de graphe aléatoire est sans doute celui de Erdős-Rényi, évoqué dans le chapitre 16 : il se construit récursivement en ajoutant un nouveau
site puis en tirant à pile ou face de manière indépendante sa connexion avec
chacun des sites existants. Ce modèle ne colle pas avec la réalité de graphes
aléatoires sociaux, pour lesquels les nouveaux sites se connectent préférentiellement aux sites existants les plus importants au sens de la connectivité
(degré). Il y a là une instance du phénomène de renforcement dont il faut
tenir compte spécifiquement.
Le graphe aléatoire à attachement préférentiel de Barabási-Albert est défini
de la manière suivante : au temps n 1, le graphe contient n sites (sommets)
et un certain nombre de liens non orientés (arêtes) entre ces sites (voir la
figure 15.2). Le degré d’un sommet est le nombre d’arêtes pointant vers ce
sommet. Au temps n = 1, le site 1 est relié à lui même. Cette initialisation
assure de belles formules, mais n’a rien de canonique, et d’autres initialisations
sont possibles. Le degré du site 1 à l’instant 1 est donc 2. Pour faire évoluer
récursivement le graphe, du temps n au temps n + 1, on considère les degrés
d n,1 , . . . , d n,n des n sites du graphe au temps n, et la loi de probabilité associée
p n,k =
d n,k
d n,1 + · · · + d n,n
,
puis on connecte le nouveau site n + 1 à un site choisi aléatoirement et indépendamment parmi les n sites existants, avec la loi de probabilité p n,· . Avec
ce mécanisme, on obtient d 1,1 = 2, d 2,1 = 3, d 2,2 = 1, et pour tout n 1,
d n,1 + · · · + d n,n = 2n (soit n arêtes).
Remarque 15.5 (Urne). On peut réaliser cette construction de la suite
(d n,· ) n1 (en perdant la géométrie du graphe) comme un modèle d’urne de
Pólya généralisée : au temps n 1 l’urne contient 2n boules dont les couleurs
203
Remarque 15.4 (Matrice de remise). Soit A = (a i,j ) 1i,jk une matrice
k × k de nombres entiers. Considérons une urne de Pólya généralisée à k
couleurs qui évolue comme suit : on tire une boule au hasard dans l’urne, on
repère sa couleur, notée i, puis on remet dans l’urne a i,j boules de couleur j
pour tout 1 j k. On dit que A est la matrice de remise de l’urne. Pour
l’urne de Pólya standard que nous avons étudiée on a k = 2 et A = 2I 2 .
15.2 Graphe de Barabási-Albert
Les graphes aléatoires permettent de modéliser un certain nombre de phénomènes naturels, comme les structures d’amitié dans les réseaux sociaux, les
structures des liens entre pages dans le World Wide Web, les structures de
collaboration dans les productions artistiques et scientifiques, les structures de
régulation entre protéines, les liaisons entre machines dans le réseau Internet,
etc. Les arbres de type Galton-Watson du chapitre 3 constituent un modèle de
graphe aléatoire adapté aux structures de filiations. Le modèle le plus célèbre
et le plus simple de graphe aléatoire est sans doute celui de Erdős-Rényi, évoqué dans le chapitre 16 : il se construit récursivement en ajoutant un nouveau
site puis en tirant à pile ou face de manière indépendante sa connexion avec
chacun des sites existants. Ce modèle ne colle pas avec la réalité de graphes
aléatoires sociaux, pour lesquels les nouveaux sites se connectent préférentiellement aux sites existants les plus importants au sens de la connectivité
(degré). Il y a là une instance du phénomène de renforcement dont il faut
tenir compte spécifiquement.
Le graphe aléatoire à attachement préférentiel de Barabási-Albert est défini
de la manière suivante : au temps n 1, le graphe contient n sites (sommets)
et un certain nombre de liens non orientés (arêtes) entre ces sites (voir la
figure 15.2). Le degré d’un sommet est le nombre d’arêtes pointant vers ce
sommet. Au temps n = 1, le site 1 est relié à lui même. Cette initialisation
assure de belles formules, mais n’a rien de canonique, et d’autres initialisations
sont possibles. Le degré du site 1 à l’instant 1 est donc 2. Pour faire évoluer
récursivement le graphe, du temps n au temps n + 1, on considère les degrés
d n,1 , . . . , d n,n des n sites du graphe au temps n, et la loi de probabilité associée
p n,k =
d n,k
d n,1 + · · · + d n,n
,
puis on connecte le nouveau site n + 1 à un site choisi aléatoirement et indépendamment parmi les n sites existants, avec la loi de probabilité p n,· . Avec
ce mécanisme, on obtient d 1,1 = 2, d 2,1 = 3, d 2,2 = 1, et pour tout n 1,
d n,1 + · · · + d n,n = 2n (soit n arêtes).
Remarque 15.5 (Urne). On peut réaliser cette construction de la suite
(d n,· ) n1 (en perdant la géométrie du graphe) comme un modèle d’urne de
Pólya généralisée : au temps n 1 l’urne contient 2n boules dont les couleurs