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

Mon réseau avec a et e remplacé respectivement par L1 et L2.

Votre réseau

• Parmi les lettres [a, b, c, d, e, f], la première est A = L1 dans (Alexandra) et la dernière est E = L2 dans (Levigne).
• Nous avons donc le graphique suivant :

Composantes

I. Identifiez les composantes fortement connexes du graphe :

Tous les éléments de mon réseau forment une composante fortement connexe soit {L1,b,d,c,L2,f}

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

Le noeud L1 est le plus central, en effet ce dernier possède 4 voisins. Les noeuds b, c, d et L2 sont eux aussi centraux, ils possèdent 3 voisins et sont connectés à des sommets très connectés également. Enfin, F est le noeud le moins central puisqu'il ne possède que 2 voisins.

Vecteur propre et PageRank

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

A = ${\begin{pmatrix}0&1&0&1&0&0\\0&1&0&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}}$

M = ${\begin{pmatrix}0&1/2&0&1/2&0&0\\0&1/2&0&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}}\$

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$ :

Initialisation du vecteur pour distribuer de manière égale une matière totale (avec 1) V₀ =${\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}$

Calcul d'une itération de la centralité de vecteur propre soit 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}}$

Nous retrouvons donc bien ici une matière totale de 6. Je multiplie ensuite la matière dans chaque noeud par 0.9 puis j'ajoute 0.1.

Ainsi M^t * V₀ * 0,9 + 0,1 ce qui nous donne :

${\begin{pmatrix}1,9\\0,55\\1\\0,55\\1,45\\0,55\end{pmatrix}}$

Nous retrouvons encore une fois une matière totale de 6, ce qui nous confirme nos calculs.

Note 1 : Nœuds sans issue

Je me sens nulle, je n'arrive pas à remplir le reste de l'activité.