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 = ( 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 ) {\displaystyle 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 = ( 0 0 1 2 1 2 0 0 0 0 0 0 1 2 0 1 2 0 0 0 0 0 0 0 0 0 1 2 1 2 0 0 1 2 0 0 1 2 0 0 1 2 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 ) {\displaystyle 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 = ( 0 0 0 0 1 2 1 0 0 0 0 0 0 1 2 0 0 0 1 2 1 2 0 1 2 0 0 0 0 1 2 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 0 0 1 0 ) {\displaystyle 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}}}
( p a p b p c p d p e p f p g p h ) = ( 0 0 0 0 1 2 1 0 0 0 0 0 0 1 2 0 0 0 1 2 1 2 0 1 2 0 0 0 0 1 2 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 0 0 1 0 ) ⋅ ( p a p b p c p d p e p f p g p h ) {\displaystyle {\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 :
( p a p b p c p d p e p f p g p h ) = ( 0 0 0 0 1 2 1 0 0 0 0 0 0 1 2 0 0 0 1 2 1 2 0 1 2 0 0 0 0 1 2 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 0 0 1 0 ) ⋅ ( 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 ) {\displaystyle {\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 :
( p a p b p c p d p e p f p g p h ) = ( 3 16 1 16 3 16 1 16 1 16 1 16 3 16 3 16 ) {\displaystyle {\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 :
( 27 160 9 160 27 160 9 160 9 160 9 160 27 160 27 160 ) {\displaystyle {\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 :
( 29 160 11 160 29 160 11 160 11 160 11 160 29 160 29 160 ) {\displaystyle {\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.
( 0 0 0 0 1 2 1 0 0 0 0 0 0 1 2 0 0 0 1 2 1 2 0 1 2 0 0 0 0 1 2 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 0 0 1 0 ) ⋅ ( 29 160 11 160 29 160 11 160 11 160 11 160 29 160 29 160 ) {\displaystyle {\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 = ( 33 320 11 320 51 320 29 320 11 320 11 320 87 320 87 320 ) {\displaystyle 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 = ( 33 320 11 320 51 320 29 320 11 320 11 320 87 320 87 320 ) ⋅ 9 10 + ( 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 ) ⋅ 1 10 {\displaystyle 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 == ( 337 3200 139 3200 499 3200 301 3200 139 3200 139 3200 823 3200 823 3200 ) {\displaystyle 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.