Modéliser les réseaux sociaux⚓︎

Consignes

À partir de la page Doctools, se connecter à l'aide des codes perso distribués.
Utiliser le code 9ZCz pour accéder au document à compléter en ligne.
Vous pouvez travailler en bînome, renseigner votre partenaire dans l'espace réservé.
Les groupes de 3 ou plus sont interdits.
Le travail est sauvegardé au fur et à mesure. Vous pouvez poursuivre en cas de coupure.
Vous pouvez travailler sur un document hors-ligne, et renseigner les réponses une fois terminé.

Un graphe

Pour représenter un réseau social on utilise un graphe défini par :

sommets : modélisent les entités sociales (utilisateurs)
arêtes : modélisent les relations non orientées entre les entités
arcs : modélisent une relation orientée d'une personne ou entité vers une autre.

Exemple de graphe non orienté

Sur le réseau Facebook, pour être en relation, deux personnes inscrites doivent sʼaccepter mutuellement comme amis. Une arête entre 2 sommets représente la relation « sont amis ».

graph LR;
    Jade --- Julien;
    Tony --- Julien;
    Tony --- Nina;
    Nina --- Julien;
    Fred --- Tony;
    Fred --- Jade;

Exemple de graphe orienté

Sur Twitter, il est possible de suivre une personne inscrite sans que cela soit réciproque. Un arc entre 2 sommets représente la relation « est un abonnés de ».

mermaid graph LR; Jade --> Julien; Julien --> Jade; Julien --> Tony; Nina --> Tony; Nina --> Julien; Julien --> Nina; Fred --> Tony; Jade --> Fred;

Exercice 1

On considère le réseau social suivant : - Cléo est amie avec Mathias, Stella, Carla et Léopold - Mathias est ami avec Cléo, Maxime, Carla, Léopold et Léane - Léane est amie avec Mathias, Charles et Léopold - Léopold est ami avec Maxime, Cléo, Mathias et Léane - Carla est amie avec Cléo et Mathias - Stella est amie avec Cléo - Maxime est ami avec Léopold et Mathias - Charles est ami avec Léane

Le page graphonline contient la liste des noeuds de se graphe social.

Utilisez l'onglet Lier les sommets pour complétez le graphe avec des arrêtes non orientées pour représenter les liens d'amitiés.
Arrangez les sommets du graphe afin qu'aucune arrête n'en coupe une autre (on dit que le graphe est planaire, ce n'est pas le cas de tous les graphes).
Utilisez l'onglet Algorithmes, calculez le degré des sommets. Que représente ce nombre ?
Quel est le plus court chemin qui relie Stella à Léane ? Préciser sa longueur.
En partant du sommet Mathias trouvez les plus cours chemin pour rejoindre les autres sommets.
Donner deux sommets du graphe qui sont le plus éloignés l'un de l'autre. C'est le diamètre du graphe.

Vocabulaire dans un graphe non orienté

chaîne : suite de sommets reliés par des arêtes**
distance entre deux sommet est égale à la longueur de la plus petite chaîne qui les relie.
écartement/éxcentricité d'un sommet est la distance maximale entre ce sommet et les autres nœuds du graphe
diamètre du graphe est la distance maximale entre deux sommet de ce graphe.
le centre est l'ensemble des sommets d'écartement minimal.
tableau d'adjacence est un tableau à double entrée ou chaque case contient 1 si les sommets sont liés par une arête, 0 sinon.

Exemple

Soit le graphe et son tableau d'adjacence et celui des distances entre sommets :

graph LR;
    A---C;
    A---D;
    C---E;
    C---D;
    B---D; 
    C---B; 
    E---D;
    A---E;

le sommet A est adjacent à C, D et E.
la distance du sommet A au sommet B est de 2
la distance du sommet C au sommet B est de 1. B et C sont adjacents.
la distance du sommet C aux sommets A, B, D et E est de 1 (voir le tableau de distance). Le sommet a un écartement de 1.
l'écartement du sommet D est de 1 (voir le tableau de distance).
l'ensemble \(\{ C; D\}\) est le centre du graphe.

Tableau d'adjacenceTableau de distance

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

Distance	A	B	C	D	E
A	0	2	1	1	1
B	2	0	1	1	2
C	1	1	0	1	1
D	1	1	1	0	1
E	1	2	1	1	0

Exercice 2

Compléter les tableaux d'adjacence et de distance du graphe ci-contre.
Déterminer l'écartement de chaque sommet.
Déterminer le diamètre et le(s) centre(s) des graphes.

graph TD;
    Marc---Tatiana;
    Marc---Elliot;
    Louise---Elliot;
    Tatiana---Mathilde; 
    Elliot---Mathilde; 
    Tatiana---Elliot; 
    Anna---Charles;
    Mathilde---Charles;

Tableau d'adjacenceTableau de distance

Adjacence	A	C	E	L	M	Mc	T
Anna
Charles
Elliot
Louise
Mathilde
Marc
Tatiana

Distance	A	C	E	L	M	Mc	T
Anna
Charles
Elliot
Louise
Mathilde
Marc
Tatiana

Exercice 2 bis

Compléter les tableaux d'adjacence et de distance du graphe ci-contre.
Déterminer l'écartement de chaque sommet.
Déterminer le diamètre et le(s) centre(s) des graphes.

graph TD;
    Quark---Jadzia;
    Quark---Tasha;
    Jadzia---Curzon;
    Jadzia---Ezra; 
    Tasha---Ezra; 
    Tasha---Naomi; 
    Naomi---Garak;
    Curzon---Garak;

Tableau d'adjacenceTableau de distance

Adjacence	C	E	G	J	N	Q	T
Curzon
Ezra
Garak
Jadzia
Naomi
Quark
Tasha

Distance	C	E	G	J	N	Q	T
Curzon
Ezra
Garak
Jadzia
Naomi
Quark
Tasha

Les propriétés principales observées des réseaux sociaux⚓︎

Enquête vidéo de Mehdi Moussaïd sur la structure des graphes sociaux

Visionnez les 12 premières minutes de la vidéo ci-dessous

Exercice 3 : compréhension

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 ikipedia, décrire l'expérience de Stanley Milgram du « petit monde » (pas celle sur l'autorité !).
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 faisant le lien entre différentes sous-communautés.
- Donner d'autres de réseaux qui exhibent cette propriété.
- Quelle est la justification proposée par Barabasi d'une telle organisation ?
Donner les caractéristiques identifiés par l'auteur pour le réseaux social sur twitter formé des amateurs de sciences sur twitter (la valeur du degré de séparation, quelques sous-communautés et des hubs).

Références⚓︎

La vidéo de Véritasium (en anglais) présente une discussion plus approfondie sur le phénomène du petit monde et sur l'importance des rencontres aléatoires, et aborde les critiques de l'expérience de Milgram. ↩