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

L'objectif de cette activité est de travailler les mesures de centralité vues dans le cours.

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).
• Expliquer le résultat en fonction des rapports entre les composantes fortement connexes du graphe.
• Comment pourrait-on procéder pour éviter ce problème ?

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

• Calculer la proximité et l'intermédiarité des noeuds
• 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é
• 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é

Diapo 25

Réponse:

Matrice 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	1	0	0	0	0	0	0	1
h	1	0	0	0	0	0	1	0

Matrice M

	a	b	c	d	e	f	g	h
a	0	1/3	1/3	1/3	0	0	0	0
b	0	0	1/2	0	1/2	0	0	0
c	0	0	0	0	0	0	1/2	1/2
d	0	0	1/2	0	0	1/2	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

Matrice MT

	a	b	c	d	e	f	g	h
a	0	0	0	0	1	1	0	0
b	1/3	0	0	0	0	0	0	0
c	1/3	1/2	0	1/2	0	0	0	0
d	1/3	0	0	0	0	0	0	0
e	0	1/2	0	0	0	0	0	0
f	0	0	0	1/2	0	0	0	0
g	0	0	1/2	0	0	0	0	1
h	0	0	1/2	0	0	0	1	0

Maintenant que l'on a la matrice MT, on va initialiser la valeur avec la grille de distribution à t=0 où chaque nœud a une valeur de 1/8

Soit P cette nouvelle matrice tel que:

P(a) = 1/8 : P(b) = 1/8 ; P(c) = 1/8 : P(d) = 1/8 ; P(e) = 1/8 : P(f) = 1/8 ; P(g) = 1/8 : P(h) = 1/8

On résout le système maintenant:

MT x P0= P1

MTe * 1/8 +MTf * 1/8 = Pa ↔ Pa= 1/25

MTb * 1/8= 1/3 * 1/8 =Pb ↔ Pb=0.041

On continue ces calculs et on obtient la matrice suivante:

P0	P1	P2
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 observe dans le graph de cette activité trois composantes fortement connexes : (a,b,d,e,f), (c) et (g,h).

On voit que la matière peut circuler entre a,b,d,e,f car ils sont tous connectés entre eux. La matière peut aussi descendre dans c, mais elle ne pourra pas "remonter" car le graph est orienté vers c. De même, la matière qui est descendu dans c finira par descendre dans g et h sans pouvoir remonter. Si on considère que l'on va avoir une infinité de tour de distribution de la matière, alors toute la matière finira par être concentré dans g et h.

.

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

Il faut laisser la possibilité à la matière de remonter. Pour se faire, il faut créer des liens qui sont orientés vers le "haut", par exemple en créant des liens entre g et e.

Diapo 18

1) Intermédiaire et proximité des nœuds:

Proximité entrante:

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’interarmées 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 X intermédiarité

Proximité	Intermédiarité
0,17	0,5
0,25	2
0,25	3
0,25	0,5

Ensuite on observe qu'il y seulement deux valeurs de proximité, on peut donc faire un nouveau graph avec ces deux valeurs et la moyenne de l'intermédiarité

Proximité sortante X intermédiarité (moyenne)

Proximité	Intermédiarité
0,17	0,5
0,25	1,83

Calculons maintenant le même tableau mais avec les proximités entrantes. On observe qu'aucune proximité a la même valeur et que l'on ne peut donc pas exprimer ce tableau avec une moyenne.

Proximité entrante X intermédiarité

Proximité	Intermédiarité
0,17	0,5
0,2	2
0,25	3
0,33	0,5

3) Voir la feuille, je n'ai pas réussi à le mettre