Utilisateur:Solstag/Modélisation des Réseaux (M1 SIREN, 2020)/Activité B
Bonjour !
Au lieu de corriger l'activité B en cours, je vous donne la correction ici, avec des notes explicatives pour éclairer les erreurs les plus communs que j'ai constaté dans vos activités. Les réponses ici sont cependant particulières à mon cas, et ne servent qu'à exposer les concepts. Vous devez lire attentivement ce document, comme si c'était l'un des cours, comprendre ce qui s'applique à ton réseau et corriger ton activité. N'hésitez pas à poser des questions dans la page de discussion de l'activité ou par mail !
Réseau original[modifier | modifier le wikicode]
Pour l'item (1.), Je choisis Auriane et Quentin.
L'item (2.) simplement explique quoi dessiner dans l'item (3.). Je note les éléments auxquels chaque personne est liée. Certains élément sont présents dans plus qu'une liste. Ces éléments seront partagés dans le graphe, avec des liens vers eux provenant de plus d'une personne. On voit ça dans le dessine ci-dessous, que j'ai choisi de faire avec un logiciel pour dessiner des graphes en forme d'art ASCII. ;-)
┌─────────────────────┐┌──────────┐
┌──────────────────> │ plongée sous-marine ││ yoga │
│ └─────────────────────┘└──────────┘
│ ∧ ∧
│ │ │
│ │ │
│ ┌───────────┐ ▛▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▜ ┌───────────────────┐
│ │ avocat │ <── ▌ ▐ ──> │ feuilles de vigne │
│ └───────────┘ ▌ ▐ └───────────────────┘
│ ┌───────────┐ ▌ ▐ ┌───────────────────┐
│ │ cachaça │ <── ▌ Ale Abdo ▐ ──> │ guitare │ <─────┐
│ └───────────┘ ▌ ▐ └───────────────────┘ │
│ ┌───────────┐ ▌ ▐ ┌───────────────────┐ │
│ │ chant │ <── ▌ ▐ ──> │ origami │ │
│ └───────────┘ ▙▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▟ └───────────────────┘ │
│ │ │ │
│ │ │ │
│ ∨ ∨ │
│ ┌─────────────────────┐┌──────────┐ │
│ │ Beyrouth ││ Tokyo │ <──────────────────────────┐ │
│ └─────────────────────┘└──────────┘ │ │
│ │ │
└──────────────────────┐ ┌─────────────────────────────────────┼────┘
│ │ │
┌───────────┐ ▛▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▜ ┌───────────────────┐ │
│ Stockholm │ <── ▌ ▐ ──> │ pamplemousse │ │
└───────────┘ ▌ ▐ └───────────────────┘ │
┌───────────┐ ▌ ▐ ┌───────────────────┐ │
│ chocolat │ <── ▌ Auriane ▐ ──> │ piano │ │
└───────────┘ ▌ ▐ └───────────────────┘ │
┌───────────┐ ▌ ▐ │
│ danse │ <── ▌ ▐ │
└───────────┘ ▙▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▟ │
│ │ │
│ │ │
∨ ∨ │
┌─────────────────────┐┌──────────┐ │
│ Amsterdam ││ New York │ │
└─────────────────────┘└──────────┘ │
│
┌─────────────────────────────────────┘
│
┌───────────┐ ▛▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▜ ┌───────────────────┐ ┌─────────────┐
│ batterie │ <── ▌ ▐ ──> │ judo │ │ panna cotta │
└───────────┘ ▌ ▐ └───────────────────┘ └─────────────┘
▌ ▐ ∧
▌ ▐ ────────────────────────────────┘
▌ Quentin ▐
┌───────────┐ ▌ ▐ ┌───────────────────┐
│ clavier │ <── ▌ ▐ ──> │ marimba │
└───────────┘ ▌ ▐ └───────────────────┘
┌───────────┐ ▌ ▐ ┌───────────────────┐
│ houmous │ <── ▌ ▐ ──> │ natation │
└───────────┘ ▙▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▟ └───────────────────┘
│ │
│ │
∨ ∨
┌─────────────────────┐┌──────────┐
│ Dar es Salam ││ Londres │
└─────────────────────┘└──────────┘
4. Dans une liste d'adjacence on représente les liens sortants pour chaque nœud. Dans notre cas, les seuls nœuds avec des liens sortants dans notre liste, par construction, sont les personnes. Donc on a :
| Nœud | Cibles des liens |
|---|---|
| [ Ale Abdo ] | ( [ guitare ], [ chant ], [ avocat ], [ cachaça ], [ feuilles de vigne ], [ origami ], [ yoga ], [ plongée sous-marine ], [ Beyrouth ], [ Tokyo ] ) |
| [ Auriane ] | ( [ piano ], [ guitare ], [ danse ], [ plongée sous-marine ], [ New York ], [ Stockholm ], [ Amsterdam ], [ chocolat ], [ pamplemousse ] ) |
| [ Quentin ] | ( [ batterie ], [ clavier ], [ marimba ], [ natation ], [ judo ], [ Tokyo ], [ Londres ], [ Dar es Salam ], [ panna cotta ], [ houmous ] ) |
| Tous les autres nœuds | ( ) |
5. Le dégrée sortant d'un nœud est la quantité d'éléments dans sa lista d'adjacence. Le degré entrant est le nombre de fois qu'il figure dans toutes les listes d'adjacence. Dans notre cas, encore par construction, les liens sortent des personnes et arrivent dans les éléments. Donc le degré entrant des personnes est zéro, ainsi que le degré sortant de n'importe que élément. Pour les autres, on note dans la liste et par le graphe dessiné que la plupart des éléments ont un degré entrant de 1, car apparaît une seule fois dans la liste d'une seule personne, tandis que trois éléments ont un degré égal a 2, car partagé par deux personnes également une fois dans la liste de chacune. Aucun élément figure dans les trois listes. D'une telle façon qu'on peut écrire le tableau de degrés :
| Nœud | Entré | Sortie |
|---|---|---|
| [ Ale Abdo ] | 0 | 10 |
| [ Auriane ] | 0 | 9 |
| [ Quentin ] | 0 | 10 |
| [ guitare ] | 2 | 0 |
| [ plongée sous-marine ] | 2 | 0 |
| [ Tokyo ] | 2 | 0 |
| Tous le autres nœuds | 1 | 0 |
6. On peut séparer les nœuds dans deux groupes: personnes et éléments. De tel sorte qu'il n'y a pas de lien entre les nœuds d'un même groupe. Par conséquence, oui, on peut dire que ce réseau est biparti. Le fait que on pourrait le diviser dans trois groupes avec cette même propriété est inconséquent. En fait, être biparti est une condition plus forte que d'être triparti ou N-parti. Comme c'est une condition interne aux groupes, le plus on peut diviser le graphe le plus facile il sera de trouver des groupes sans connexions internes. À la limite, tous les réseaux à N nœuds sont N-partis, dans N groupes avec un seul élément et donc sans lien interne.
Je vous note qu'être biparti impose que toutes les marches sur le réseau doivent alterner la partition à chaque pas, car pas de lien à l'intérieur des partitions, et donc tout chemin qui permet de retourner à son nœud de départ doit faire un nombre pair d'aller-retours entre les partitions. C'est à dire que dans un réseau biparti il n'y a pas de cycle à taille impair. Dans un réseau non-orienté, la réciproque est aussi vraie: s'il n'y a pas de cycle impair, le réseau est biparti. Car pour trouver une bipartition des nœuds il suffit de marcher sur le réseau en distribuant aux nœuds des étiquettes 0 et 1 alternées. Alors si on pouvait trouver deux nœuds avec la même étiquette liés, et donc niant la bipartition, en retraçant le parcours de la marche on aurait trouvé aussi un cycle impair, une contradiction.
7. Ce réseau orienté n'est pas fortement connexe, car, par exemple, on ne peux pas aller de [ pamplemousse ] à [ danse ]. En réalité, il est très peu connecté : on ne peux passer que d'une personne à ses éléments, ne pouvant ni revenir ni repartir ailleurs. En conséquence, dans le sens de plus grande distance entre deux nœuds, il n'y a pas de diamètre pour ce réseau car il n'y a pas de chemin entre tous les nœuds. Cependant, on peut observer que le chemin le plus long qu'on peut parcourir dans le réseau - d'aller d'une personne à un de ses éléments - est de longueur 1.
Réseau projeté[modifier | modifier le wikicode]
8. L'énoncé nous dit de rajouter un lien non-orienté entre deux éléments pour chaque personne qu'on trouve connectée à tous les deux dans le réseau original. Alors, cela veut dire que les personnes induisent des liens entre les éléments auxquels elles se connectent. Tous les éléments liés à un même personne sont alors liées entre eux, deux à deux. Cela équivaut à des sous-graphes dits complets ou K-graphes. On peut alors traiter séparément dans notre réseau les éléments qui ne se connectent qu'à une seule personne, et donc ne participent qu'à ces graphes complets, et ceux qui se trouvent dans la liste de plusieurs personnes, et qu'auront une connectivité plus riche.
Pour simplifier le dessin et la matrice, on peut définir trois K-graphes d'éléments, un pour chaque personne, qu'on appellera K-Ale Abdo, K-Auriane et K-Quentin, chacun contenant uniquement les éléments dont la connectivité dans le graphe projeté est complètement déterminé par leur seul lien dans le graphe original provenant d'une de ces personnes. Par conséquence, ses graphes complets ne se connectent pas directement entre eux, mais se retrouvent par les éléments qui se lient à tous d'un côté et de l'autre, car participent aux listes des deux personnes : [ guitare ] et [ plongée sous-marine ], qui se connectent une fois à chacun des nœuds de K-Ale Abdo et K-Auriane, et deux fois entre eux-mêmes car une fois par personne les partageant ; et [ Tokyo ], qui se connecte une fois à chacun des nœuds de K-Ale Abdo et K-Quentin.
9. En prenant compte que les blocs avec multiples noms représentent des K-graphes où tous les pairs se connectent, et que les liens avec ces K-graphes représentent des multiples connexions à chacun des éléments, on peut dessiner notre réseau :
┌-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·┐ ! ! ! ┌─────────────────────┐ ┌───────────────────┐ ┌───────┐ ┌──────────────┐ ! │ │ │ │ │ │ │ (K-Quentin) │ ! │ │ │ │ │ │ │ batterie │ ! │ │ │ │ │ │ │ clavier │ ! │ │ │ │ │ │ │ marimba │ ! │ plongée sous-marine │ │ │ │ Tokyo │ │ natation │ ! │ │ │ │ │ │ │ judo │ ! │ │ │ │ │ │ │ Londres │ ! │ │ │ (K-Ale Abdo) │ │ │ │ Dar es Salam │ ! Auriane │ │ Ale Abdo │ chant │ Ale │ │ Quentin │ panna cotta │ ! ┌·-·-·-·-·-·-·-·-·-·-·-·- │ │ ·-·-·-·-·-· │ avocat │ ·-·-·- │ │ -·-·-·-·-· │ houmous │ ! ! └─────────────────────┘ │ cachaça │ └───────┘ └──────────────┘ ! ! ! │ feuilles de vigne │ ! ! ! Auriane │ origami │ ! ! ! │ yoga │ ! ┌──────────────┐ ┌─────────────────────┐ │ Beyrouth │ ! │ (K-Auriane) │ │ │ │ │ ! │ piano │ │ │ │ │ ! │ danse │ │ │ │ │ ! │ New York │ │ │ │ │ ! │ Stockholm │ │ │ │ │ ! │ Amsterdam │ │ guitare │ │ │ ! │ chocolat │ │ │ Ale Abdo │ │ ! │ pamplemousse │ │ │ -·-·-·-·-·- │ │ ! └──────────────┘ │ │ └───────────────────┘ ! ! Auriane │ │ ! └·-·-·-·-·-·-·-·-·-·-·-·- │ │ ! └─────────────────────┘ ! Ale Abdo ! └-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·┘
10. Comme les membres des chacun des K-graphes ont exactement les mêmes connexions, on peut écrire la matrice d'adjacence en forme compacte. Il faudra prendre en compte que les colonnes pour les K-graphes représentent des liens vers plusieurs nœuds : soit vers ses voisins extérieurs, qui se connectent à tous les nœuds du K-graphe avec un lien par nœud ; soit vers ses propres nœuds, sur la diagonale, où chacun de ses nœuds se connecte à tous les autres membres du K-graphe :
| Nœuds\Nœuds | [ guitare ] | [ plongée sous-marine ] | [ Tokyo ] | K-Ale Abdo (N=7) | K-Auriane (N=7) | K-Quentin (N=9) |
|---|---|---|---|---|---|---|
| [ guitare ] | 0 | 2 | 0 | 7 | 7 | 0 |
| [ plongée sous-marine ] | 2 | 0 | 0 | 7 | 7 | 0 |
| [ Tokyo ] | 0 | 0 | 0 | 7 | 0 | 9 |
| Un membre quelconque de K-Ale Abdo | 1 | 1 | 1 | 6 | 0 | 0 |
| Un membre quelconque de K-Auriane | 1 | 1 | 0 | 0 | 6 | 0 |
| Un membre quelconque de K-Quentin | 0 | 0 | 1 | 0 | 0 | 8 |
Comme le réseau est non-orienté, on note le caractère symétrique de la matrice d'adjacence.
11. Le degré est simplement la somme de la ligne dans la matrice d'adjacence. Dans le cas non-orienté la matrice est symétrique et peu importe si on somme la ligne ou colonne. Dans un réseau orienté la ligne fournirait le degré sortant et la colonne celui entrant. Pour autant, dans notre matrice compacte, il faut faire attention qu'une partie des colonnes ne représente pas des nœuds individuels mais des sous-graphes complets, et que les lignes ne comptent pas tous les membres de ces sous-graphes, mais uniquement un membre, non spécifié, car leurs connectivités sont équivalentes. Dans ce cas, pour obtenir le degré des nœuds il faut bien sommer pour chaque ligne, donc pour les nœuds, sur toutes les les colonnes, donc sur tout le graphe : les nœuds mis à part plus le K-graphes. Le tableau pour les degré sera alors :
| Nœud | degré |
|---|---|
| [ guitare ] | 16 |
| [ plongée sous-marine ] | 16 |
| [ Tokyo ] | 16 |
| Un membre quelconque de K-Ale Abdo | 9 |
| Un membre quelconque de K-Auriane | 8 |
| Un membre quelconque de K-Quentin | 9 |
12. Le réseau contient plusieurs cycles impairs de diverses longueurs, y compris plusieurs "triangles" grâce à ses sous-graphes complets. Par exemple: < [ avocat ] -- [ feuilles de vigne ] -- [ yoga ] -- [ avocat ] >. Visiblement, et comme discuté dans l'item (6.), on ne peut pas répartir ces trois nœuds dans deux groupes sans finir avec un lien entre nœuds d'un même groupe. Donc, peu importe le reste du réseau, l'existence de ce seul triangle suffit pour rendre une bipartition impossible. Alors ce réseau n'est pas biparti.
13. Le diamètre est la plus grande distance entre deux nœuds. Ce graphe étant non-orienté et connexe, on peut définir une distance pour tous les pairs de nœuds, et donc un diamètre. C'est facile de voir à partir du dessin que la distance maximale est atteinte entre les nœuds de K-Quentin et ceux de K-Auriane. Comme dans notre graphe les nœuds de chacun de ces K-graphes se connectent tous aux mêmes nœuds extérieurs, ils sont équivalents en termes de distances. Prenons alors la distance entre [ danse ] et [ judo ]. Le chemin le plus court fait 4 sauts : à partir de [ danse ], il passe par [ Tokyo ], par un membre de K-Ale Abdo, et par [ guitare ] ou [ plongée sous-marine ], pour enfin arriver à [ judo ]. Cela est alors la valeur de la distance maximale, c'est à dire, du diamètre : 4.
14. On vient d'utiliser le fait que le graphe est connexe. C'est à dire, qu'il a une seule composante connexe. Cela signifie qu'il y a un chemin dans le graphe entre n'importe quel pair de nœuds, ce qui on peut facilement constater avec l'aide de notre dessin.
Réseau projeté II[modifier | modifier le wikicode]
9. On ne trouve que trois personnes dans le réseau original, et donc on aura trois nœuds dans ce réseau projeté. Et chaque pair de personnes sera connecté par autant d'éléments qu'ils partagent.
10.
▛▀▀▀▀▀▀▀▀▀▜ Tokyo ▛▀▀▀▀▀▀▀▀▀▀▜
▌ Quentin ▐ ──────── ▌ Ale Abdo ▐ ─┐
▙▄▄▄▄▄▄▄▄▄▟ ▙▄▄▄▄▄▄▄▄▄▄▟ │
│ │
│ guitare │ plongée sous-marine
│ │
▛▀▀▀▀▀▀▀▀▀▀▜ │
▌ Auriane ▐ ─┘
▙▄▄▄▄▄▄▄▄▄▄▟
11.
| Ale Abdo | Auriane | Quentin | |
|---|---|---|---|
| Ale Abdo | 0 | 2 | 1 |
| Auriane | 2 | 0 | 0 |
| Quentin | 1 | 0 | 0 |
12. Les degrés s'obtiennent par l'addition des valeurs dans la ligne correspondante. Comme le graphe est non-orienté il n'y a qu'un seul degré et on pourrait également faire l'addition par colonne.
| Nœud | Degré |
|---|---|
| Ale Abdo | 3 |
| Auriane | 2 |
| Quentin | 1 |
13. Le réseau est biparti avec parties : {[ Ale Abdo ]} et {[ Auriane ], [ Quentin ]}, car il n'y a pas de lien entre les membres de chaque partie.
14. Le diamètre est 2 : la distance entre [ Auriane ] et [ Quentin ].
15. Le réseau a une seule composante connexe, car on peu trouver un chemin entre tous les pairs de nœuds.
Une observation intéressante est que [ Auriane ] est connecté à [ piano ] tandis que [ Quentin ] est connecté à [ clavier ]. Si pour les traitement de nos données nous disposions d'un vocabulaire contrôlé, il serait peut-être le cas qu'ils se trouveraient connectés par leurs instruments. Et, si on disposait d'une ontologie d'instruments de musique, même si le vocabulaire distinguait les deux, il nous serait possible d'inférer une équivalence entre [ clavier ] et [ piano ] si pour notre application ce niveau de distinction n'était pas importante. En outre, une ontologie nous permettrait de prendre en compte, par exemple, la proximité entre [ natation ] et [ plongée sous-marine ]. Avec Wikidata, on dispose d'un tel vocabulaire contrôlé et d'une ample ontologie permettant de faire quelques uns de ces liens. I.e. <https://www.wikidata.org/wiki/Q5994> (piano) est une sous-classe de <https://www.wikidata.org/wiki/Q52954> (instrument à clavier), comme <https://www.wikidata.org/wiki/Q6388> (natation) et <https://www.wikidata.org/wiki/Q179643> (plongée sous-marine) sont sous-classes de <https://www.wikidata.org/wiki/Q3467704> (locomotion aquatique).