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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche

L'objectif de cette activité est de travailler les mesures de centralité vues dans le cours.

1) Pour le graphe du diapo 25 de l'ensemble 3 :

  • 1.1 Calculer la centralité de vecteur propre des noeuds (si en mode itératif, calculez au moins deux étapes de diffusion).
  • 1.2 Expliquer le résultat en fonction des rapports entre les composantes fortement connexes du graphe.
  • 1.3 Comment pourrait-on procéder pour éviter ce problème ?

2) Pour le graphe du diapo 18 de l'ensemble 3 :

  • 2.1Calculer la proximité et l'intermédiarité des noeuds
  • 2.2Faire le tableau de corrélation combiné mettant en relation ces deux mesures
    • c'est-à-dire, un tableau où la première colonne correspond à la proximité et la deuxième à l'intermédiarité
    • dans le cas où plus d'un noeud a la même proximité, vous avez le choix entre lister plusieurs lignes avec la même proximité, ou lister la moyenne des intermédiarités pour cette proximité
  • 2.3 Dessiner le graphique pour la corrélation combiné de ces deux mesures
    • c'est-à-dire, un graphique où l'abscisse correspond à la proximité et l'ordonnée à l'intermédiarité de chaque noeud
    • dans le cas où plus d'un noeud a la même proximité, vous avez le choix entre afficher plusieurs points avec la même proximité, ou afficher la moyenne des intermédiarités pour cette proximité

1.1

On suppose que

a=1/8

b=1/8

c=1/8

d=1/8

e=1/8

f=1/8

g=1/8

h=1/8

1ère itération

a=1/8+1/8=1/4

b=1/8/3=1/24

c=1/24+1/16+1/16=1/6

d=1/24

e=1/16

f=1/16

g=1/16+1/8=3/16

h=1/16+1/8=3/16

T=1

2ème itération

a=1/8

b=1/12

c=1/24+1/12=3/24

d=1/12

e=1/48

f=1/48

g=3/16+1/12=13/48

h=3/16+1/12=13/48

T=1

1.2 On constate que certains noeuds donnent la totalité de leur contenu alors qu'il ne reçoivent que petites quantités (e,f), alors que certains s'échange la totalité de leur contenu et en recoivent en plus à chaque itération (g,h). On constate ici qu'il va y avoir un vrai déséquilibre qui va se faire au fils des itérations. g et h vont finir par avoir la grande majorité du contenu quand les autres noeuds vont se vider au fur et à mesure.

1.3 Pour cela, il faudrait réinjecter le contenu de g et h dans d'autres noeuds (par exemple e et f).

2.1

cp(1) = 1/4

cp(2) = 1/4

cp(3) = 1/4

cp(4) = 1/6

g(1) = 1 + 1 = 2

g(2) = 1 + 1 + 1 = 3

g(3) = 0,5

g(4) = 0,5

g = 6

2.2

Intermédiarité Proximité
1 1/4 2
2 1/4 3
3 1/4 1/2
4 1/6 1/2

2.3

Voir Feuille