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

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, M^T, puis multiplions la avec le vecteur de matière V à chaque itération.

Calcul de la matrice M^T:

• 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 M^T.

M^T

	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 V₀ avec une distribution repartie également: 1/8 = 0,125 pour chaque noeud.
• En suite, on multiplie la matrice M^T avec le vecteur V₀ pour obtenir le vecteur suivante, V₁ (exemple a pour V1 = 0*0,125+...+1*0,125+1*0,125+0*0,125+...=0,25)
• Puis, on multiplie la matrice M^T avec le vecteur V₁ pour obtenir le vecteur V₂.

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