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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche

Pour le graphe du diapo 25 de l'ensemble 3 :

  • Calculer la centralité de vecteur propre des noeuds (si en mode itératif, calculez au moins deux étapes de diffusion).

On va calculer la centralité de vecteu propre en mode itératif, en écrivant la matrice de diffusion d'entrée des noeuds, MT, puis la multipliant avec le vecteur de matière V à chaque itération.

Calcul de la matrice MT:

  • Pour la matrice de diffusion, on commence avec la matrice d'adjacence, A, où les lignes correspondent au nombre de liens sortant du noeud correspondant à la ligne et entrant dans le noeud correspondant à la colonne.
A
a b c d e f g h
a 0 1 1 1 0 0 0 0
b 0 0 1 0 1 0 0 0
c 0 0 0 0 0 0 1 1
d 0 0 1 0 0 1 0 0
e 1 0 0 0 0 0 0 0
f 1 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 1
h 0 0 0 0 0 0 1 0
  • Comme dans la centralité de vecteur propre, la matière en diffusion est partagé également entre les liens de sortie, pour obtenir la matrice de diffusion de sortie, M, on divise chaque ligne par la somme de ses valeurs.
M
a b c d e f g h
a 0 0,33 0,33 0,33 0 0 0 0
b 0 0 0,5 0 0,5 0 0 0
c 0 0 0 0 0 0 0,5 0,5
d 0 0 0,5 0 0 0,5 0 0
e 1 0 0 0 0 0 0 0
f 1 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 1
h 0 0 0 0 0 0 1 0
  • Enfin, pour passer de la matrice de diffusion de sortie à la matrice de diffusion d'entrée, on transpose la matrice M et obtient MT.
MT
a b c d e f g h
a 0 0 0 0 1 1 0 0
b 0,33 0 0 0 0 0 0 0
c 0,33 0,5 0 0,5 0 0 0 0
d 0,33 0 0 0 0 0 0 0
e 0 0,5 0 0 0 0 0 0
f 0 0 0 0,5 0 0 0 0
g 0 0 0,5 0 0 0 0 1
h 0 0 0,5 0 0 0 1 0

Calcul de la centralité de vecteur propre:

  • On initialise le vecteur de matière V0 avec une distribution repartie également: 1/8 = 0,125 pour chaque noeud.
  • En suite, on multiplie la matrice MT avec le vecteur V0 pour obtenir le vecteur suivante, V1.
  • Finalement, on multiplie la matrice MT avec le vecteur V1 pour obtenir le vecteur V2.
Matière
V0 V1 V2
a 0,125
b 0,125
c 0,125
d 0,125
e 0,125
f 0,125
g 0,125
h 0,125
a 0,25
b 0,04
c 0,17
d 0,04
e 0,06
f 0,06
g 0,19
h 0,19
a 0,12
b 0,08
c 0,12
d 0,08
e 0,02
f 0,02
g 0,28
h 0,28

.

  • Expliquer le résultat en fonction des rapports entre les composantes fortement connexes du graphe.

On voit que le graphe a trois composantes fortement connexes: {a,b,d,e,f}, {c} et {g,h}.

La composante {c} reçoit de la matière de la composante {a,b,d,e,f}, et la transmet à la composante {g,h}.

La composante {g,h} reçoit de la matière de la composante {c}, mais ne la transmet à aucune autre.

Donc toute la matière ira éventuellement se concentrer dans la composante {g,h}, rendant la centralité de vecteur propre inutile pour classer la plupart des noeuds.

.

  • Comment pourrait-on procéder pour éviter ce problème ?

On peut ajouter des liens pour que le graphe devient une seule composante fortement connexe.

La façon employé dans l'algorithme PageRank consiste de créer des liens faibles, qui ne transportent qu'une fraction de la matière, entre tous les noeuds.

Ce qui est équivalent à prélever à chaque itération une fraction de la matière de chaque noeud et la distribuer également entre tous.

.

Pour le graphe du diapo 18 de l'ensemble 3 :

  • Calculer la proximité et l'intermédiarité des noeuds
Proximité sortante
Noeud Calcul Proximité
1
2
3
4
Proximité entrante
Noeud Calcul Proximité
1
2
3
4

Pour l'intermédiarité, on trouve d'abord les chemins les plus courts pour chaque pair de noeuds:

  • (1,2) : 132 et 142
  • (1,3) : 13
  • (1,4) : 14
  • (2,1) : 21
  • (2,3) : 213
  • (2,4) : 24
  • (3,1) : 321
  • (3,2) : 32
  • (3,4) : 34
  • (4,1) : 421
  • (4,2) : 42
  • (4,3) : 4213
Intermédiarité
Noeud Calcul Intermédiarité
1 1+1 2
2 1+1+1 3
3 0.5 0,5
4 0.5 0,5

.

  • Faire le tableau de corrélation combiné mettant en relation ces deux mesures
    • c'est-à-dire, un tableau où la première colonne correspond à la proximité et la deuxième à l'intermédiarité
    • dans le cas où plus d'un noeud a la même proximité, vous avez le choix entre lister plusieurs lignes avec la même proximité, ou lister la moyenne des intermédiarités pour cette proximité

.

Proximité sortante X intermédiarité
Proximité Intermédiarité
0,17 0,5
0,25 2
0,25 3
0,25 0,5
Proximité sortante X intermédiarité (moyenne)
Proximité Intermédiarité
0,17 0,5
0,25 1,83
Proximité entrante X intermédiarité
Proximité Intermédiarité
0,17 0,5
0,2 2
0,25 3
0,33 0,5

Le tableau pour la moyenne ici est le même, car il n'y a pas deux noeuds avec proximité entrante égal.

.

  • Dessiner le graphique pour la corrélation combiné de ces deux mesures
    • c'est-à-dire, un graphique où l'abscisse correspond à la proximité et l'ordonnée à l'intermédiarité de chaque noeud
    • dans le cas où plus d'un noeud a la même proximité, vous avez le choix entre afficher plusieurs points avec la même proximité, ou afficher la moyenne des intermédiarités pour cette proximité

.

Aux étudiants: faire sur feuille papier; malheureusement, à cause d'un bogue, les graphiques ci-dessous exigent éditer manuellement le code de la page.

Proximité sortante X intermédiarité (moyenne)

Proximité entrante X intermédiarité