Utilisateur:Bourgeois Tom/Modélisation des Réseaux (M1 SIREN, 2022)/Activité B
1. Gardez uniquement les cas concrets de votre réseau, c'est-à-dire, le niveau le plus granulaire de réponse aux questions.
Tom -> Lasagne, Bière, London Mule, le rock, la salsa, Handball, tennis, Saxophone, batterie
2. Trouvez deux collègues dont les réseaux de l'activité A ont des nœuds en commun avec le votre.
Hannah roux-brion -> oeufs, fromage, St Germain, rock, piano, athlétisme, tennis, course de fond
Daniel -> pâte carbonara, pizza, omelette aux pommes de terre, flamenco, guitare, batterie, escrime, tennis, surf
3. Construisez un réseau unique avec les nœuds et liens de ces trois réseaux, toujours gardant seulement les cas concrets, dont les personnes.
1. Identifiez les composantes connexes (c'est-à-dire, les composantes ignorant l'orientation des liens) et fortement connexes (prenant en compte l'orientation des liens).
Il y a une seule composante connexe, c'est tout le graphe, car par construction toutes les personnes sont liées à [Tom ], et tous les autres nœuds sont liés à au moins une personne.
Chaque nœud du graphe est une composante fortement connexe, car dans ce graphe il n'y a pas deux nœuds entre lesquels on puisse aller et revenir en prenant compte l'orientation des liens ; on ne peut que partir d'une personne et arriver à un nœud objet (non-personne), d'où on ne peut pas sortir
2. Si on ne prend pas en compte l'orientation des liens :
1. Ce réseau contient-il des triangles ? C'est-à-dire, y a-t-il trois nœuds formant un cycle (A—B—C—A)
Il n'existe pas de triangle dans ce réseau.
2. Si non, quel est la taille du plus petit cycle qu'il contient
Le plus petit cycle a une taille de 4
3. Si on prenait en compte l'orientation des liens, comment ça changerait les réponses précédentes ?
Si on prenait l'orientation des liens, il n'y aurait pas de cycles dans ce réseau.
3. Faites le graphique de distribution de degrés, en considérant les liens du graphe comme non-orientés, puis le graphique de distribution de degrés sortant et entrant du graphe orienté. Vous pouvez, alternativement, présenter ces informations sous forme de tableaux.
| Graphe non orienté | ||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 19 | 2 | 1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
Distribution des degrés sortants et entrants du graphe orienté :
| Degrés entrant | |||
| 0 | 1 | 2 | 3 |
| 3 | 16 | 2 | 1 |
| Degrés sortant | ||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 26 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
4. Gardez dans votre réseau uniquement les nœuds à degré total — entrant plus sortant — supérieur à 1.
1. Écrivez la matrice d'adjacence de ce réseau simplifié.
Le réseau simplifié :
Matrice adjacente pour le réseau orienté
| tom | hannah | Daniel | Tennis | Rock | Batterie | |
| tom | 0 | 0 | 0 | 1 | 1 | 1 |
| hannah | 0 | 0 | 0 | 1 | 1 | 0 |
| Daniel | 0 | 0 | 0 | 1 | 0 | 1 |
| Tennis | 0 | 0 | 0 | 0 | 0 | 0 |
| Rock | 0 | 0 | 0 | 0 | 0 | 0 |
| Batterie | 0 | 0 | 0 | 0 | 0 | 0 |
Matrice adjacente pour le réseau non-orienté
| tom | hannah | Daniel | Tennis | Rock | Batterie | |
| tom | 0 | 0 | 0 | 1 | 1 | 1 |
| hannah | 0 | 0 | 0 | 1 | 1 | 0 |
| Daniel | 0 | 0 | 0 | 1 | 0 | 1 |
| Tennis | 1 | 1 | 1 | 0 | 0 | 0 |
| Rock | 1 | 1 | 0 | 0 | 0 | 0 |
| Batterie | 1 | 0 | 1 | 0 | 0 | 0 |
2. Considérez les liens du réseau simplifié comme non-orientés et:
1. Projetez-le sur les nœuds correspondant aux personnes. Projetez-le sur les nœuds qui ne sont pas des personnes.
Projections non-orientés :
· Sur les personnes :
[Tom] - Tennis – [Hannah]
[Tom] - Tennis – [Daniel]
[Tom] - Batterie – [Daniel]
[Hannah] - Tennis – [Daniel]
· Sur les objets :
[Batterie] - Tom – [Tennis]
[Batterie] - Daniel – [Tennis]
1. Calculez le diamètre de chacune de ses composantes connexes.
Il n'y a qu'une seule composante connexe et la plus grande distance est 3 et on la trouve pour aller de [Hannah] à [Batterie]
2. On peut transformer le réseau simplifié dans un réseau fortement connexe en y rajoutant un minimum de liens orientés. Quels liens rajouter ?
Dans mon réseau, les personnes n'ont pas de lien entrant, il faudrait donc ajouter au moins 3 liens pour qu'on puisse arriver à chacune des 3 personnes. A son tour, les objets aussi n'ont pas de lien sortant, même problématique. Voyons donc si on peut ajouter 3 liens partant des objets vers les personnes, d'une telle sorte qu'on puisse circuler dans le graphe. Si on rajoute au graphe les liens :
[Batterie] -> [Daniel]
[Tennis] -> [Hannah]
[Rock] –> [Tom]
On voit que ça suffit pour qu'on puisse passer entre tous les nœuds du graphe, lui rendant fortement connexe !