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

Graphe slide 25

Etude de la centralité de vecteurs propres de noeuds

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

Matrice M transposée

	a	b	c	d	e	f	g	h
a	0	0	0	0	1/8	1/8	0	0
b	1/8	0	0	0	0	0	0	0
c	1/8	1/8	0	1/8	0	0	0	0
d	1/8	0	0	0	0	0	0	0
e	0	1/8	0	0	0	0	0	0
f	0	0	0	1/8	0	0	0	0
g	0	0	1/8	0	0	0	0	1/8
h	0	0	1/8	0	0	0	1/8	0

Matrice P

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

On résout l'équation Mt*P = P

Calcul de Pa : 1/8 Pe + 1/8 Pf = Pa <=> 1/8 . 1/8 + 1/8 . 1/8 = Pa <=> Pa = 1/32

Calcul de Pb :1/8 Pa = Pb <=> Pb = 1/64

Calcul de Pc: 1/8Pa + 1/8Pb + 1/8Pd = Pc <=> Pc = 1/256

Calcul de Pd : Pd = 1/8 Pa <=> Pd = 1/64

Calcul de Pe : Pe = 1/8 Pb <=> Pe = 1/64

Calcul de Pf : Pf = 1/8 Pd <=> Pf = 1/64

Calcul de Pg : Pg = 1/8 Pc + 1/8 Ph <=> Pg = 1/32

Calcul de Ph : Ph = 1/8 Pc + 1/8 Pg <=> Ph = 1/32

On a 3 composantes fortement connexes : (e, b, a, d, f), (c) et (g, h).

Moins il y a de points dans la composantes fortement connexes, plus les valeurs sont petites.

Pour éviter ce problème on pourrait créer des liens de e vers g (ou inversement) et de h vers f (ou inversement).

Graphe Slide 18

Proximité des noeuds :

• Proximité sortante

P1 P1 = 1

P1 P2 = 2

P1 P3 = 1

P1 P4 = 1

c entrante (P1) = 1/(1+2+1+1) = 1/5

P2 P1 = 1

P2 P2 = 0

P2 P3 = 2

P2 P4 = 1

c entrante (P2) = 1/(1+0+2+1) = 1/4

P3 P1 = 1

P3 P2 = 1

P3 P3 = 0

P3 P4 = 2

c entrante (P3) = 1/(1+1+0+2) = 1/4

P4 P1 = 2

P4 P2 = 1

P4 P3 = 3

P4 P4 = 0

c entrante (P4) = 1/(2+1+3+0) = 1/6

• Proximité entrante

P1 P1 = 1

P2 P1 = 1

P3 P1 = 2

P4 P1 = 2

c sortante (P1) = 1/6

P1 P2 = 2

P2 P2 = 0

P3 P2 = 1

P4 P2 = 1

c sortante (P2) = 1/4

P1 P3 = 1

P2 P3 = 2

P3 P3 = 0

P4 P3 = 3

c sortante (P3) = 1/6

P1 P4 = 1

P2 P4 = 1

P3 P4 = 1

P4 P4 = 0

c sortante (P4) = 1/3

Intermédiarité des noeuds

	Nombre de liens sortants	c sortants (i)	intermédiarité
1	3	1/5	3/5
2	2	1/4	1/2
3	2	1/4	1/2
4	1	1/6	1/6

	Nombre de liens ENTRANTS	c sortants (i)	intermédiarité
1	2	1/6	1/3
2	2	1/4	1/2
3	1	1/6	1/6
4	3	1/3	1