Utilisateur:Solstag/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).

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

Calcul de la matrice M^T:

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 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₁.
Finalement, on multiplie la matrice M^T avec le vecteur V₁ pour obtenir le vecteur V₂.

Matière

V₀

V₁

V₂

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	${\frac {1}{2+1+1}}$	$0,25$
2	${\frac {1}{1+2+1}}$	$0,25$
3	${\frac {1}{2+1+1}}$	$0,25$
4	${\frac {1}{2+1+3}}$	$0,17$

Proximité entrante
Noeud	Calcul	Proximité
1	${\frac {1}{1+2+2}}$	$0,2$
2	${\frac {1}{2+1+1}}$	$0,25$
3	${\frac {1}{1+2+3}}$	$0,17$
4	${\frac {1}{1+1+1}}$	$0,33$

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é