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

Une page de Wikiversité, la communauté pédagogique libre.

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