Utilisateur:Auriane SIREN/Modélisation des Réseaux (M1 SIREN, 2020)/Activité E
La première lettre qui apparaît dans mon prénom est "a" et la dernière dans mon nom est "c". On prend donc L1 = a et L2 = c.
Je supprime le lien allant de a à c et j'ajoute un lien allant de e à c.
I. Composantes fortement connexes
J'identifie deux composantes fortement connexes dans ce graphe :
- Entre les nœuds G et H
- Entre les nœuds A-D-F
Les nœuds B-C-E sont isolés.
II. Calcul de la centralité du vecteur propre
On commence par calculer la matrice d'adjacence du graphe où la densité de matière est égale à 1 :
A | B | C | D | E | F | G | H | |
---|---|---|---|---|---|---|---|---|
A | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
B | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
D | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
E | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
F | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
H | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Puis on calcule la matrice d'adjacence de la matière en répartissant la matière entre les nœuds :
A | B | C | D | E | F | G | H | |
---|---|---|---|---|---|---|---|---|
A | 0 | 1/2 | 0 | 1/2 | 0 | 0 | 0 | 0 |
B | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 0 | 0 | 0 | 1/2 | 1/2 |
D | 0 | 0 | 1/2 | 0 | 0 | 1/2 | 0 | 0 |
E | 1/2 | 0 | 1/2 | 0 | 0 | 0 | 0 | 0 |
F | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
H | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Enfin on obtient la matrice transposée Mt :
A | B | C | D | E | F | G | H | |
---|---|---|---|---|---|---|---|---|
A | 0 | 0 | 0 | 0 | 1/2 | 1 | 0 | 0 |
B | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
C | 0 | 1 | 0 | 1/2 | 1/2 | 0 | 0 | 0 |
D | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
F | 0 | 0 | 0 | 1/2 | 0 | 0 | 0 | 0 |
G | 0 | 0 | 1/2 | 0 | 0 | 0 | 0 | 1 |
H | 0 | 0 | 1/2 | 0 | 0 | 0 | 1 | 0 |
III. Calculer deux itérations de PageRank
Le vecteur initial de matière sera :
V0 =
En faisant une première itération pour la distribution de matière (Mt * V0) on obtient :
Mt *V0 = V1
Puis on multiplie la matière de chaque nœud par 0.9 :
V1*9/10 = V2
Puis on partage 0.1 de la matière totale entre chaque nœud soit un ajout de 1/80 de matière à chaque nœud ce qui nous donne :
V2 + V0 * 1/10 = V3
Vérification que le total de la matière reste constant (c'est-à-dire égal à 1) = 29/160 + 11/160 + 19/80 + 11/160 + 1/80 + 11/160 + 29/160 + 29/160 = 1
Deuxième itération :
Résultat de la deuxième distribution de matière :
Mt * V3 = V4
On multiplie une seconde fois par s = 0.9 en redistribuant 0.1 de la matière totale :
V4*9/10 = + V0 * 1/10 =
On vérifie que le total de la matière reste constant : 2/25 + 301/3200 + 71/640 + 301/3200 + 1/80 + 139/3200 + 113/400 + 113/400 = 1
La matière totale reste donc bien constante.