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

Travail original

Mon réseau

Considérez le graphe de la diapo 25 de l'ensemble 3 : Image 1 à droite

- 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.

Je m’appelle MA Yibo. Du coup, je trouve « a » (dans MA) pour L1 et « b » (dans Yibo) pour L2.

J’enlève le lien depuis a vers c.

Je rajoute un lien depuis f vers b.

Voilà le nouveau graphe : Image 2 à droite

Composantes

1. Identifiez les composantes fortement connexes du graphe.

Il y a 2 composantes fortement connexes du graphe :

G1 = {a, b, d, e, f}

G2 = {c}

Proximité et intermédiarité

1. Calculez la proximité de L1 et L2.

Définition : l’inverse de la somme des distances

C^G1_p(a) = 1/6

(a->b:1, a->d:1, a->e:2, a->f:2)

C^G1_p(b) = 1/10

(b->a:2, b->d:3, b->e:1, b->f:4)

2. Calculez l’intermédiarité de L1 et L2.

Définition : la somme, pour chaque pair des autres nœuds, de la fraction des chemins les plus courts entre ces nœuds qui passent par le premier.

g(a) = 6

g(b) = 3

Pour ab, ae, ad, af, ba, be, bd, bf, da, db, de, df, ea, eb, ed, ef, fa, fb, fd, fe, on peut supprimer ab, ad, be, df, ea, fa, fb, car il existe un lien direct entre ces nœuds, c’est-à-dire qu’il n’y a pas de nœuds intermédiaires entre ces nœuds.

Par conséquent, on considère que les nœuds : ae, af, ba, bd, bf, da, db, de, eb, ed, ef, fd, fe.

a = 1+1+1+1+1+1 (bd, bf, eb, ed, ef, fd)

b = 1+1+1 (ae, de, fe)

Vecteur propre et PageRank

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

Définition : état d’équilibre d’une dynamique de diffusion linéaire entre les nœuds

Voir l’image à droite

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

Voir l’image à droite

Correction

Mon réseau

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

Voici mon graphe :

Composantes

Les composantes sont :

G1 = {a, b, d, e, f}

G2 = {c}

Proximité et intermédiarité

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

Proximité

Le graphe est orienté donc on 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, b, d, e, f} : 1/6.

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, b, d, e, f} : 1/6.

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

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

Intermédiarité

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) : 1 pour le pair (bd, bf, eb, ed, ef, fd) = 6.

Intermédiarité de L2 (b) : 1 pour (ae, de, fe) = 3.

Vecteur propre et PageRank

Vecteur propre

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

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

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

Total = 5

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 :

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

Total = 6

PageRank

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.

Total = 6

Question pour les curieux

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.

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