Utilisateur:Alice Joie Dauphine/Modélisation des Réseaux (M1 SIREN, 2022)/Activité B

Réseau

1. Le niveau le plus granulaire de mes réponses étaient tel que :

Réseau joint d'Alice, Mathilde et Sophie

Alice -> basketball, handball, guitare, piano, clarinette, vin, cheesecake, omelette, valse, danse contemporaine

2. J'ai remarqué que Mathilde et Sophie avaient des noeuds en commun avec moi, voici les éléments composites de leurs réseaux :

Mathilde ->  bachata, salsa, musculation, RPM, ramens, vin, guitare, piano

Sophie -> piano, batterie, fajitas, couscous, limonade, ski, danse, basketball, danse contemporaine

3. Voici ci-contre le réseau composé des cas concrets de nos trois réseaux :

Questions

Question 1

Le réseau précédent est un graphe connexe si on ignore l'orientation. En effet, l'ensemble de ce réseau représente une composante connexe, car quels que soient deux sommets de ce graphe, il existe un chemin reliant ces deux sommets.

En ce qui concerne les composantes fortement connexes, chaque sommet représente une composante fortement connexe. En prenant en compte l'orientation du graphe, il n'existe pas de sous-ensemble composé de plusieurs sommets dans lequel il y a un chemin pour toute paire de sommet.

Les composantes fortement connexes sont donc : {Alice}, {Mathilde}, {Sophie}, {basketball}, {handball}, {ski}, {RPM}, {musculation}, {danse}, {danse contemporaine}, {bachata}, {salsa}, {valse}, {guitare}, {piano}, {clarinette}, {batterie}, {fajitas}, {couscous}, {limonade}, {omelette}, {cheescake}, {vin}, {ramens}.

Question 2

1. Il n'existe pas de triangle dans ce réseau.
2. Le plus petit cycle de ce réseau, en ne considérant pas l'orientation, possède une distance de 4. Il en existe plusieurs, six exactement : (Mathilde, vin, Alice, guitare, Mathilde), (Mathilde, vin, Alice, piano, Mathilde), (Mathilde, guitare, Alice, piano, Mathilde), (Sophie, piano, Alice, danse contemporaine), (Sophie, danse contemporaine, Alice, basketball, Sophie), (Sophie, piano, Alice, basketball, Sophie)
3. Si on prenait l'orientation des liens, il n'y aurait pas de cycles dans ce réseau. En effet, les personnes, Sophie, Mathilde et Alice n'ont que des liens sortants et non entrants.

Question 3

Distribution des degrés du graphe non-orientés :

Graphe non orienté

0	1	2	3	4	5	6	7	8	9	10
0	16	4	1	0	0	0	0	1	1	1

Les sommets à remarquer :

d(guitare) = 2

d(vin) = 2

d(danse contemporaine) = 2

d(basketball) = 2

d(piano) = 3

d(Mathilde) = 8

d(Sophie) = 9

d(Alice) = 10

Les autres sommets possèdent un degré de 1.

Distribution des degrés sortants et entrants du graphe orienté :

Degrés entrant

0	1	2	3
3	16	4	1

A remarquer :

d⁻(guitare) = 2

d⁻(vin) = 2

d⁻(danse contemporaine) = 2

d⁻(basketball) = 2

d⁻(piano) = 3

Les noeuds ayant un degré strictement supérieur à 1 représente ceux en commun entre les différentes personnes du réseau (donc si c'est un noeud commun et que l'on a considéré trois personnes différentes, on aura 1 < d⁻(noeud commun) ≤ 3

Degrés sortant

0	1	2	3	4	5	6	7	8	9	10
21	0	0	0	0	0	0	0	1	1	1

d ⁺(Alice) = 10

d ⁺(Sophie) = 9

d ⁺(Mathilde) = 8

Les préférences ne peuvent avoir de liens orientés vers les personnes, seul l'inverse est possible.

Distribution de degrés

Non orientés	Entrant	Sortants

Question 4

Réseau simplifié orienté

Réseau simplifié non orienté

1. Voici les matrices adjacentes pour le cas du réseau orienté et non-orienté.

Matrice adjacente pour le réseau orienté

	Alice	Mathilde	Sophie	Guitare	Vin	Danse contempo	Basketball	Piano
Alice	0	0	0	1	1	1	1	1
Mathilde	0	0	0	1	1	0	0	1
Sophie	0	0	0	0	0	1	1	1
Guitare	0	0	0	0	0	0	0	0
Vin	0	0	0	0	0	0	0	0
Danse contempo	0	0	0	0	0	0	0	0
Basketball	0	0	0	0	0	0	0	0
Piano	0	0	0	0	0	0	0	0

Matrice adjacente pour le réseau non-orienté

	Alice	Mathilde	Sophie	Guitare	Vin	Danse contempo	Basketball	Piano
Alice	0	0	0	1	1	1	1	1
Mathilde	0	0	0	1	1	0	0	1
Sophie	0	0	0	0	0	1	1	1
Guitare	1	1	0	0	0	0	0	0
Vin	1	1	0	0	0	0	0	0
Danse contempo	1	0	1	0	0	0	0	0
Basketball	1	0	1	0	0	0	0	0
Piano	1	1	1	0	0	0	0	0

2.1 Projections non-orientés :

- Sur les personnes :

[ Alice ] - Guitare - [ Mathilde ]

[ Alice ] - Vin - [ Mathilde ]

[ Alice ] - Danse contemporaine - [ Sophie ]

[ Alice ] - Basketball - [ Sophie ]

[ Alice ] - Piano - [ Mathilde ]

[ Sophie ] - Piano - [ Alice ]

[ Mathilde ] - Piano - [ Sophie ]

- Sur les objets :

[ Basketball ] - Alice - [ Guitare ]

[ Basketball ] - Alice - [ Vin ]

[ Basketball ] - Alice - [ Danse contemporaine ]

[ Basketball ] - Sophie - [ Piano ]

[ Guitare ] - Mathilde - [ Vin ]

[ Guitare ] - Alice - [ Danse contemporaine ]

[ Guitare ] - Mathilde - [ Piano ]

[ Vin ] - Alice - [ Danse contemporaine ]

[ Vin ] - Mathilde - [ Piano ]

[ Piano ] - Sophie - [ Danse contemporaine ] 2.2 Il n'y a qu'une seule composante connexe

Pour ce qui est du graphe qui établit la synthèse de ce réseau simplifié, le diamètre est de 5. En effet, on peut utiliser le chemin suivant :

Δ {Mathilde, vin, Alice, basketball, Sophie, piano} = 5.

3. Pour transformer ce réseau simplifié en un réseau fortement connexe, il faudrait que chaque noeud ait au moins un lien entrant et un lien sortant.

Dans mon réseau, les personnes n'ont pas de lien entrant, il faudrait donc ajouter au moins 3 liens pour qu'on puise arriver à chacune des 3 personnes. A son tour, les objets aussi n'ont pas de lien sortant, même problématique mais avec 5 liens sortants. Voyons donc si on peut ajouter 5 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 :

[ Basketball ] -> [ Alice ]

Réseau fortement connexe

[ Vin ] -> [ Alice ]

[ Danse contemporaine ] -> [ Sophie ]

[ Piano ] -> [ Sophie ]

[ Guitare ] -> [ Mathilde ]

On peut passer par tous les noeuds du graphe, donc notre réseau est maintenant fortement connexe :