Activité - Modéliser un réseau social¶

Sources

Exercices¶

Activité notée

Cette activité sera notée sur 10 points. Répondez aux questions ci-dessous sur une feuille que vous me rendrez. N'oubliez pas de mettre votre nom, votre prénom et votre classe !

Voici un graphe illustrant un réseau social ayant 6 abonnés (A, B, C, D, E et F) tel que :

A est ami avec B, C et D
B est ami avec A et D
C est ami avec A, E et D
D est ami avec tous les autres abonnés
E est ami avec C, D et F
F est ami avec E et D

Les cercles sont appelés des sommets et les segments de droites des arêtes.

Vocabulaire

Chaîne : Dans un graphe, une chaîne reliant un sommet x à un sommet y est définie par une suite finie d'arêtes consécutives, reliant x à y.
Exemple : Dans le graphe donné ci-dessus, A-D-E-C est une chaîne de 3 arêtes

Distance entre 2 sommets : La distance entre deux sommets d'un graphe est le nombre minimum d'arêtes d'une chaîne allant de l'un à l'autre.
Exemple : La distance entre le sommet A et le sommet F est de 2 (chaîne A-D-F).

Écartement : L'écartement d'un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe.
Exemple : distance (A-B) = 1 ; distance (A-C) = 1 ; distance (A-D) = 1 ; distance (A-E) = 2 ; distance (A-F) = 2 ; nous pouvons donc dire que la distance maximale existant entre le sommet A et les autres sommets du graphe est de 2 (distance (A-E) et distance (A-F)). Nous pouvons donc dire que l'écartement de A est de 2.

Centre : On appelle centre d'un graphe, le sommet d'écartement minimal (le centre n'est pas nécessairement unique).
Exemple : Dans le graphe 1 tous les sommets ont un écartement de 2 à l'exception du sommet D qui a un écartement de 1, nous pouvons donc affirmer que le centre du graphe 1 est le sommet D.

Rayon : On appelle rayon d'un graphe G, l'écartement d'un centre de G.
Exemple : D a un écartement de 1, c'est le centre du graphe, nous pouvons donc dire que le rayon du graphe est de 1.

Diamètre : On appelle diamètre d'un graphe G, la distance maximale entre deux sommets du graphe G.
Exemple : Dans le graphe 1 la distance maximale entre 2 sommets est de 2, nous pouvons donc dire que le diamètre du graphe est de 2.

Exercice 1

En utilisant le graphe présenté précédemment, répondre aux consignes suivantes :
1. Donner une chaine de ce graphe composée de 4 arêtes et une chaine de 5 arêtes.
2. Déterminer la distance entre le sommet C et B et la distance entre le sommet B et E.
3. Déterminer l’écartement de D ainsi que l’écartement de E.

Réponse exercice 1

Chaîne de 4 arêtes : B-A-D-F-E, ou encore B-A-C-E-F...
Chaîne de 5 arêtes : F-E-C-A-B-D, ou encore B-D-F-E-C-A...
La distance entre C et B est de 2 arêtes (c'est le plus petit nombre d'arêtes qui les sépare), et la distance entre B et E est également de 2 arêtes.
L'écartement de D est de 1 (car sa distance avec tous les autres sommets est de 1), et l'écartement de E est de 2.

Exercice 2

Construire un graphe d’un réseau social à partir des informations suivantes :

Albert est ami avec Bryan et Edouard
Bryan est ami avec Albert et Charlotte
Charlotte est ami avec Bryan, Flavien et Daniel
Daniel est ami avec Charlotte, Flavien et Edouard
Edouard est ami avec Albert, Daniel et Flavien
Flavien est ami avec Charlotte, Daniel et Edouard

(Vous pouvez utiliser des lettres de A à F si vous préférez.)

Réponse exercice 2

Voici le graphe obtenu (on peut le représenter différemment, tant qu'il contient les mêmes sommets et les mêmes arêtes) :

Graphe de l'exercice 2

Ce graphe contient :

6 sommets
8 arêtes
Centres du graphe : 'Albert', 'Bryan', 'Edouard', 'Charlotte', 'Flavien' et 'Daniel' sont tous des centres, car ils ont tous le même écartement (qui est de 2).
Diamètre du graphe : 2 (car la distance maximale entre deux sommets est de 2)

Exercice 3

Déterminer le (ou les) centre(s) du graphe ci-dessous.
En déduire son rayon et son diamètre.

Modélisation d'un graphe

Réponse exercice 3

Centres du graphe

Pour déterminer le centre du graphe, regardons d'abord l'écartement de chaque sommet :

A a un écartement de 3,
B a un écartement de 3,
C a un écartement de 2,
D a un écartement de 2,
E a un écartement de 3,
F a un écartement de 2,
G a un écartement de 3.

Les centres du graphe sont les sommets d'écartement minimal. Ici, les trois sommets ayant l'écartement le plus petit (qui est de 2) sont : C, D et F.

Rayon :

Le rayon est l'écartement d'un centre du graphe.
Les centres de ce graphe ont pour écartement 2, donc le rayon est de 2.

Diamètre :

Le diamètre est la distance maximale entre deux sommets du graphe. Ici, les sommets les plus éloignés entre eux ont une distance de 3, donc le diamètre est de 3.

Un tableau d'adjacence est un tableau à double entrée où chaque case contient 1 si les sommets sont liés par une arête, et 0 sinon.

Exemple :

Adjacence	A	B	C	D	E
A	0	0	1	1	1
B	0	0	1	1	0
C	1	1	0	1	1
D	1	1	1	0	1
E	1	0	1	1	0

Exercice 4

Voici un graphe :

Un graphe

a. Combien y a t-il d'arêtes et de sommets dans ce graphe ?
b. Complétez le tableau d'adjacence de ce graphe :

Adjacence	Anna	Charles	Elliot	Louise	Mathilde	Marc	Tatiana
Anna
Charles
Elliot
Louise
Mathilde
Marc
Tatiana

c. Déterminer le diamètre et le(s) centre(s) du graphe.

Réponse exercice 4

a. Il y a 8 arêtes et 7 sommets dans ce graphe.

b. Voici le tableau d'adjacence obtenu :

Adjacence	Anna	Charles	Elliot	Louise	Mathilde	Marc	Tatiana
Anna	0	1	0	0	0	0	0
Charles	1	0	0	0	1	0	0
Elliot	0	0	0	1	1	1	1
Louise	0	0	1	0	0	0	0
Mathilde	0	1	1	0	0	0	1
Marc	0	0	1	0	0	0	1
Tatiana	0	0	1	0	1	1	0

c. La distance maximale entre 2 sommets est de 4 arêtes : Donc le diamètre est de 4.

Vidéo - Comment sommes nous connectés ?¶

À faire

Pour répondre aux questions suivantes, rendez-vous sur l'application Éléa.
Dans la partie "Les réseaux sociaux", ouvrez le test nommé "Vidéo - Comment sommes nous connectés". Ce questionnaire sera évalué sur 10 points.

Visionnez les 12 premières minutes de la vidéo suivante :

Exercice 5 - Questions sur la vidéo

Décrire le premier modèle théorique introduit par Paul Erdös pour simuler un réseau social.
Quelle est la première propriété mise en évidence par ce modèle ?
En vous aidant de la page wikipedia, décrire l'expérience de Stanley Milgram du « petit monde ».
Quelle(s) critique(s) majeure(s) peux-on émettre sur l'étude menée ?
Quel est le réseau social étudié par Duncan Watts ? Quelle est la longueur moyenne du chemin entre deux acteurs ?
Quel effet a l’utilisation des plateformes de réseaux sociaux sur les degrés de séparation ?
Quelle seconde propriété des réseaux sociaux a été identifiée par Duncan Watts ?
Albert Lazlo Barabasi constate que les réseaux sociaux font aussi apparaitre des Hubs (également appelés clusters) faisant le lien entre différentes sous-communautés :
1. Donner d'autres exemples de réseaux qui exhibent cette propriété.
2. Quelle est la justification proposée par Barabasi d'une telle organisation ?
Donner les caractéristiques identifiés par l'auteur pour le réseau social formé des amateurs de sciences sur Twitter (la valeur du degré de séparation, quelques sous-communautés et des hubs).
D'après vous, quels peuvent être les conséquences de ces regroupements sur les réseaux sociaux ?

Aller plus loin avec Python¶

(Cette partie ne compte pas dans les exercices notés.)

À télécharger

Télécharger le fichier suivant : graphe.py

À faire 1

Ouvrir l'application Thonny
Cliquer sur l'onglet Fichier puis Ouvrir.
Choisissez votre fichier graphe.py préalablement téléchargé.
Vous devez installer le module Python nommé networkx et le module nommé matplotlib. Pour cela, cliquez sur l'onglet Outils, puis Gérer les paquets, puis recherchez et installez les deux modules.
Exécutez le script avec le bouton d'exécution (le bouton vert avec une flèche), ou en appuyant sur le bouton F5 du clavier. Observez ce qu'il se passe.

N'hésitez pas à jeter un oeil à cette présentation de Thonny pour en savoir plus sur son fonctionnement.

À faire 2

Tentez de modifier le code pour afficher le graphe suivant :

Un graphe

Vérifiez si le(s) centre(s) du graphe et son diamètre affichés par le programme (dans la console en bas à gauche) correspondent bien à ceux obtenus à l'exercice 4.

À faire 3

Modifiez le programme de manière à obtenir le graphe suivant :

Un graphe

Quels sont le(s) centre(s) du graphe et son diamètre affichés par le programme ?