Aller au contenu

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

Une page de Wikiversité, la communauté pédagogique libre.

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

Ecrivons la matrice de diffusion d'entrée des noeuds, MT, puis multiplions la avec le vecteur de matière V à chaque itération.

Calcul de la matrice MT:

  • 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" (exemple, est-ce que A est lié à B, si oui =1 sinon =0).
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
  • Procédons à la normalisation des lignes ("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, 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 (exemple a pour V1 = 0*0,125+...+1*0,125+1*0,125+0*0,125+...=0,25)
  • Puis, 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.

Le graphe compte trois composantes fortement connexes: {a,b,d,e,f}, {c} et {g,h}. Au bout de la 2eme itération on voit que la matière a tendance à se stocker dans (g) et (h) du fait que la matière de {a,b,d,e,f} arrive uniquement de {c} pour aller dans {g,h}

A l'intérieur de la composante, il existe un chemin reliant tous les 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, que la matière remonte par exemple de (g) vers (e)

L'objectif étant de "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é entrante: (inverse de la somme des distances depuis les autres noeuds).

Noeud Calcul Proximité
1 1/(2+1+1) 0.25
2 1/(1+2+1) 0.25
3 1/(2+1+1) 0.25
4 1/(2+1+3) 0.17

Proximité sortante:

Neud Calcul Proximité
1 1/(1+2+2) 0.2
2 1/(2+1+1) 0.25
3 1/(1+2+3) 0.17
4 1/(1+1+1) 0.33

Pour trouver l'intermédiarité entre les nœuds, on trouve d'abord les chemins les plus courts pour chaque paire de nœuds:

(1,2) : 1 puis 3 puis 2 et 1 puis 4 puis 2

(1,3) : 1 puis 3

(1,4) : 1 puis 4

(2,1) : 2 puis 1

(2,3) : 2 puis 1 puis 3

(2,4) : 2 puis 4

(3,1) : 3 puis 2 puis 1

(3,2) : 3 puis 2

(3,4) : 3 puis 4

(4,1) : 4 puis 2 puis 1

(4,2) : 4 puis 2

(4,3) : 4 puis 2 puis 1 puis 3

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 & intermédiarité
Proximité Intermédiarité
0,17 0,5
0,25 2
0,25 3
0,25 0,5

Il y seulement deux valeurs de proximité, on peut donc faire un tableau pour la moyenne de l'intermédiarité

Proximité sortante & intermédiarité (moyenne)
Proximité Intermédiarité
0,17 0,5
0,25 1,83

Concernant les proximités entrante, aucune proximité a la même valeur, on a donc:

Proximité entrante & intermédiarité
Proximité Intermédiarité
0,17 0,5
0,2 2
0,25 3
0,33 0,5
  • 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é

Voir feuille papier

Récupérée de « https://fr.wikiversity.org/w/index.php?title=Utilisateur:Edouard_Ferrero/Modélisation_des_Réseaux_(M1,_2018)/Activité_E&oldid=745423 »