Utilisateur:A. Isabelle/Modélisation des Réseaux (M1, 2018)/Activité E
Pour le graphe du diapo 25 de l'ensemble 3
-Calcul de la centralité de vecteur propre des noeuds (si en mode itératif, calculez au moins deux étapes de diffusion). Pour ce faire, on écrit la matrice de diffusion d'entrée des nœuds.
Donc d'abord la matrice d'adjacence
| 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 |
Puis on fait la normalisation
| a | b | c | d | e | f | g | h | |
|---|---|---|---|---|---|---|---|---|
| a | 0 | 1/3 | 1/3 | 1/3 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1/2 | 0 | 1/2 | 0 | 0 | 0 |
| c | 0 | 0 | 0 | 0 | 0 | 0 | 1/2 | 1/2 |
| d | 0 | 0 | 1/2 | 0 | 0 | 1/2 | 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 |
Puis la transposition
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 1/3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1/3 | 1/2 | 0 | 1/2 | 0 | 0 | 0 | 0 |
| 1/3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1/2 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1/2 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1/2 | 0 | 0 | 0 | 1 | 0 |
Expliquer le résultat en fonction des rapports entre les composantes fortement connexes du graphe.
Nous ne connaissons pas l'état initial donc on présume que
P(a) = P(b) [...] = P(h) = 1/8
On voit que le graphe a trois composantes fortement connexes: {a,b,d,e,f}, {c} et {g,h}.
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 (ou inversement) et de h vers f (ou inversement).
Pour le graphe du diapo 18 de l'ensemble 3
Calculer la proximité et l'intermédiarité des nœuds. Pour des graphes orientés, comme ici, il y a proximité d'entrée et de sortie. Intermédiarité: on prend toutes les paires de nœuds et on regarde combien de chemins les plus courts doivent passer par l'un.
PROXIMITÉ SORTANTE
P1 P1 = 1
P1 P2 = 2
P1 P3 = 1
P1 P4 = 1
c entrante (P1) = 1/5
.
P2 P1 = 1
P2 P3 = 2
P2 P4 = 1
c entrante (P2) = 1/4
.
P3 P1 = 2
P3 P2 = 1
P3 P4 = 1
c entrante (P3) = 1/4
.
P4 P1 = 2
P4 P2 = 1
P4 P3 = 3
c entrante (P4) = 1/6
.
PROXIMITÉ ENTRANTE
P1 P1 = 1
P2 P1 = 1
P3 P1 = 2
P4 P1 = 2
c sortante (P1) = 1/6
.
P1 P2 = 2
P3 P2 = 1
P4 P2 = 1
c sortante (P2) = 1/4
.
P1 P3 = 1
P2 P3 = 2
P4 P3 = 3
c sortante (P3) = 1/6
.
P1 P4 = 1
P2 P4 = 1
P3 P4 = 1
c sortante (P4) = 1/3
Tableau de corrélation combinée mettant en relation ces deux mesure
| nbre de liens sortants | c sortant (i) | intermédiarité | |
|---|---|---|---|
| 1 | 3 | 1/5 | 0,6 |
| 2 | 2 | 1/4 | 0,5 |
| 3 | 2 | 1/4 | 0, 5 |
| 4 | 1 | 1/6 | 0, 17 |
| nbre de liens entrants | c sortant (i) | intermédiarité | |
|---|---|---|---|
| 1 | 2 | 1/6 | 1/3 |
| 2 | 2 | 1/4 | 1/2 |
| 3 | 1 | 1/6 | 1/6 |
| 4 | 3 | 1/3 | 1 |
Dessiner le graphique pour la corrélation combinée de ces deux mesures: voir feuille