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

Dans mon nom je trouve "a" (dans Marine) pour L1 et "b" (dans Bayet) pour L2. Pour pouvoir avoir L1 différent de L2, je ne prends pas deux fois la lettre "a" même si c'est celle qui apparaît en premier et en dernier dans mon nom complet.

Je supprime le lien allant de "a" à "b" et rajoute un lien de "e" vers "b".

Graphe

I. J'identifie plusieurs composantes fortement connexes :

• l'ensemble de nœud {g,h}
• l'ensemble de nœud {a,d,f}
• l'ensemble de nœud {e,b}
• le nœud {c} isolé, il n'a pas de relations de forte connexité avec d'autres nœuds

Identification des composantes fortement connexes

II. Voici les matrices de calcul de la centralité des vecteurs propres par multiplication matricielle, où A = matrice d'adjacence du graphe et M = matrice qui représente le système linéaire.

$A={\begin{pmatrix}0&0&1&1&0&0&0&0\\0&0&1&0&1&0&0&0\\0&0&0&0&0&0&1&1\\0&0&1&0&0&1&0&0\\1&1&0&0&0&0&0&0\\1&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\end{pmatrix}}$

$M={\begin{pmatrix}0&0&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0\\0&0&0&0&0&0&{\tfrac {1}{2}}&{\tfrac {1}{2}}\\0&0&{\tfrac {1}{2}}&0&0&{\tfrac {1}{2}}&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&0&0&0&0&0\\1&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\end{pmatrix}}$

$M^{T}={\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}$

En allant plus loin, nous pouvons 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

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}pa\\pb\\pc\\pd\\pe\\pf\\pg\\ph\end{pmatrix}}$

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {3}{16}}\end{pmatrix}}$

Deuxième distribution de matière

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {3}{16}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {3}{32}}\\{\tfrac {1}{32}}\\{\tfrac {5}{32}}\\{\tfrac {3}{32}}\\{\tfrac {1}{32}}\\{\tfrac {1}{32}}\\{\tfrac {9}{32}}\\{\tfrac {9}{32}}\end{pmatrix}}$

III. Soit s le coefficient de calibrage = 0,9 et N le nombre de nœuds = 8

a) Initialisation de la matière : je prends 1 comme matière de départ. Je répartis cette matière de manière égale entre les 8 nœuds du graphe. Chacun des 8 nœuds débute alors avec une densité de 1/8.

La matrice suivante est obtenue :

Répartition de la matière entre les 8 nœuds

${\begin{pmatrix}pa\\pb\\pc\\pd\\pe\\pf\\pg\\ph\end{pmatrix}}={\begin{pmatrix}{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\end{pmatrix}}$

b) Première itération par calcul matricriel :

Première distribution de matière

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}pa\\pb\\pc\\pd\\pe\\pf\\pg\\ph\end{pmatrix}}$

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\\{\tfrac {1}{8}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {3}{16}}\end{pmatrix}}$

Multiplication de la matière dans chaque nœud par s = 0,9 :

Mutilplication de la matrice par 0,9

${\begin{pmatrix}{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {1}{16}}\\{\tfrac {3}{16}}\\{\tfrac {3}{16}}\end{pmatrix}}\cdot 0,9={\begin{pmatrix}{\tfrac {27}{160}}\\{\tfrac {9}{160}}\\{\tfrac {27}{160}}\\{\tfrac {9}{160}}\\{\tfrac {9}{160}}\\{\tfrac {9}{160}}\\{\tfrac {27}{160}}\\{\tfrac {27}{160}}\end{pmatrix}}$

Partage de s - 1 = 0,9 - 1 = 0,1 de la matière totale entre tous les nœuds. La matière totale est de 1, je dois partager 1/10 de la matière totale. Il y a 8 nœuds dans le graphe. Je dois donc rajouter 1/80 de matière dans chaque nœud.

Partage de 0,1 de la matière totale entre tous les nœuds

${\begin{pmatrix}{\tfrac {27}{160}}\\{\tfrac {9}{160}}\\{\tfrac {27}{160}}\\{\tfrac {9}{160}}\\{\tfrac {9}{160}}\\{\tfrac {9}{160}}\\{\tfrac {27}{160}}\\{\tfrac {27}{160}}\end{pmatrix}}+{\begin{pmatrix}{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {29}{160}}\\{\tfrac {11}{160}}\\{\tfrac {29}{160}}\\{\tfrac {11}{160}}\\{\tfrac {11}{160}}\\{\tfrac {11}{160}}\\{\tfrac {29}{160}}\\{\tfrac {29}{160}}\end{pmatrix}}$

Vérification que le total de la matière = 1 : 29/160 + 11/160 + 29/160 + 11/160 + 11/160 + 11/160 + 29/160 + 29/160 = 1

c) Deuxième itération :

${\begin{pmatrix}0&0&0&0&{\tfrac {1}{2}}&1&0&0\\0&0&0&0&{\tfrac {1}{2}}&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0&0&0&0\\{\tfrac {1}{2}}&0&0&0&0&0&0&0\\0&{\tfrac {1}{2}}&0&0&0&0&0&0\\0&0&0&{\tfrac {1}{2}}&0&0&0&0\\0&0&{\tfrac {1}{2}}&0&0&0&0&1\\0&0&{\tfrac {1}{2}}&0&0&0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}{\tfrac {29}{160}}\\{\tfrac {11}{160}}\\{\tfrac {29}{160}}\\{\tfrac {11}{160}}\\{\tfrac {11}{160}}\\{\tfrac {11}{160}}\\{\tfrac {29}{160}}\\{\tfrac {29}{160}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {33}{320}}\\{\tfrac {11}{320}}\\{\tfrac {51}{320}}\\{\tfrac {29}{320}}\\{\tfrac {11}{320}}\\{\tfrac {11}{320}}\\{\tfrac {87}{320}}\\{\tfrac {87}{320}}\end{pmatrix}}$

${\begin{pmatrix}{\tfrac {33}{320}}\\{\tfrac {11}{320}}\\{\tfrac {51}{320}}\\{\tfrac {29}{320}}\\{\tfrac {11}{320}}\\{\tfrac {11}{320}}\\{\tfrac {87}{320}}\\{\tfrac {87}{320}}\end{pmatrix}}\cdot 0,9+{\begin{pmatrix}{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\\{\tfrac {1}{80}}\end{pmatrix}}={\begin{pmatrix}{\tfrac {337}{3200}}\\{\tfrac {139}{3200}}\\{\tfrac {499}{3200}}\\{\tfrac {301}{3200}}\\{\tfrac {139}{3200}}\\{\tfrac {139}{3200}}\\{\tfrac {823}{3200}}\\{\tfrac {823}{3200}}\end{pmatrix}}$

Vérification que le total de la matière = 1 : 337/3200 + 139/3200 + 499/3200 + 301/3200 + 139/3200 + 139/3200 + 823/3200 + 823/3200 = 1

La matière totale reste égale à 1 et est donc constante