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 noeud {g,h}
l'ensemble de noeud {a,d,f}
l'ensemble de noeud {e,b}
le noeud {c} isolé, il n'a pas de relations de forte connexité avec d'autres noeuds 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 = ( 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}}} 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
( 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}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}}} ( 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 ) = ( 3 16 1 16 3 16 1 16 1 16 1 16 3 16 3 16 ) {\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 {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
( 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 ) ⋅ ( 3 16 1 16 3 16 1 16 1 16 1 16 3 16 3 16 ) = ( 3 32 1 32 5 32 3 32 1 32 1 32 9 32 9 32 ) {\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 {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 noeuds = 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 noeuds du graphe. Chacun des 8 noeuds débute alors avec une densité de 1/8.
La matrice suivante est obtenue :
Répartition de la matière entre les 8 noeuds
( p a p b p c p d p e p f p g p h ) = ( 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}{\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
( 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}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}}} ( 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 ) = ( 3 16 1 16 3 16 1 16 1 16 1 16 3 16 3 16 ) {\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 {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 noeud par s = 0,9 :
Mutilplication de la matrice par 0,9
( 3 16 1 16 3 16 1 16 1 16 1 16 3 16 3 16 ) ⋅ 0 , 9 = ( 27 160 9 160 27 160 9 160 9 160 9 160 27 160 27 160 ) {\displaystyle {\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 noeuds. La matière totale est de 1, je dois partager 1/10 de la matière totale. Il y a 8 noeuds dans le graphe. Je dois donc rajouter 1/80 de matière dans chaque noeud.
Partage de 0,1 de la matière totale entre tous les noeuds
( 27 160 9 160 27 160 9 160 9 160 9 160 27 160 27 160 ) + ( 1 80 1 80 1 80 1 80 1 80 1 80 1 80 1 80 ) = ( 29 160 11 160 29 160 11 160 11 160 11 160 29 160 29 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}}+{\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 :
( 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 ) = ( 33 320 11 320 51 320 29 320 11 320 11 320 87 320 87 320 ) {\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}}={\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}}} ( 33 320 11 320 51 320 29 320 11 320 11 320 87 320 87 320 ) ⋅ 0 , 9 + ( 1 80 1 80 1 80 1 80 1 80 1 80 1 80 1 80 ) = ( 337 3200 139 3200 499 3200 301 3200 139 3200 139 3200 823 3200 823 3200 ) {\displaystyle {\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