Utilisateur:Ma Yibo/Modélisation des Réseaux (M1 SIREN, 2021)/Activité E
Travail original
[modifier | modifier le wikicode]Mon réseau
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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é
[modifier | modifier le wikicode]1. Calculez la proximité de L1 et L2.
Définition : l’inverse de la somme des distances
CG1p(a) = 1/6
(a->b:1, a->d:1, a->e:2, a->f:2)
CG1p(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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]Mon réseau
[modifier | modifier le wikicode]Mon L1 est le nœud a et mon L2 est le nœud b.
Voici mon graphe :
Composantes
[modifier | modifier le wikicode]Les composantes sont :
G1 = {a, b, d, e, f}
G2 = {c}
Proximité et intermédiarité
[modifier | modifier le wikicode]IMPORTANT : Pour le calcul de la proximité et intermédiarité il faut considérer la composante fortement connexe à laquelle le nœud appartient.
Proximité
[modifier | modifier le wikicode]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é
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]Vecteur propre
[modifier | modifier le wikicode]Plaçant les nœuds ordonnés alphabétiquement, on obtient la matrice MT :
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 MT :
Et donc le nouveau calcul de l'itération :
Total = 6
PageRank
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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 :