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

Pour le graphe du diapo 25 de l'ensemble 3

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

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

Matrice M

	a	b	c	d	e	f	g	h
a		1/3 * 1/8 = 1/24	1/3 * 1/8 = 1/24	1/3 * 1/8 = 1/24
b			1/8*1/2= 1/16		1/8*1/2= 1/16
c							1/16	1/16
d			1/16			1/16
e	1/8
f	1/8
g								1/8
h							1/8

Matrice M transposée

	a	b	c	d	e	f	g	h
a					1/8	1/8
b	1/24
c	1/24	1/16		1/16
d	1/24
e		1/16
f				1/16
g			1/16					1/8
h			1/16				1/8

Pa = 1/8
Pb = 1/8
Pc = 1/8
Pd = 1/8
Pe = 1/8
Pf = 1/8
Pg = 1/8
Ph = 1/8

Pour trouver la centralité, on résout l'équation pour trouver les p(n*) tels que P=MT.P

D'où:

p(a)=1/8p(e)+1/8p(f) = 1/32

p(b)=1/24p(a)= 1/768

p(c)=1/24p(a)+1/16p(b)+1/16p(d)= 1/768 + 1/12288+ 1/12288 = 1/768 + 2/12288= 1/768 + 1/644 = 3/2048

p(d)=1/24p(a) = 1/768

p(e)=1/16p(b) = 1/8*1/768 =1/12288

p(f)=1/16p(d)= 1/12288

p(g)=1/16p(c)+1/8p(h)= ??

p(h)=1/16p(c)+1/8p(g) =1??

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

On remarque que les points a,g,h ont une forte centralité. G et H sont aussi fortement connexes.

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

Enlever un des deux liens entre g et h

Pour le graphe du diapo 18 de l'ensemble 3

1) Calculer la proximité et l'intermédiarité des noeud

Proximité sortante:

• Somme distances sortantes de 1:1+ 2+ 1+ 1 = 4 --> p(1)= 1/5
• Somme distances sortantes de 2: 1 + 2 + 1 --> p(2) = 1/4

• Somme distances sortantes de 3: 2+ 1 + 1 --> p(3)= 1/4
• Somme distances sortantes de 4 : 2 + 1 + 2 = 1/5

Proximité entrante:

• Somme distances entrantes de 1: 1 +1 + 2 + 2 = 1/6
• Somme distances entrantes de 2: 2 + 1 + 1= 1/4
• Somme distances entrantes de 3 : 1 + 2 + 3 = 1/6
• Somme distances entrantes de 4 : 1+ 1 + 1 = 1/3

2) Faire le tableau de corrélation combiné mettant en relation ces deux mesure

noeuds	nombre de liens sortants	proximité c(n)	intermédiarité g(n)
1	3	1/5	3/5
2	2	1/4	1/2
3	2	1/4	1/2
4	1	1/6	1/6

noeuds	nombre de liens entrants	proximité c(n)	intermédiarité g(n)
1	2	1/6	1/3
2	2	1/4	1/2
3	1	1/6	1/6
4	3	1/3	1