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

Mon nom est Antoine Thomann. Soit L1 = A et L2 = H.
J'ai décidé de retirer le lien allant de A vers D, et de rajouter un lien allant de H vers C.

Représentation du graphe

Question n°1

J'identifie les composantes connexes suivantes :

• [A, B, E]
  
• [C, G, H]
  
• [D]
  
• [F]

Question n°2

La matrice initiale A est la suivante :

$A=\left(\begin{array}{cccccccc}0& 1& 1& 0& 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& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0\end{array}\right)$

La matrice distribuée est la suivante :

$M=\left(\begin{array}{cccccccc}0& \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0\\ 0& 0& \left(\frac{1}{2}\right)& 0& \left(\frac{1}{2}\right)& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& \left(\frac{1}{2}\right)& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& \left(\frac{1}{2}\right)& 0\end{array}\right)$

La matrice transposée est la suivante :

$MT=\left(\begin{array}{cccccccc}0& 0& 0& 0& 1& 1& 0& 0\\ \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0& 0\\ \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)& 0& \left(\frac{1}{2}\right)& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 1& 0\end{array}\right)$

La centralité du vecteur propre s'obtient grâce à la multiplication de MT par la densité de matière de chaque nœud:

$\left(\begin{array}{c}{P}^{\prime }A\\ P^{\prime }B\\ P^{\prime }C\\ P^{\prime }D\\ P^{\prime }E\\ P^{\prime }F\\ P^{\prime }G\\ P^{\prime }H\end{array}\right)=\left(\begin{array}{cccccccc}0& 0& 0& 0& 1& 1& 0& 0\\ \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0& 0\\ \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)& 0& \left(\frac{1}{2}\right)& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 1& 0\end{array}\right)\ast \left(\begin{array}{c}PA\\ PB\\ PC\\ PD\\ PE\\ PF\\ PG\\ PH\end{array}\right)$

Question n°3

Détermination de la densité de matière

On distribue une matière m=1 entre les différents nœuds :

$\left(\begin{array}{c}PA\\ PB\\ PC\\ PD\\ PE\\ PF\\ PG\\ PH\end{array}\right)=\left(\begin{array}{c}\left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\end{array}\right)$

Première itération

Pour la première itération, on a :

$i1=MT\ast PI=\left(\begin{array}{cccccccc}0& 0& 0& 0& 1& 1& 0& 0\\ \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0& 0\\ \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)& 0& \left(\frac{1}{2}\right)& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 1& 0\end{array}\right)\ast \left(\begin{array}{c}\left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{1}{8}\right)\end{array}\right)=\left(\begin{array}{c}\left(\frac{1}{4}\right)\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{4}\right)\\ 0\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{3}{16}\right)\end{array}\right)$

On multiplie ensuite par s=0,9 :

$\left(\begin{array}{c}\left(\frac{1}{4}\right)\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{4}\right)\\ 0\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{16}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{3}{16}\right)\end{array}\right)\ast 0,9=\left(\begin{array}{c}\left(\frac{9}{40}\right)\\ \left(\frac{9}{160}\right)\\ \left(\frac{9}{40}\right)\\ 0\\ \left(\frac{9}{160}\right)\\ \left(\frac{9}{160}\right)\\ \left(\frac{9}{80}\right)\\ \left(\frac{27}{160}\right)\end{array}\right)$

On distribue ensuite s-1=0,1 entre les différents nœuds, soit $\left(\frac{1}{80}\right)$ à ajouter pour chaque nœud :

$\left(\begin{array}{c}\left(\frac{19}{80}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{19}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{29}{160}\right)\end{array}\right)$

On vérifie ensuite si la matière reste constante :

$pi1=\left(\frac{19}{80}\right)+\left(\frac{11}{160}\right)+\left(\frac{19}{80}\right)+\left(\frac{1}{80}\right)+\left(\frac{11}{160}\right)+\left(\frac{11}{160}\right)+\left(\frac{1}{8}\right)+\left(\frac{29}{160}\right)=1$

Ainsi, la matière reste constante.

Seconde itération

Pour la seconde itération, on a :

$i2=MT\ast i1=\left(\begin{array}{cccccccc}0& 0& 0& 0& 1& 1& 0& 0\\ \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0& 0\\ \left(\frac{1}{2}\right)& \left(\frac{1}{2}\right)& 0& \left(\frac{1}{2}\right)& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 0& \left(\frac{1}{2}\right)\\ 0& 0& \left(\frac{1}{2}\right)& 0& 0& 0& 1& 0\end{array}\right)\ast \left(\begin{array}{c}\left(\frac{19}{80}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{19}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{11}{160}\right)\\ \left(\frac{1}{8}\right)\\ \left(\frac{29}{160}\right)\end{array}\right)=\left(\begin{array}{c}\left(\frac{11}{80}\right)\\ \left(\frac{19}{160}\right)\\ \left(\frac{1}{4}\right)\\ 0\\ \left(\frac{11}{320}\right)\\ \left(\frac{1}{160}\right)\\ \left(\frac{67}{320}\right)\\ \left(\frac{39}{160}\right)\end{array}\right)$

On multiplie ensuite par s=0,9 :

$\left(\begin{array}{c}\left(\frac{11}{80}\right)\\ \left(\frac{19}{160}\right)\\ \left(\frac{1}{4}\right)\\ 0\\ \left(\frac{11}{320}\right)\\ \left(\frac{1}{160}\right)\\ \left(\frac{67}{320}\right)\\ \left(\frac{39}{160}\right)\end{array}\right)\ast 0,9=\left(\begin{array}{c}\left(\frac{99}{800}\right)\\ \left(\frac{171}{1600}\right)\\ \left(\frac{9}{40}\right)\\ 0\\ \left(\frac{99}{3200}\right)\\ \left(\frac{9}{1600}\right)\\ \left(\frac{603}{3200}\right)\\ \left(\frac{351}{1600}\right)\end{array}\right)$

On distribue ensuite s-1=0,1 entre les différents nœuds, soit $\left(\frac{1}{80}\right)$ à ajouter pour chaque nœud :

$\left(\begin{array}{c}\left(\frac{109}{800}\right)\\ \left(\frac{191}{1600}\right)\\ \left(\frac{19}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{139}{3200}\right)\\ \left(\frac{29}{1600}\right)\\ \left(\frac{643}{3200}\right)\\ \left(\frac{371}{1600}\right)\end{array}\right)$

On vérifie ensuite si la matière reste constante :

$pi2=\left(\frac{109}{800}\right)+\left(\frac{191}{1600}\right)+\left(\frac{19}{80}\right)+\left(\frac{1}{80}\right)+\left(\frac{139}{3200}\right)+\left(\frac{29}{1600}\right)+\left(\frac{643}{3200}\right)+\left(\frac{371}{1600}\right)=1$

Ainsi, on observe que la matière reste constante.

Question bonus

On pourrait la représenter ainsi :

$0,9\ast VM+\left(\begin{array}{c}\left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\\ \left(\frac{1}{80}\right)\end{array}\right)$