- Comprendre la notion de graphe (sommets, arêtes)
- Calculer la distance, le diamètre, l'écartement et le centre d'un graphe
- Construire et lire une matrice d'adjacence
- Connaître la théorie des 6 degrés de séparation
Représenter un réseau social sous forme de graphe mathématique et en analyser les propriétés fondamentales.
— Qu'est-ce qu'un réseau social ?
— Comment représenter simplement les liens entre personnes ?
— Peut-on mesurer la distance entre deux utilisateurs d'un réseau ?
Partie 1 — Qu'est-ce qu'un graphe ?
Dans un réseau social, les liens entre utilisateurs sont complexes. On les représente sous la forme d'un graphe.
Un graphe est constitué de :
- Sommets (ou nœuds — vertices/nodes) → les utilisateurs
- Arêtes (edges) → les liens entre utilisateurs
Distance entre deux sommets : nombre minimum d'arêtes pour aller de l'un à l'autre. Ex : distance(a, f) = 2 (chemin a → d → f).
Diamètre : distance maximale entre deux sommets quelconques du graphe. Ici : diamètre = 2.
Écartement d'un sommet : distance maximale entre ce sommet et tous les autres. Écartement(a) = 2 | Écartement(d) = 1.
Centre : sommet d'écartement minimal. Ici : d (en vert) avec un écartement de 1.
Rayon : écartement du centre. Ici : rayon = 1.
📌 distance(A,B) = nombre minimum d'arêtes entre A et B
📌 écartement(X) = distance max entre X et tous les autres sommets
📌 diamètre = écartement maximum parmi tous les sommets
📌 centre = sommet dont l'écartement est le plus petit
📌 rayon = écartement du centre | rayon ≤ diamètre
Travail 1 — Dessiner un réseau social
Tracer le graphe du réseau social suivant (6 membres : A, B, C, D, E, F) :
- 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
- E est ami avec C, D et F
- F est ami avec E et D
Utiliser l'outil en ligne : graphonline.ru/fr/
D (vert) = centre du graphe
Partie 2 — La Matrice d'adjacence
Une matrice d'adjacence est un tableau à deux dimensions décrivant tous les liens d'un graphe.
- On place un 1 si deux sommets sont reliés par une arête
- On place un 0 si aucun lien n'existe
- La diagonale est toujours 0 (pas de lien vers soi-même)
- La matrice est symétrique pour un graphe non orienté
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
Travail 2 — Compléter une matrice d'adjacence
Remplissez chaque case avec 0 ou 1 selon le graphe ci-contre :
| A | B | C | D | |
|---|---|---|---|---|
| A | ||||
| B | ||||
| C | ||||
| D |
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
Liens : A-B ✔ | A-C ✔ | B-C ✔ | C-D ✔ | Tous les autres = 0
Partie 3 — Les 6 degrés de séparation
En 1967, le psychologue Stanley Milgram formule l'hypothèse que toute personne sur Terre est reliée à n'importe quelle autre par une chaîne d'au plus 6 intermédiaires.
Sur un graphe : chaque sommet est relié à tout autre sommet par un chemin d'au plus 6 arêtes.
Les réseaux sociaux utilisent des algorithmes de recommandation qui créent des "bulles de filtre" : l'utilisateur ne voit que les contenus correspondant à ses goûts.
Théorie développée par Eli Pariser : à partir des données collectées (historique, clics, interactions), l'algorithme sélectionne les contenus visibles — enfermant l'utilisateur dans une bulle qui renforce ses opinions.
- Liens forts : amis proches, opinions similaires → bulle fermée
- Liens faibles : connaissances lointaines → permettent de traverser le graphe rapidement
Exercices — Vérifie tes connaissances
Q1 — Dans un réseau social, les membres sont appelés :
Q2 — Les connexions entre membres d'un réseau sont appelées :
Graphe : P-Q, Q-R, R-S, S-P, Q-S (pointillés)
Q1 — Quelle est la distance entre P et R ?
Q2 — Quel est le diamètre de ce graphe ?
Q3 — Quel(s) sommet(s) est (sont) le centre de ce graphe ?
Combien d'arêtes possède le graphe décrit par cette matrice ?
| X | Y | Z | W | |
|---|---|---|---|---|
| X | 0 | 1 | 0 | 1 |
| Y | 1 | 0 | 1 | 0 |
| Z | 0 | 1 | 0 | 1 |
| W | 1 | 0 | 1 | 0 |
Entrez deux prénoms et visualisez une chaîne fictive de 6 degrés :
Q — Selon Facebook en 2016, le nombre moyen de degrés de séparation est :
Ma synthèse
| Notion | Définition |
|---|---|
| Graphe | Ensemble de sommets reliés par des arêtes |
| Sommet | Nœud du graphe (utilisateur d'un réseau) |
| Arête | Lien entre deux sommets |
| Distance | Nb minimum d'arêtes entre deux sommets |
| Diamètre | Distance maximale du graphe |
| Centre | Sommet d'écartement minimal |
| Matrice d'adjacence | Tableau 0/1 décrivant tous les liens |
| 6 degrés de séparation | Toute personne est reliée à toute autre en ≤ 6 intermédiaires |