Utilisateur:Auriane SIREN/Modélisation des Réseaux (M1 SIREN, 2020)/Activité E

Une page de Wikiversité, la communauté pédagogique libre.
Aller à la navigation Aller à la recherche

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.

Graphe modifié.jpg


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.