Aller au contenu

Séance 5 — Diffusion d'une information (BFS) et composantes connexes

Fiche enseignant

Objectifs pédagogiques

  • Introduire intuitivement le concept de parcours en largeur (BFS) à travers la métaphore de la diffusion d'une information dans un réseau social.
  • Faire le lien entre la distance dans le graphe et la distance sociale entre individus.
  • Montrer que le point de départ d'une diffusion change radicalement son déroulement.
  • Introduire la notion de composantes connexes à travers un acteur isolé.
  • Comparer BFS et DFS sans mathématiques : deux logiques d'exploration du réseau.

Prérequis

  • Avoir compris les notions de graphe, sommets, arêtes (Séance 1).
  • Avoir manipulé BFS et DFS une première fois (Séance 4).
  • Avoir manipulé un graphe simple avec networkx (ajout de sommets, arêtes, visualisation).

Durée estimée

2h, séance unique (fusion des anciennes séances 6 et 6bis — leur contenu se recoupait largement).

Matériel / outils

  • Notebook Seance_5_Composantes_Diffusion.ipynb
  • Python avec networkx et matplotlib

Déroulé pédagogique

1. Introduction sociologique

But : ancrer le BFS dans une situation concrète.

Expliquer :

Une information (rumeur, message, idée) se propage dans un réseau social. Certain·es la reçoivent directement, d'autres plus tard. Le BFS modélise cette propagation par cercles de proximité.

Point clé à dire : « En BFS, on explore niveau par niveau — comme une onde sociale. »

2. Exemple manuel : propagation pas à pas

Simulation à la main sur le petit graphe (Alice — Bob/Emma — Chloé/Félix — David/Gaël) : faire remplir le tableau des niveaux avant de passer à Python.

3-4. Construction du réseau et parcours BFS depuis Alice

Résultat attendu (ordre BFS) : 

[('Alice', 'Bob'), ('Alice', 'Emma'), ('Bob', 'Chloé'), ('Bob', 'Félix'), ('Chloé', 'David'), ('Chloé', 'Gaël')]
Distances depuis Alice : Alice 0, Bob/Emma 1, Chloé/Félix 2, David/Gaël 3.

À dire : la distance = nombre d'étapes pour atteindre une personne ; plus elle est grande, plus la personne est éloignée du centre du réseau. Lien sociologique : proximité sociale, vitesse d'accès à l'information.

5. Comparaison BFS / DFS (à l'oral)

Stratégie Métaphore Manière d'explorer Exemple
BFS (largeur) diffusion sociale explore les cercles autour de la source bouche-à-oreille, message collectif
DFS (profondeur) exploration ciblée suit un chemin jusqu'au bout avant de revenir enquête, filiation, exploration hiérarchique

6. Recommencer depuis Chloé

Résultat attendu (exemple) : 

[('Chloé', 'Bob'), ('Chloé', 'David'), ('Chloé', 'Gaël'), ('Bob', 'Alice'), ('Bob', 'Félix'), ('Alice', 'Emma')]
Analyse : Chloé devient un nouveau centre de diffusion, la profondeur du graphe diminue (elle est plus "au milieu"). Chloé relie deux sous-groupes : c'est une personne-pont — à relier au coefficient de clustering vu en Séance 3 (un pont a un coefficient de clustering faible : ses ami·es ne se connaissent pas entre eux).

Point clé à dire : le point de départ de la diffusion influence sa vitesse et sa portée — une info ne se propage pas pareil selon qui la lance en premier.

7. Composantes connexes : Hugo l'isolé

Après G.add_node('Hugo') : 

Composante 1 : {'Alice', 'Bob', 'Chloé', 'Emma', 'Félix', 'David', 'Gaël'}
Composante 2 : {'Hugo'}
À dire : le graphe n'est plus connexe : deux composantes distinctes. Hugo ne reçoit aucune information.

Lien sociologique : un acteur isolé symbolise une exclusion sociale : il n'est intégré à aucun cercle relationnel.

8. Discussion finale

Questions à lancer : - Que se passe-t-il si un individu n'est relié à personne ? - Si plusieurs personnes lancent l'info en même temps ? - Qui apprend la nouvelle le plus vite ? Pourquoi ?

Lien avec la sociologie des réseaux : notions de centralité, vitesse de diffusion, position périphérique, effet d'isolation.

Interprétations sociologiques clés à souligner

Concept Python Traduction sociologique
Distance Proximité ou éloignement social
Composante connexe Groupe / sous-communauté
Sommet central Individu influent, pivot relationnel
Sommet isolé Exclusion, absence de lien social
BFS Diffusion collective, propagation rapide

Notes pédagogiques

  • Insister sur le lien entre structure et diffusion : le BFS donne une première intuition du "pouvoir de connexion" dans un réseau social.
  • Éviter tout formalisme algorithmique (pas de file, pas de pseudo-code) — le DFS/BFS formels ont déjà été codés en Séance 4, ici on reste sur l'interprétation sociologique.
  • Valoriser les représentations graphiques et le vocabulaire sociologique (proximité, cercles, diffusion, influence).

Transition possible : Cette séance consolide le BFS (Séance 4) et introduit les composantes connexes. Le DFS ayant déjà été vu et comparé au BFS dès la Séance 2/4, ces notions sont désormais réunies : elles préparent directement les étudiantes à l'évaluation (partiel blanc), qui reprend BFS, DFS et composantes connexes dans un contexte de lecture de réseau. La séance suivante (6-7) introduit les graphes pondérés et l'algorithme de Dijkstra.

Dernière mise à jour : 24/07/2026