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

Mon réseau

Instruction

Considérez le graphe du diapo 25 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.
• 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.

Résultat

Mon L1 est le nœud a et mon L2 est le nœud d.

Voici mon graphe :

J'enlève un lien sortant de mon nœud L1 - je choisis (a, b) - et j'ajoute un lien vers mon nœud L2 - je choisis (f, d).

Composantes

Instruction

I. Identifiez les composantes fortement connexes du graphe.

Résultat

Les composantes sont : {a, d, f}, {b}, {c}, {e}.

Proximité et intermédiarité

Instruction

I. Calculez la proximité de L1 et L2.

II. Calculez l'intermédiarité de L1 et L2.

Résultat

IMPORTANT : Pour le calcul de la proximité et intermédiarité il faut considérer la composante fortement connexe à laquelle le nœud appartient.

Le graphe est orienté donc ont peut parler de proximité entrante et sortante.

La proximité sortante de L1 (a) est l'inverse de la somme de la distance de a vers les autres membres de sa composante fortement connexe {a, d, f} : 1/3.

La proximité entrante de L1 (a) est l'inverse de la somme de la distance vers a de chacun des membres de sa composante fortement connexe {a, d, f} : 1/3.

La proximité sortante de L2 (d) est l'inverse de la somme de la distance de d vers les autres membres de sa composante fortement connexe {a, d, f} : 1/3.

La proximité entrante de L2 (d) est l'inverse de la somme de la distance vers d de chacun des membres de sa composante fortement connexe {a, d, f} : 1/2.

Pour l'intermédiarité d'un nœud on ajoute pour chacun des pairs orientés des autres nœuds la fraction des chemins les plus courts entre eux qui passent par le nœud:

Intermédiarité de L1 (a) : 0 pour le pair (d, f) plus 0 pour (f, d) = 0.

Intermédiarité de L2 (d) :1 pour (a, f), 0 pour (f, a) = 1.

Vecteur propre et PageRank

Instruction

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

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 égale 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 $1-s\ (=0,1)$ 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.

Résultat

Plaçant les nœuds ordonnées alphabétiquement, on obtient la matrice $M^{T}$ :

$A={\begin{pmatrix}0&0&1&1&0&0\\0&0&1&0&1&0\\0&0&0&0&0&0\\0&0&1&0&0&1\\1&0&0&0&0&0\\1&0&0&1&0&0\\\end{pmatrix}}$, $M={\begin{pmatrix}0&0&1/2&1/2&0&0\\0&0&1/2&0&1/2&0\\0&0&0&0&0&0\\0&0&1/2&0&0&1/2\\1&0&0&0&0&0\\1/2&0&0&1/2&0&0\\\end{pmatrix}}$, $M^{T}={\begin{pmatrix}0&0&0&0&1&1/2\\0&0&0&0&0&0\\1/2&1/2&0&1/2&0&0\\1/2&0&0&0&0&1/2\\0&1/2&0&0&0&0\\0&0&0&1/2&0&0\\\end{pmatrix}}$

J'initialise mon vecteur de matière distribuant également une matière totale de $6$ :

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

Je procède au calcul d'une itération de la centralité de vecteur propre :

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

Même avant la multiplication par le facteur redistributif s, je note que la matière totale est passée à ... $5$ ?! Ce n'est pas bien.

Ah, je lis la note sur les « nœuds sans issue » et je me rends compte que mon nœud c n'a pas d'issue ! Il faut alors suivre l'instruction et traiter le nœud c comme s'il était connecté à tous les autres nœuds, pour distribuer également sa matière entre eux. Comme ça on obtient une nouvelle matrice $M^{T}$ :

$A={\begin{pmatrix}0&0&1&1&0&0\\0&0&1&0&1&0\\1&1&0&1&1&1\\0&0&1&0&0&1\\1&0&0&0&0&0\\1&0&0&1&0&0\\\end{pmatrix}}$, $M={\begin{pmatrix}0&0&1/2&1/2&0&0\\0&0&1/2&0&1/2&0\\1/5&1/5&0&1/5&1/5&1/5\\0&0&1/2&0&0&1/2\\1&0&0&0&0&0\\1/2&0&0&1/2&0&0\\\end{pmatrix}}$, $M^{T}={\begin{pmatrix}0&0&1/5&0&1&1/2\\0&0&1/5&0&0&0\\1/2&1/2&0&1/2&0&0\\1/2&0&1/5&0&0&1/2\\0&1/2&1/5&0&0&0\\0&0&1/5&1/2&0&0\\\end{pmatrix}}$

Et donc le nouveau calcul de l'itération :

$M^{T}V_{0}={\begin{pmatrix}0&0&1/5&0&1&1/2\\0&0&1/5&0&0&0\\1/2&1/2&0&1/2&0&0\\1/2&0&1/5&0&0&1/2\\0&1/2&1/5&0&0&0\\0&0&1/5&1/2&0&0\\\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}17/10\\2/10\\15/10\\12/10\\7/10\\7/10\end{pmatrix}}$

Pour une matière totale après l'itération de ... 6 ! Elle reste inchangé, comme on voulait.

On peut alors effectuer l'étape de redistribution, pour éviter que le risque que la matière se concentre uniquement dans quelques composantes fortement connexes du graphe vers lesquelles elle rentrerait mais ne sortirait pas.

$0.9*V_{0}+0.1=9/10*{\begin{pmatrix}17/10\\2/10\\15/10\\12/10\\7/10\\7/10\end{pmatrix}}+{\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}={\begin{pmatrix}163/100\\28/100\\145/100\\118/100\\73/100\\73/100\end{pmatrix}}$

On vérifie que la matière totale est ... 6 ! Super !

Instruction

Il est aussi possible de représenter l'étape redistributive ("revenu universel") sous la forme d'une matrice qui multiplie le vecteur de matière. Quelle serait cette matrice ?

Résultat

Attribuer à chaque nœud une partie $1-s$ de la matière de chacun des nœuds, cela correspond à une matrice où tous les éléments sont ${\frac {1-s}{N}}$, où $N$ est le nombre de nœuds du graphe.

Comme on veut aussi garder une partie $s$ de la matière de chaque nœud dans le nœud lui-même, il faut ajouter ce terme $s$ à la diagonale de la matrice.

Dans notre cas, pour $s=0.9$ (et donc $1-s=0.1$) on obtient alors la matrice de redistribution :

$R={\begin{pmatrix}0.9+0.1/6&0.1/6&0.1/6&0.1/6&0.1/6&0.1/6\\0.1/6&0.9+0.1/6&0.1/6&0.1/6&0.1/6&0.1/6\\0.1/6&0.1/6&0.9+0.1/6&0.1/6&0.1/6&0.1/6\\0.1/6&0.1/6&0.1/6&0.9+0.1/6&0.1/6&0.1/6\\0.1/6&0.1/6&0.1/6&0.1/6&0.9+0.1/6&0.1/6\\0.1/6&0.1/6&0.1/6&0.1/6&0.1/6&0.9+0.1/6\\\end{pmatrix}}$

Plus généralement, employant la notation $\delta (i,j)={\begin{cases}1,&{\text{si }}i=j\\0,&{\text{si }}i\neq j\end{cases}}$ , pour un réseau à $N$ nœuds on peut définir cette matrice comme $R_{ij}=\delta (i,j)*s+{\frac {1-s}{N}}$.