Qu'est-ce qu'un graphe en SNT ?

Un graphe est un ensemble de sommets reliés par des arêtes, utilisé pour modéliser des réseaux (sociaux, informatiques, routiers).

Comment mesure-t-on l'influence dans un réseau social ?

On utilise le degré d'un sommet (nombre de connexions), la centralité et la distance entre les sommets du graphe.

Qu'est-ce que le diamètre d'un graphe ?

Le diamètre est la longueur du plus long des plus courts chemins entre deux sommets du graphe.

Lycée · 2ⁿᵈᵉ · Sciences numériques et technologie (SNT)

Graphes et influence

Modéliser les réseaux sociaux par des graphes : sommets, arêtes, degré et propagation de l'information (programme SNT 2nde)

À 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).

Qu'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.

Vocabulaire 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.

Degré 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.

Chemins 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.

Matrice 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 :

	1	2	3	4
1	0	1	1	0
2	1	0	0	1
3	1	0	0	0
4	0	1	0	0

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).

Modé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.

Propagation 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.

La 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.

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.

Bloqué sur ce chapitre ?

Cours particuliers de sciences numériques et technologie (snt) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.

Réserver un 1^er cours → Voir les tarifs

Soutien scolaire à Marseille · Cours particuliers au lycée · Aide aux devoirs