À propos de cette page
Ce cours de sciences numériques et technologie (snt) en seconde sur « Graphes et influence » suit le programme officiel de sciences numériques et technologie (snt) de seconde. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Qu'est-ce qu'un graphe ?, Vocabulaire des graphes, Degré d'un sommet et influence, Chemins et distances. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de seconde à réussir en sciences numériques et technologie (snt).
Au programme
1 · Qu'est-ce qu'un graphe ?
2 · Vocabulaire des graphes
3 · Degré d'un sommet et influence
4 · Chemins et distances
5 · Matrice d'adjacence
6 · Modéliser un réseau social
7 · Propagation de l'information
8 · La notion de petit monde
1Qu'est-ce qu'un graphe ?
Un graphe est une structure mathématique permettant de modéliser des relations entre des objets. On l'utilise massivement en informatique pour représenter des réseaux : réseaux sociaux, réseaux informatiques, cartes routières, etc.
Définition. Un
graphe $G = (S, A)$ est composé :
- d'un ensemble de sommets (ou nœuds) $S$ — par exemple des personnes, des pages web, des villes ;
- d'un ensemble d'arêtes $A$ — chaque arête relie deux sommets et représente une relation entre eux.
On note $|S|$ le nombre de sommets et $|A|$ le nombre d'arêtes.
Exemple. Dans un réseau social, chaque utilisateur est un sommet. Un lien d'amitié entre deux utilisateurs est une arête. Si Alice, Bob et Carla sont amis deux à deux, le graphe a 3 sommets et 3 arêtes.
Un graphe peut être non orienté (la relation est symétrique : « A est ami avec B » implique « B est ami avec A ») ou orienté (la relation a un sens : « A suit B » n'implique pas « B suit A »).
Différentes familles de graphes utilisés pour modéliser les réseaux.
2Vocabulaire des graphes
Maîtriser le vocabulaire des graphes est essentiel pour analyser un réseau social.
| Terme | Définition |
|---|
| Sommet | Un nœud du graphe (utilisateur, page, ville…) |
| Arête | Un lien entre deux sommets |
| Degré | Nombre d'arêtes incidentes à un sommet |
| Voisin | Sommet directement relié par une arête |
| Chemin | Suite de sommets reliés par des arêtes |
| Distance | Longueur du plus court chemin entre deux sommets |
| Graphe connexe | Tout sommet est accessible depuis tout autre sommet |
| Diamètre | La plus grande distance entre deux sommets du graphe |
Astuce. On représente souvent un graphe par un dessin (les sommets = cercles, les arêtes = traits) ou par une matrice d'adjacence (tableau de 0 et de 1).
Attention ! Le degré d'un sommet n'est pas la même chose que la distance. Le degré mesure combien de voisins directs a ce sommet ; la distance mesure combien d'étapes il faut pour atteindre un autre sommet.
3Degré d'un sommet et influence
Le degré d'un sommet est l'un des indicateurs les plus simples de l'influence dans un réseau social.
Définition. Le degré $d(v)$ d'un sommet $v$ est le nombre de ses voisins (arêtes qui lui sont incidentes). Dans un graphe à $n$ sommets, $d(v) \in \{0, 1, \ldots, n-1\}$.
Plus le degré d'un utilisateur est élevé, plus il a de connexions directes, et donc plus il peut diffuser rapidement une information à un grand nombre de personnes.
Exemple. Considère un graphe à 5 sommets A, B, C, D, E avec les arêtes : A-B, A-C, A-D, A-E, B-C.
— $d(A) = 4$ (A est relié à B, C, D, E) : A est très influent.
— $d(B) = 2$ (B est relié à A, C).
— $d(C) = 2$, $d(D) = 1$, $d(E) = 1$.
La somme des degrés d'un graphe vaut toujours le double du nombre d'arêtes : $\sum_{v \in S} d(v) = 2 \times |A|$. C'est le lemme des poignées de mains.
Le sommet A a le degré le plus élevé : c'est le plus influent du réseau.
Astuce. Dans un réseau orienté (comme Twitter/X), on distingue le degré entrant (nombre d'abonnés) et le degré sortant (nombre d'abonnements). L'influence se mesure souvent par le degré entrant.
4Chemins et distances
Pour savoir à quelle vitesse une information peut se propager entre deux utilisateurs, on s'intéresse aux chemins dans le graphe.
Définition. Un chemin de longueur $k$ entre deux sommets $u$ et $v$ est une suite $u = s_0, s_1, \ldots, s_k = v$ où chaque paire $(s_i, s_{i+1})$ est une arête du graphe. La distance $d(u,v)$ est la longueur du plus court chemin entre $u$ et $v$.
Exemple. Dans un graphe avec les arêtes A-B, B-C, C-D, A-C :
— La distance $d(A,D) = 2$ (chemin A-C-D).
— Il existe aussi le chemin A-B-C-D de longueur 3, mais ce n'est pas le plus court.
Définition. Le diamètre d'un graphe est la valeur maximale des distances entre toutes les paires de sommets : $\text{diam}(G) = \max_{u,v \in S} d(u,v)$.
Un diamètre faible signifie que l'information peut circuler rapidement dans tout le réseau.
Attention ! Si le graphe n'est pas connexe (certains sommets sont isolés ou dans des composantes séparées), la distance entre deux sommets de composantes différentes n'est pas définie (ou considérée comme infinie).
Astuce. Pour trouver le plus court chemin dans un graphe, on peut utiliser l'algorithme du parcours en largeur (BFS — Breadth First Search), qui explore les voisins couche par couche.
5Matrice d'adjacence
La matrice d'adjacence est une façon de représenter un graphe sous forme de tableau numérique, pratique pour le traitement informatique.
Définition. Pour un graphe à $n$ sommets numérotés de $1$ à $n$, la matrice d'adjacence est une matrice $M$ de taille $n \times n$ telle que :
$M[i][j] = 1$ si une arête relie le sommet $i$ au sommet $j$, et $M[i][j] = 0$ sinon.
Exemple. Graphe non orienté à 4 sommets (1, 2, 3, 4) avec arêtes 1-2, 1-3, 2-4 :
Le degré du sommet $i$ est la somme de la ligne $i$ (ou colonne $i$) de la matrice.
Astuce. Pour un graphe non orienté, la matrice d'adjacence est toujours symétrique : $M[i][j] = M[j][i]$. La diagonale est nulle (pas d'arête d'un sommet vers lui-même).
6Modéliser un réseau social
Les réseaux sociaux comme Facebook, Instagram ou Twitter/X peuvent tous être modélisés par des graphes. Chaque plateforme correspond à un type de graphe particulier.
| Réseau social | Type de graphe | Explication |
|---|
| Facebook (amitié) | Non orienté | L'amitié est réciproque |
| Twitter/X (abonnement) | Orienté | On peut suivre quelqu'un sans être suivi en retour |
| LinkedIn (connexion) | Non orienté | La mise en relation est mutuelle |
| YouTube (abonnement) | Orienté | Un abonné ne l'est pas nécessairement en retour |
Exemple. Un graphe simplifié d'un réseau d'amitié avec 6 personnes : Alice, Bob, Carla, David, Eva, Fatima. Les amitiés : Alice-Bob, Alice-Carla, Bob-David, Bob-Eva, Carla-Fatima, Eva-Fatima.
— $d(\text{Alice}) = 2$, $d(\text{Bob}) = 3$, $d(\text{Eva}) = 2$. Bob est le plus influent.
Pipeline de modélisation : des utilisateurs aux influenceurs détectés.
Attention ! La modélisation simplifie la réalité. Par exemple, les liens d'amitié sur Facebook ne reflètent pas forcément des liens d'amitié réels ou la force de la relation.
7Propagation de l'information
L'un des phénomènes les plus importants dans les réseaux sociaux est la propagation de l'information : comment une publication, une rumeur ou une fausse information se diffuse-t-elle ?
On peut modéliser cette propagation par des vagues successives dans le graphe. À chaque étape, tous les voisins d'un sommet « contaminé » deviennent à leur tour contaminés.
Exemple. Dans un graphe, Alice publie une information (étape 0). À l'étape 1, ses amis directs la voient. À l'étape 2, les amis de ses amis la voient. Et ainsi de suite. Le nombre de personnes atteintes peut croître très vite si le graphe est dense.
Définition. L'éccentricité d'un sommet $v$ est la distance maximale entre $v$ et tout autre sommet du graphe : $e(v) = \max_{u \in S} d(u,v)$. Un sommet de faible excentricité peut diffuser une information à tous en peu d'étapes.
Les algorithmes de recommandation des réseaux sociaux exploitent ces propriétés pour maximiser la propagation des contenus.
Astuce. La propagation rapide est liée à la présence de nœuds hubs (sommets de très grand degré). Supprimer ces hubs fragmente le réseau et ralentit la propagation.
8La notion de petit monde
En 1967, le psychologue Stanley Milgram a réalisé une expérience célèbre : il a montré que deux personnes quelconques aux États-Unis sont reliées par une chaîne de 6 intermédiaires au maximum. C'est la théorie des six degrés de séparation.
Définition. Un graphe est dit petit monde (small world) si son diamètre est petit par rapport à son nombre de sommets. Dans un tel graphe, tout sommet peut être atteint depuis tout autre en un petit nombre d'étapes.
Les grands réseaux sociaux numériques vérifient cette propriété : Facebook a annoncé en 2016 que le degré de séparation moyen entre deux utilisateurs était de 3,57 (au lieu de 6 pour le monde réel).
Plus Facebook grandit, plus le degré de séparation diminue : le réseau se resserre.
Exemple. Sur un réseau social à 1 milliard d'utilisateurs avec un degré de séparation de 4, une information peut potentiellement atteindre tout le monde en 4 étapes seulement !
Attention ! Un diamètre faible ne signifie pas qu'une information atteint effectivement tout le monde : des bulles de filtre, des paramètres de confidentialité ou des algorithmes peuvent limiter la propagation réelle.
★À retenir
En bref :
• Un graphe est un ensemble de sommets reliés par des arêtes ; il modélise les réseaux sociaux.
• Le degré d'un sommet = nombre de ses voisins directs → indicateur d'influence.
• La distance $d(u,v)$ = longueur du plus court chemin entre $u$ et $v$.
• Le diamètre = la plus grande distance entre deux sommets du graphe.
• La matrice d'adjacence représente un graphe sous forme de tableau (0/1).
• Un graphe petit monde a un diamètre faible → l'information se propage vite.
• La propagation se fait par vagues successives à partir d'un sommet source.