Utilisateur:Alicecorreia/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/24	1/24	1/24
b			1/16		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 MT(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

Matrice P

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

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)

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

p(c)=1/24p(a)+1/16p(b)+1/16p(d)

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

p(e)=1/16p(b)

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

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

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

s'achant que p(a)+p(b)+p(c)+p(d)+p(e)+p(f)+p(g)+p(h)=1

p(a)=1/32

p(b)=1/768

p(c)=1/768+1/6144=3/2048

p(d)=1/768

p(e)=1/12288

p(f)=1/12288

p(g)= faire des manip pour sortir p(g) dans p'h), et après on trouve p(g) et p(h)

p(h)

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

On a trois groupes de composantes fortement connexes: (e, b, a, d, f), (c) et (g, h). Plus les groupes contiennent de composantes connexes, et plus les valeurs de ces groupes sont élevées.

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

On peut régler ce problème en créant des liens de e vers g, g vers e, h vers f, ou bien f vers h .

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

1- Calculer la proximité et l'intermédiarité des noeuds

La proximité est la distance entre un noeud et chaque autre noeud.

Le graphe est orienté

Proximité sortante :

p1-p1: 1

p1-p2 : 2

p1-p3 : 1

p1-p4 : 1

c(p1)= 1/1+2+1+1= 1/5

p2-p1:1

p2-p3: 2

p2-p4:1

c(p2)=1/1+2+1= 1/4

p3-p1:2

p3-p2:1

p3-p4: 1

c(p3): 1/2+1+1= 1/4

p4-p1: 2

p4-p2: 1

p4-p3: 3

c(p4): 1/2+1+3= 1/6

Proximité Entrante:

p1-p1: 1

p2-p1: 1

p3-p1: 2

p4-p1: 2

c(p1)= 1/6

p1-p2: 2

p3-p2: 1

p4-p2: 1

c(p2)=1/4

p1-p3: 1

p2-p3: 2

p4-p3: 3

c(p3)= 1/6

p1-p4: 1

p2-p4: 1

p3-p4:1

c(p4)= 1/3

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

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