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

Une page de Wikiversité.
Aller à la navigation Aller à la recherche


Question I :

Graphe du réseau

Parmi les lettres a, b, c, d, e, f, g, h, la première lettre de mon nom est (e) et la dernière également (e) donc on pris (d) à la place : Quentin Bidone

On a donc retiré de L1 (e) un lien sortant (celui de e vers a) et on a ajouté un lien entrant à L2 (d) (celui de b vers d).

On identifie donc trois composantes fortement connexes :

- une entre les noeuds g et h

- une entre les noeuds a, b, c, d et f

- une au noeud e


Question II

Le calcul de la centralité du vecteur propre par multiplication matricielle correspond à

Avec Pj la densité de matière pour le noeud J et Mij la matrice représentant le système linéaire que l'on obtient en calculant la matrice d'adjacence du graphe sur la densité des noeuds.

Aussi pour écrire cette multiplication matricielle il faut procéder en trois étapes :

- D'abord créer la matrice d'adjacence du graphe en considérant que la somme de Pi (la densité de matière d'un noeud i)=1

A B C D E F G H
A 0 1 1 1 0 0 0 0
B 0 0 1 1 1 0 0 0
C 0 0 0 0 0 0 1 1
D 0 0 1 0 0 1 0 0
E 0 0 0 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

- Une fois cette matrice obtenue, on peut calculer la matrice de diffusion en sortie de la matière, M :

A B C D E F G H
A 0 0 0 0 0
B 0 0 0 0 0
C 0 0 0 0 0 0
D 0 0 0 0 0 0
E 0 0 0 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 en regardant chaque colonne de chaque noeud on obtient la matrice de diffusion en entrée de la matière, Mt :

A B C D E F G H
A 0 0 0 0 0 1 0 0
B 0 0 0 0 0 0 0
C 0 0 0 0 0
D 0 0 0 0 0 0
E 0 0 0 0 0 0 0
F 0 0 0 0 0 0 0
G 0 0 0 0 0 0 1
H 0 0 0 0 0 1 0

La centralité du vecteur propre est don égal à la matrice obtenue multipliée par la densité de matière des noeuds soit :


Avant de passer la suite, nous allons réaliser la distribution de la matière via 2 itérations pour ensuite pouvoir comparer la valeur quand on applique un coefficient s :

- première distribution de matière :

- deuxième distribution de matière :


Question III :

Je prends 1 comme matière et j'initialise :


Puis je fais une première itération :

a) Je multiplie la matière dans chaque noeud par 0,9 :

b) Je partage S-1 de matière entre tous les noeuds soit 0,9 - 1 = 0,1. La matière totale étant de 1, je dois partager entre tous les noeuds 1 * 0,1 = de matière. Sachant qu'il y a 8 noeuds, il faut donner à chaque noeud de matière soit :

c) Afin de vérifier que la matière est bien constante, il suffit de comparer la densité de matière obtenue à la quantité de matière de départ soit :

Le résultat ne correspond pas à 1 la matière ne reste donc pas constante. En effet le noeud E n'étant n'ayant aucune sortie, de la matière est perdue ici à chaque tour malgré la redistribution.


Faisons à présent la seconde itération de matière :

a) Je multiplie la matière dans chaque noeud par 0,9

b) Je partage S-1 de matière entre tous les noeuds soit 0,9 - 1 = 0,1. La matière totale étant de 1, je dois partager entre tous les noeuds 1 * 0,1 = de matière. Sachant qu'il y a 8 noeuds, il faut donner à chaque noeud de matière soit :

c) Afin de vérifier que la matière est bien constante, il suffit de comparer la densité de matière obtenue à la quantité de matière de départ soit :

Le résultat ne correspond pas à 1 la matière ne reste donc pas constante. A nouveau le noeud E n'étant n'ayant aucune sortie, de la matière est perdue ici à chaque tour malgré la redistribution.

Reprise de l'activité avec une diffusion dans tous les noeuds de la matière restée dans le noeud E[modifier | modifier le wikicode]

Afin de mieux respecter le principe de circulation, nous allons reprendre l'activité en considérant que le noeud E dispose d'un lien sortant vers tous les autres noeuds, afin d'éviter une perte de matière.

Ce nouveau paramètre intégré, la matrice de diffusion en entrée de la matière, Mt correspond à :

A B C D E F G H
A 0 0 0 0 1 0 0
B 0 0 0 0 0 0
C 0 0 0 0
D 0 0 0 0 0
E 0 0 0 0 0 0 0
F 0 0 0 0 0 0
G 0 0 0 0 0 1
H 0 0 0 0 1 0

La centralité du vecteur propre est don égal à la matrice obtenue multipliée par la densité de matière des noeuds soit :

Avant de passer la suite, nous allons réaliser la distribution de la matière via 2 itérations pour ensuite pouvoir comparer la valeur quand on applique un coefficient s

- première distribution de matière :


- deuxième distribution de matière :


Question III :

Je prends 1 comme matière et j'initialise :


Puis je fais une première itération :

a) Je multiplie la matière dans chaque noeud par 0,9 :

b) Je partage S-1 de matière entre tous les noeuds soit 0,9 - 1 = 0,1. La matière totale étant de 1, je dois partager entre tous les noeuds 1 * 0,1 = de matière. Sachant qu'il y a 8 noeuds, il faut donner à chaque noeud de matière soit :

c) Afin de vérifier que la matière est bien constante, il suffit de comparer la densité de matière obtenue à la quantité de matière de départ soit :

La matière est donc bien constante et à l'équilibre.

Faisons à présent la seconde itération de matière :


a) Je multiplie la matière dans chaque noeud par 0,9 :

b) Je partage S-1 de matière entre tous les noeuds soit 0,9 - 1 = 0,1. La matière totale étant de 1, je dois partager entre tous les noeuds 1 * 0,1 = de matière. Sachant qu'il y a 8 noeuds, il faut donner à chaque noeud de matière soit :

c) Afin de vérifier que la matière est bien constante, il suffit de comparer la densité de matière obtenue à la quantité de matière de départ soit :

La matière est donc bien constante et à l'équilibre.