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.