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

Votre réseau

Considérez le graphe du diapo 24 de l'ensemble 3 :

• 

  Enlevez les nœuds "g" et "h".
• Parmi les lettres [a, b, c, d, e, f], prenez la première et la dernière qu'apparaissent dans votre nom complet. On va las appeler L1 et L2.
  • Par exemple, dans mon nom je trouve "a" (dans Alexandre) pour L1 et "d" (dans Abdo) pour L2.
  • Je m'appelle Emma Le Vourch
• Enlevez l'un des liens sortants du nœud L1.
• Rajoutez un lien depuis un nœud autre que L1 vers le nœud L2.

Composantes

I. Identifiez les composantes fortement connexes du graphe.

Le réseau entier est fortement connexe. En effet,

{L1,a,b,L2,d,f} sont tous fortement connexes.

II. En fonction des ses composantes fortement connexes, que peut-on conclure à propos de la centralité de vecteur propre du graphe ?

Chaque noeud a, au minimum, deux voisins.

Le noeud le plus central est a car il possède 4 voisins: b,d,L1,f. Aussi, b, L2, d et L1 sont fortements connexes avec 3 voisins et étant eux-mêmes connectés à des sommets aussi très connectés.

Vecteur propre et PageRank

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

Ordre dans la matrice : L1, b, c, d, L2, f

On veut construire une première matrice, la matrice A. 1 correspond à lorsqu'on a un nœud sortant entre 2 composantes.

$A={\begin{pmatrix}0&1&0&1&0&0\\0&0&1&0&1&0\\0&0&0&0&1&0\\0&0&1&0&0&1\\1&0&0&0&0&0\\1&0&0&0&0&0\\\end{pmatrix}}$

Par la suite, nous divisons chaque croisement par le nombre de noeuds sortants.

$M={\begin{pmatrix}0&1/2&0&1/2&0&0\\0&0&1/2&0&1/2&0\\0&0&0&0&1&0\\0&0&1/2&0&0&1/2\\1&0&0&0&0&0\\1&0&0&0&0&0\\\end{pmatrix}}$

Voici la matrice transposée de M :

$M^{t}={\begin{pmatrix}0&0&0&0&1&1\\1/2&0&0&0&0&0\\0&1/2&0&1/2&0&0\\1/2&0&0&0&0&0\\0&1/2&1&0&0&0\\0&0&0&1/2&0&0\\\end{pmatrix}}$

II. Calculez une itération de PageRank avec s = 0,9 :

• Initialisez le vecteur de matière pour le calcul de la centralité de vecteur propre en la partageant également entre tous les nœuds.
  • Pour simplifier le calcul vous pouvez choisir une quantité totale égal au nombre de nœuds, d'une telle sorte que chaque nœud est initialisé avec 1.
• Pour une fois :
  • Faites une itération pour tous les nœuds de l'algorithme pour e calcul de la centralité de vecteur propre (de façon matricielle ou manuelle).
  • Multipliez la matière dans chaque nœud par s = 0,9, puis partagez également  de la matière totale entre tous les nœuds.
• Vérifiez que la matière totale n'a pas changé au bout des comptes

$V_{0}={\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}$

Nous allons désormais effectuer le calcul d'une itération de la centralité de vecteur propre :

$M^{t}*V_{0}={\begin{pmatrix}0&0&0&0&1&1\\1/2&0&0&0&0&0\\0&1/2&0&1/2&0&0\\1/2&0&0&0&0&0\\0&1/2&1&0&0&0\\0&0&0&1/2&0&0\\\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}$= ${\begin{pmatrix}2\\1/2\\1\\1/2\\3/2\\1/2\end{pmatrix}}$

Ici, il est rapidement possible de vérifier que nous avons bien une matière totale de 6.

Donc on doit avoir $M^{t}V_{0}*0,9+0,1$

Soit ${\begin{pmatrix}2\\1/2\\1\\1/2\\3/2\\1/2\end{pmatrix}}$* 0,9 + ${\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}$ = ${\begin{pmatrix}1,8\\0,45\\0,9\\0,45\\1,35\\0,45\end{pmatrix}}$+${\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}$ = ${\begin{pmatrix}1,9\\0,55\\1\\0,55\\1,45\\0,55\end{pmatrix}}$

Ici, encore, nous obtenons le résultat de 6.

Note 1 : Nœuds sans issue

Si en enlevant le lien sortant du nœud L1 vous vous retrouvez avec un nœud sans lien sortant, la matière dans ce nœud n'aura pas de destination et par conséquence la matière totale ne sera pas constante et aura tendance à s'anéantir. Garder la matière dans le nœud ne résout pas le problème, car on perd la correspondance entre importance du nœud et circulation de matière. C'est alors un peu le même problème des graphes non fortement connexes, et la bonne solution n'est pas si différente : si un nœud n'a pas de lien sortant, on va simplement imaginer qu'il n'a pas de préférence pour verser sa matière et donc on va la repartir également entre les autres nœuds. C'est à dire, un nœud sans lien sortant doit être traité comme un nœud avec des liens sortants vers tous les autres nœuds !

Graphe de blocs

Je n'ai pas compris cette question... j'ai essayé de la faire mais ça n'a pas marché, je vous demanderai des précisions dessus si je n'arrive toujours pas à la comprendre même avec la correction.

Bon travail !