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