Utilisateur:Auriane SIREN/Modélisation des Réseaux (M1 SIREN, 2020)/Activité B
I. Réseau original
Question 1 : Je choisis les listes de Marine SIREN et EmiliaSIREN.
Question 2 & 3 :
* Dans ce graphe il y a eu une confusion avec l'ajout d'un lien sortant du nœud Auriane vers le nœud Copenhague (qui n'était pas présent dans l'activité A).
Question 4 :
On représente désormais le réseau sous forme de listes d'adjacence, c'est-à-dire qu'on ne prend en compte que les liens sortants pour chaque nœud :
| Noeud | Cible des liens |
|---|---|
| Auriane | [Pamplemousse, chocolat, Amsterdam, danse, plongée, New York, Stockholm, Copenhague, guitare, piano] |
| Marine | [Krav-maga, lecture, Sydney, Tokyo, smoothiez, pizzas, Copenhague, piano] |
| Emilia | [Venise, Barcelone, Mexico City, limonade, macarons, pâtes, volleyball, art, cinéma, chant guitare, piano] |
| Tous les autres noeuds | [] |
Les listes d'adjacence du reste des nœuds sont des ensembles vides car ils n'ont pas de lien de sortie vers d'autres nœuds dans ce graphe orienté.
Question 5 :
À partir de la liste d’adjacence, on peut calculer le degré de sortie de chaque nœud en additionnant le nombre de nœuds vers lesquels il a un lien, donc ceux présents dans sa liste d'adjacence. On peut obtenir le degré d'entrée en calculant le nombre de fois où un nœud apparaît dans les listes d'adjacence d'autres nœuds, en considérant qu'il sera nul pour les individus car il n'existe aucun lien entrant vers les individus.
Ainsi, nous obtenons pour les degrés d'entrée :
d-(Auriane) = 0, d-(Marine) = 0 et d-(Emilia) = 0
d-(Autres activités non-partagées) = 1
d-(Piano) = 3
d-(Copenhague) = 2
d-(Guitare) = 2
Et nous obtenons pour les degrés de sortie :
d+(Auriane) = 10
d+(Marine) = 8
d+(Emilia) = 12
d+(Autres activités non-partagées) = 0
Pour récapituler :
| Noeud | Degré d'entrée | Degré de sortie |
|---|---|---|
| Auriane | 0 | 10 |
| Marine | 0 | 8 |
| Emilia | 0 | 12 |
| Piano | 3 | 0 |
| Copenhague | 2 | 0 |
| Guitare | 2 | 0 |
| Autres activités non-partagées entre les participants | 1 | 0 |
Question 6 :
Il s'agit bien d'un réseau biparti car les groupes de nœuds individus ne sont pas liés entre eux, de même que les nœuds activités ne sont pas liés entre eux. Il est donc possible de scinder le graphe entre plusieurs groupes : les individus et les activités ou autres éléments.
Question 7 :
Non, on ne peut pas calculer le diamètre pour ce réseau car tous les nœuds ne sont pas connectés. Par exemple nous ne pouvons pas aller de [Emilia] à [Marine] ou de [pâtes] à [Copenhague]. La connectivité est même faible dans ce graphe orienté des individus vers les éléments car la distance maximale entre deux nœuds est de 1, on ne peut pas faire de chemin plus long en suivant le sens des liens du graphe.
II. Réseau projeté
Question 8 & 9 :
Pour la version simplifiée du graphe, nous ne considérons que les éléments communs entre les individus :
Pour la version complète nous définissons 3 graphes K d'éléments associés à chaque individu qui ne se connectent pas directement les uns aux autres mais se lient aux éléments qu'ils ont en commun :
Question 10 :
Matrice réalisée à partir de la représentation graphique simplifiée :
| Piano | Guitare | Copenhague | |
|---|---|---|---|
| Piano | 0 | 2 | 2 |
| Guitare | 2 | 0 | 1 |
| Copenhague | 2 | 1 | 0 |
Matrice réalisée à partir de la représentation graphique complète :
| Piano | Guitare | Copenhague | K-Marine (N=6) | K-Emilia (N=8) | K-Auriane (N=7) | |
|---|---|---|---|---|---|---|
| Piano | 0 | 2 | 2 | 6 | 8 | 7 |
| Guitare | 2 | 0 | 1 | 0 | 8 | 7 |
| Copenhague | 2 | 1 | 0 | 6 | 0 | 7 |
| Un membre quelconque de K-Marine | 1 | 0 | 1 | 5 | 0 | 0 |
| Un membre quelconque de K-Emilia | 1 | 1 | 0 | 0 | 7 | 0 |
| Un membre quelconque de K-Auriane | 1 | 1 | 1 | 0 | 0 | 6 |
Question 11 :
Le degré de chaque nœud peut se calculer en additionnant le nombre de liens pour un élément par ligne ou par colonne, sans distinction entre l'entrée et la sortie car il ne s'agit pas d'un graphe orienté (mis à part les nœuds entre K-graphes). Ainsi, nous obtenons avec la version simplifiée du graphe :
d(Piano) = 4
d(Guitare) = 3
d(Copenhague) = 3
Avec en additionnant les lignes de la version complète du graphe (et non ses colonnes car elle ne va pas dans le détail des K-graphes) nous obtenons les résultats suivants :
| Noeud | Degré |
|---|---|
| Piano | 25 |
| Guitare | 20 |
| Copenhague | 16 |
| Un membre quelconque de K-Marine | 7 |
| Un membre quelconque de K-Emilia | 9 |
| Un membre quelconque de K-Auriane | 9 |
Question 12 :
Ce n'est pas un réseau biparti car il y a bien des groupes de nœuds liés entre eux dans des sous-graphes complets. Ainsi, [Piano], [Guitare] et [Copenhague] sont reliés entre eux, il n'est donc pas possible de les scinder dans des sous-graphes différents. Ce n'est donc pas un réseau biparti.
Question 13 :
Dans la version simplifiée du graphe, il existe un chemin entre tous les nœuds. Le diamètre étant la plus grande distance (longueur du plus court chemin) entre chaque paire de nœud, il est égal à 1 dans cette version.
Comme la version complète du graphe reste non-orientée et connexe, nous pouvons calculer un diamètre. À partir du graphe on voit que la distance maximale existe entre K-Marine et K-Emilia. Il suffit donc de calculer par exemple la distance entre [Sydney] et [pâtes] = nous effectuons de sauts de [Sydney] à [Piano] puis de [Piano] à [pâtes], le diamètre est donc égal à 2.
Question 14 :
On ne peut dissocier aucun sous-graphe dans ce réseau, les nœuds étant tous voisins directs. Il n'existe donc qu'une seule composante connexe dans ce réseau, c'est donc un graphe connexe.
III. Réseau projeté 2
Questions 15 et 16 :
Question 17 :
| Emilia | Marine | Auriane | |
|---|---|---|---|
| Emilia | 0 | 1 | 2 |
| Marine | 1 | 0 | 2 |
| Auriane | 2 | 2 | 0 |
Question 18 :
On déduit le degré de chaque nœud en ajoutant les lignes ou les colonnes. Il n'y a aucune différence entre degré entrant ou sortant car il s'agit d'un graphe non-orienté, la matrice est donc symétrique.
| Nœud | Degré |
|---|---|
| Emilia | 3 |
| Marine | 3 |
| Auriane | 4 |
Question 19 :
Le réseau n'est pas biparti car tous les nœuds du graphe sont reliés entre eux et voisins directs, le graphe est complet. On ne peut donc pas séparer les nœuds [Marine], [Emilia] et [Auriane] en deux groupes distincts car ils sont reliés par les liens [piano], [guitare] et [Copenhague].
Question 20 :
Le diamètre du réseau est la plus grande distance qui existe entre deux nœuds d'un même graphe. Dans le cas de notre graphe non-orienté, tous les nœuds étant voisins directs, le diamètre est de 1.
Question 21 :
Comme pour le réseau projeté précédent, il n'existe aucun sous-graphe dans ce réseau projeté et tous les nœuds sont liés. Il n'y a donc qu'une seule composante connexe dans ce réseau, le graphe est donc connexe.