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

L1 = a

L2 = b

Graphe

I. Identifiez les composantes fortement connexes

Nous avons comme composantes fortement connexes, c’est-à-dire les groupes de noeuds où il y a un chemin entre tous :

{a,d,f} ; {c}; {g,h} ; {e,b}

II. Construisez la matrice pour le calcul de la centralité de vecteur propre par multiplication matricielle, comme proposé dans les diapos.

$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}}$

${\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}pa\\pb\\pc\\pd\\pe\\pf\\pg\\ph\end{pmatrix}}$

III. Nous réalisions la première itération avec le calcul matriciel. La matière de départ pour chaque noeud est de 1/8, c’est-à-dire de 1 partagé entre chaque noeud. Ce qui nous donne :

${\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}}$

Ce qui nous donne comme résultat :

${\begin{pmatrix}pa\\pb\\pc\\pd\\pe\\pf\\pg\\ph\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}}$

Ensuite, nous multiplions chaque noeud par 0,9, ce qui donne :

${\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}}$

Enfin, nous rajoutons 0,1 de matière dans l'ensemble du réseau, ce qui fait 1/80 pour chaque noeud. Cela nous donne :

${\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}}$

Nous ajoutons maintenant les matières de chaque noeud. Nous trouvons : 29/160 + 11/160 + 29/160 + 11/160 + 11/160 + 11/160 + 29/160 + 29/160 = 160/160, ce qui fait bien 1. La matière totale reste donc bien constante.

Procédons maintenant à la 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}}$

Ce qui nous donne :

$V_{2}={\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}}$

Nous multiplions maintenant le résultat par 9/10 et partageons la matière restante de manière égale entre tous les noeuds :

$V_{2}={\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 {\frac {9}{10}}+{\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}}\cdot {\frac {1}{10}}$

Nous avons donc comme résultat final :

$V_{2}=={\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}}$

En ajoutant la matière de chaque noeud, nous retrouvons encore un total d'1, donc la matière totale reste constante.