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 = ${\begin{Bmatrix}1/8\\1/8\\1/8\\1/8\\1/8\\1/8\\1/8\\1/8\end{Bmatrix}}$

En faisant une première itération pour la distribution de matière (Mt * V0) on obtient :

Mt *V0 = V1${\begin{Bmatrix}3/16\\1/16\\1/4\\1/16\\0\\1/16\\3/16\\3/16\end{Bmatrix}}$

Puis on multiplie la matière de chaque nœud par 0.9 :

V1*9/10 = V2 ${\begin{Bmatrix}27/160\\9/160\\9/40\\9/160\\0\\9/160\\27/160\\27/160\end{Bmatrix}}$

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 ${\begin{Bmatrix}29/160\\11/160\\19/80\\11/160\\1/80\\11/160\\29/160\\29/160\end{Bmatrix}}$

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${\begin{Bmatrix}3/40\\29/320\\7/64\\29/320\\0\\11/320\\3/10\\3/10\end{Bmatrix}}$

On multiplie une seconde fois par s = 0.9 en redistribuant 0.1 de la matière totale :

V4*9/10 = ${\begin{Bmatrix}27/400\\261/3200\\63/640\\261/3200\\0\\99/3200\\27/100\\27/100\end{Bmatrix}}$ + V0 * 1/10 = ${\begin{Bmatrix}2/25\\301/3200\\71/640\\301/3200\\1/80\\139/3200\\113/400\\113/400\end{Bmatrix}}$

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.