Sciences numériques et technologie (SNT) 2ⁿᵈᵉ
Ressources · 2ⁿᵈᵉ · Sciences numériques et technologie (SNT)
Graphes et influence
Modéliser un réseau social : sommets, arêtes, degré, distance, diamètre, centre, rayon, petit monde (SNT de 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 : L'essentiel, Modéliser un réseau social par un graphe, Distance, excentricité, diamètre, rayon, centre, Petit monde et expérience de Milgram. 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).
1
L'essentiel
Graphe. Un graphe est formé de sommets (ici, les utilisateurs d'un réseau social) reliés par des arêtes (les relations entre eux). Deux sommets reliés par une arête sont dits voisins.
Degré. Le degré d'un sommet est le nombre de ses voisins, c'est-à-dire le nombre d'arêtes qui partent de lui. Dans un réseau d'amis, c'est le nombre d'amis.
Chaîne et distance. Une chaîne est une suite de sommets dont deux consécutifs sont voisins ; sa longueur est son nombre d'arêtes. La distance d(X, Y) est la longueur d'une plus courte chaîne reliant X à Y. Par convention, d(X, X) = 0.
Graphe connexe. Un graphe est connexe si deux sommets quelconques sont toujours reliés par au moins une chaîne. Dans un graphe non connexe, certaines distances ne sont pas définies.
Propriété. Dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes, car chaque arête est comptée une fois pour chacune de ses deux extrémités. En particulier, cette somme est toujours paire.
Exemple (réseau R0, repris dans tout le cours). Amitiés : Ana–Bilal, Ana–Chloé, Bilal–Chloé, Chloé–Driss, Driss–Emma, Driss–Farid. Six sommets, six arêtes. Degrés : Ana 2, Bilal 2, Chloé 3, Driss 3, Emma 1, Farid 1. Somme : 2 + 2 + 3 + 3 + 1 + 1 = 12 = 2 × 6.
2
Modéliser un réseau social par un graphe
| Relation | Type de graphe | Lecture |
|---|---|---|
| Amitié réciproque (A ami de B ⇔ B ami de A) | non orienté : arêtes sans flèche | degré = nombre d'amis |
| Abonnement (A suit B sans que B suive forcément A) | orienté : chaque lien est une flèche A → B | flèches entrantes = abonnés ; flèches sortantes = abonnements |
Liste d'adjacence. On décrit un graphe en écrivant, pour chaque sommet, la liste de ses voisins. Pour un graphe non orienté, si B est dans la liste de A, alors A est dans la liste de B.
En Python. Un dictionnaire associe à chaque sommet (la clé) la liste de ses voisins. Le degré s'obtient avec
len.reseau = {'Ana': ['Bilal', 'Chloé'], 'Bilal': ['Ana', 'Chloé'],
'Chloé': ['Ana', 'Bilal', 'Driss'], 'Driss': ['Chloé', 'Emma', 'Farid'],
'Emma': ['Driss'], 'Farid': ['Driss']}
len(reseau['Chloé']) # vaut 3 : degré de ChloéAstuce. Le dessin d'un graphe n'a aucune importance : seules comptent les relations. Deux dessins différents du même réseau donnent les mêmes degrés et les mêmes distances.
3
Distance, excentricité, diamètre, rayon, centre
Excentricité. Dans un graphe connexe, l'excentricité e(X) d'un sommet X est la plus grande distance entre X et les autres sommets. C'est le nombre d'étapes nécessaires pour que X touche tout le réseau.
Diamètre. Le diamètre D est la plus grande excentricité, c'est-à-dire la plus grande distance entre deux sommets du graphe.
Rayon et centre. Le rayon r est la plus petite excentricité. Le centre est l'ensemble des sommets dont l'excentricité est égale au rayon (il peut y en avoir plusieurs).
Exemple (R0). Excentricités : Ana 3, Bilal 3, Chloé 2, Driss 2, Emma 3, Farid 3. Donc D = 3, r = 2 et le centre est {Chloé, Driss}. Une nouvelle partie de Chloé atteint tout le monde en 2 étapes au plus.
Repère. On a toujours r ≤ D. Un graphe « serré » a un petit diamètre ; un réseau allongé (en chaîne) a un grand diamètre.
4
Petit monde et expérience de Milgram
Petit monde. Un réseau est dit « petit monde » lorsque, malgré un très grand nombre de sommets, la distance entre deux sommets reste petite (quelques unités). Cela s'explique par quelques liens « longs » entre groupes éloignés et par des sommets très connectés.
L'expérience de Milgram (1967). Le psychologue américain Stanley Milgram a confié des lettres à des habitants du Nebraska et du Kansas. Chacun devait faire parvenir sa lettre à un destinataire inconnu de la région de Boston, en ne la transmettant qu'à une connaissance personnelle jugée plus proche de la cible. Seule une minorité des lettres est arrivée (64 chaînes sur 296 départs dans l'article publié en 1969) ; pour celles-ci, la chaîne comptait en moyenne un peu plus de cinq intermédiaires (5,2). Ce résultat a popularisé l'idée des « six degrés de séparation », une expression que Milgram n'employait pas lui-même.
Aujourd'hui. Sur les grands réseaux sociaux en ligne, qui comptent des centaines de millions, voire des milliards de comptes, les études mesurent des distances moyennes encore plus faibles, de l'ordre de 4 à 5. Sur Facebook, la distance moyenne était de 4,74 en 2011 (721 millions de comptes actifs) et de 4,57 en 2016 (1,59 milliard), soit 3,57 intermédiaires : les « 3,57 degrés de séparation ».
Attention. « Six degrés » est un ordre de grandeur issu d'une expérience imparfaite, pas une loi : ce n'est ni une distance exacte, ni le diamètre du réseau mondial.
5
Influence et circulation de l'information
Sommets influents. Un sommet de grand degré (un « hub ») diffuse une information vers beaucoup de voisins en une seule étape. Dans un réseau d'abonnements, le nombre d'abonnés (flèches entrantes) mesure l'audience d'un compte.
Position dans le réseau. L'influence dépend aussi de la position : un sommet du centre atteint tout le monde en peu d'étapes, et un sommet « pont » entre deux groupes contrôle le passage de l'information de l'un à l'autre.
Dans la plupart des réseaux sociaux, la répartition des degrés est très inégale : beaucoup de comptes ont peu de relations et quelques comptes en ont énormément.
Information conditionnée par ses amis. Un utilisateur ne voit que ce que publient ou partagent les comptes auxquels il est relié (amis, abonnements), puis ce que l'algorithme du réseau choisit de lui montrer en fonction de ses goûts supposés. Si ses relations pensent toutes de la même façon et que l'algorithme lui propose surtout des contenus proches de ceux qu'il apprécie déjà, il risque de s'enfermer dans une bulle de filtre (expression popularisée par Eli Pariser en 2011) : les informations venues d'autres groupes ne lui parviennent pas.
Communautés : bonding et bridging. Dans le graphe d'un réseau social, on repère des communautés grâce à la densité des liens : des groupes de sommets très reliés entre eux et peu reliés au reste. Renforcer les liens existants au sein d'un même groupe s'appelle le bonding ; construire de nouveaux liens, non redondants, vers d'autres groupes s'appelle le bridging. Des recommandations d'amis et de contenus qui se renforcent les unes les autres favorisent le bonding et peuvent enfermer une communauté sur elle-même, jusqu'à appauvrir l'esprit critique ; les liens « ponts » du bridging relient les communautés et diversifient l'information reçue.
6
Méthodes
Méthode 1 — Calculer les distances depuis un sommet (par niveaux)
- Placer le sommet de départ au niveau 0.
- Placer tous ses voisins au niveau 1.
- Placer au niveau 2 les voisins des sommets du niveau 1 qui n'ont pas encore été placés, et ainsi de suite.
- La distance d'un sommet au départ est le numéro du niveau où il apparaît la première fois ; le dernier niveau donne l'excentricité.
Exemple rédigé. Dans R0, depuis Ana : niveau 0 : Ana ; niveau 1 : Bilal, Chloé ; niveau 2 : Driss (voisin de Chloé) ; niveau 3 : Emma, Farid (voisins de Driss). Donc d(Ana, Driss) = 2, d(Ana, Emma) = 3, et e(Ana) = 3.
Méthode 2 — Déterminer diamètre, rayon et centre
- Vérifier que le graphe est connexe.
- Appliquer la méthode 1 à chaque sommet et noter son excentricité dans un tableau.
- Diamètre = plus grande valeur ; rayon = plus petite valeur.
- Centre = sommets dont l'excentricité vaut le rayon.
Exemple rédigé. Pour R0 :
D = 3, r = 2, centre = {Chloé, Driss}.
| Sommet | Ana | Bilal | Chloé | Driss | Emma | Farid |
|---|---|---|---|---|---|---|
| e | 3 | 3 | 2 | 2 | 3 | 3 |
Méthode 3 — Passer d'une description à une liste d'adjacence (et à Python)
- Lister tous les sommets.
- Pour chaque relation réciproque A–B, écrire B dans la liste de A et A dans la liste de B (pour un abonnement A → B, seulement B dans la liste de A).
- Contrôler : la somme des longueurs des listes doit valoir le double du nombre d'arêtes.
Exemple rédigé. « Wassim est ami avec Yanis et avec Zélie ; Yanis est ami avec Zélie. » On obtient
{'Wassim': ['Yanis', 'Zélie'], 'Yanis': ['Wassim', 'Zélie'], 'Zélie': ['Wassim', 'Yanis']}. Contrôle : 2 + 2 + 2 = 6 = 2 × 3 arêtes.7
Pièges et erreurs classiques
Distance ≠ longueur d'une chaîne quelconque. Trouver une chaîne de longueur 4 entre X et Y prouve seulement que d(X, Y) ≤ 4. Pour affirmer d(X, Y) = 4, il faut montrer qu'aucune chaîne plus courte n'existe (méthode des niveaux).
Compter les arêtes, pas les sommets. La chaîne A–B–C a pour longueur 2, pas 3.
Plus grand degré ≠ centre. Un sommet très connecté mais situé en bord de réseau peut avoir une grande excentricité. Le centre se détermine avec les excentricités, pas avec les degrés.
Graphe non connexe. Si deux groupes ne sont reliés par aucune chaîne, leur distance n'est pas définie, et le diamètre non plus.
Graphe orienté. « A suit B » ne signifie pas « B suit A ». Dans une liste d'adjacence non orientée, en revanche, oublier d'écrire la relation dans les deux listes est une erreur.
En bref
- Réseau social = graphe : utilisateurs = sommets, relations = arêtes (flèches pour un abonnement).
- Degré = nombre de voisins ; somme des degrés = 2 × nombre d'arêtes.
- Distance = longueur d'une plus courte chaîne ; excentricité = plus grande distance depuis un sommet.
- Diamètre = plus grande excentricité ; rayon = plus petite ; centre = sommets d'excentricité égale au rayon.
- Petit monde : distances très faibles dans d'immenses réseaux (Milgram, 1967 : un peu plus de cinq intermédiaires).
- L'information que l'on reçoit dépend de ses relations : risque de bulle de filtre.
Bloqué sur ce chapitre ?
Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.
Soutien scolaire à Marseille · Cours particuliers au lycée · Aide aux devoirs