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).
| 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 |
| 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 |
| 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 |
| 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 |