Utilisateur:Victor Alric/Modélisation des Réseaux (M1 SIREN, 2020)/Activité D

Une page de Wikiversité, la communauté pédagogique libre.


Question 1

Voici le nouveau graphe connexe, obtenu en utilisant les réseaux projetés II de Zélie et Emma : https://commons.wikimedia.org/wiki/File:R%C3%A9seau_projet%C3%A9_2_-_activit%C3%A9_D.jpg

FYI : le lien "piano" entre [Armance] et [Émilia] a volontairement été supprimé pour ne pas encombrer le graphe, néanmoins le raisonnement reste exactement le même.

Voici le graphique pour la distribution de degrés : https://commons.wikimedia.org/wiki/File:Distribution_de_degr%C3%A9s_-_activit%C3%A9_D.jpg


Question 2

Pour déterminer la corrélation de voisins entre degré et degré, il nous faut le degré des noeuds (objet de la question précédente) et le degré des voisins. Pour chaque noeud, le degré des voisins se calcule en faisant une moyenne.

Exemple : le noeud [Emma] a 2 voisins : [Victor] (degré : 14) et [Émilia] (degré : 7) Ainsi, la corrélation de voisins entre degré et degré du noeud [Emma] vaut : c([Emma]) = (14+7)/2 = 10,5. On procède de la même façon pour les autres noeuds.

On obtient donc :

Noeud Degré Corrélation de voisins entre degré et degré Explications
[Emma] 4 10,5 c([Emma]) = (14+7)/2 = 10,5
[Émilia], [Thibaud] 7 8,725 c([Émilia]) = (14+8+4+7+8)/5 = 8,2 et c([Thibaud]) = (14+7+8+8)/4 = 9,25, d’où moyenne = (8,2+9,25)/2 = 8,725
[Armance], [Zélie] 8 9 c([Armance]) = c([Zélie]) = (7+8+14+7)/4 = 9
[Victor] 14 6,8 c([Victor]) = (8+8+7+4+7)/5 = 6,8

Voici le graphique pour la corrélation de voisins entre degré et degré : https://commons.wikimedia.org/wiki/File:Degr%C3%A9_de_voisins_-_activit%C3%A9_D.jpg


Question 3

On remarque une corrélation négative entre degré et degré de voisins. En effet, les noeuds à petit degré sont connectés à des noeuds à plus grand degré. Ainsi, le réseau est dissortatif.


Question 4

Pour un noeud i, le coefficient de clustering c(i) vaut : c(i) = paires de voisins connectés/((n(i)*(n(i)-1))/2) On obtient ainsi :

Noeud Coefficient de clustering Explications
[Victor] 0,7 7/(5*4/2) = 0,7
[Armance] 0,67 4/(4*3/2) = 0,67
[Zélie] 0,67 4/(4*3/2) = 0,67
[Thibaud] 0,67 4/(4*3/2) = 0,67
[Emma] 1 1/(2*1/2) = 1
[Émilia] 0,4 4/(5*4/2) = 0,4


Question 5

Voici le tableau pour la corrélation combinée entre degré et coefficient de clustering :

Degré Corrélation combinée
4 1
7 (0,67+0,4)/2 = 0,535
8 0,67
14 0,7

Le graphique pour la corrélation combinée entre degré et coefficient de clustering est le suivant : https://commons.wikimedia.org/wiki/File:Corr%C3%A9lation_combin%C3%A9e_-_activit%C3%A9_D.jpg


Question 6

Graphique et tableau 1 : le réseau comporte une quantité importe de noeuds très connectés. En effet, 5 noeuds ont un degré supérieur ou égal à 7. À l’inverse, il y a peu de noeuds non connectés, car 1 noeud sur 6 a un degré égal à 4.

Graphique et tableau 2 : globalement, plus un noeud est connecté, moins ses voisins le sont.

Graphique et tableau 3 : de manière générale, plus un noeud est connecté, plus son coefficient de clustering est faible. Malgré tout, celui-ci reste plutôt élevé pour tous les noeuds.


Question 7

On choisit le noeud [Victor], dont le coefficient de clustering vaut 7/10, soit 0,7. Ce noeud possède 5 voisins ([Thibaud], [Armance], [Zélie], [Émilia] et [Emma]). Au vu des connexions, il suffirait d’ajouter un lien entre [Thibaud] et [Emma], un autre entre [Armance] et [Emma], et enfin un dernier entre [Emma] et [Zélie]. Ainsi, le coefficient de clustering vaudrait 10/10, soit 1.


Question 8

On choisit le noeud [Emma], dont le coefficient de clustering vaut 1. Ce noeud ne possède que 2 voisins : [Victor] et [Émilia]. Comme ces trois noeuds sont mutuellement liés par deux liens à chaque fois, le plus grand ensemble de liens que nous pouvons retirer du réseau sans modifier ni le nombre de voisins ni le coefficient de clustering vaut 20. On peut en effet retirer l’ensemble des autres noeuds du réseau (total : 17), en plus de 3 liens entre les noeuds [Victor], [Émilia] et [Emma].


Question 9

Proximité = inverse de la somme des distances entre le noeud et chacun des autres.

Noeud Proximité
[Victor] 1/(1+1+1+1+1) = 1/5
[Zélie] 1/(1+2+1+1+1) = 1/6
[Armance] 1/(1+1+2+1+1) = 1/6
[Thibaud] 1/(1+1+2+1+1) = 1/6
[Emma] 1/(1+2+2+2+1) = 1/8
[Émilia] 1/(1+1+1+1+1) = 1/5

Les noeuds [Victor] et [Émilia] ont la plus grande proximité, concordant avec le fait qu’ils soient les plus connectés au reste du réseau. Le noeud [Emma] a la plus petite proximité, car il n’a que 2 voisins et est donc le moins connecté au reste du réseau.

Intermédiarité = la somme, pour chaque paire des autres noeuds, de la fraction des chemins les plus courts entre ces noeuds qui passent par le premier.

Noeud Intermédiarité
[Victor] 1+1+1/2+1+1+1 = 5,5
[Zélie] 0
[Armance] 0
[Emma] 0
[Émilia] 0
[Thibaud] 0

[Victor] a la plus grande intermédiarité.