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 |