{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "# Séance 6 — Parcours en largeur (BFS) : comment l’information se propage dans un réseau\n\n## Objectifs\n- Comprendre intuitivement ce qu’est un **parcours en largeur** (Breadth-First Search ou BFS).\n- Relier ce concept à la **diffusion d’une information, d’une rumeur ou d’une idée** dans un réseau social.\n- Explorer un réseau avec Python et `networkx` pour visualiser cette propagation.\n- Comparer avec une autre stratégie d’exploration : le **parcours en profondeur (DFS)**.\n"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 1. Introduction sociologique : une rumeur se propage\nImaginez qu’une personne — appelons-la **Alice** — partage une nouvelle dans son groupe d’amis.\nChacun la répète à ses proches, et ainsi de suite.\n\nL’information se diffuse **par cercles successifs** : d’abord les amis directs d’Alice, puis les amis des amis, etc.\n\nC’est exactement ce que fait un **parcours en largeur** : explorer un réseau *niveau par niveau*.\n\n→ En sociologie des réseaux, cela correspond à la **distance sociale** entre individus."
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 2. Exemple manuel : propagation d’une information\nConsidérons ce réseau :\n\n```\nAlice — Bob — Chloé — David\n  │       │      │\n Emma    Félix   Gaël\n```\n\nSupposons qu’Alice commence à diffuser une nouvelle.\n\n**Étapes :**\n1. Niveau 0 : Alice\n2. Niveau 1 : les personnes directement connectées à Alice → {Bob, Emma}\n3. Niveau 2 : les amis de Bob (hors Alice) → {Chloé, Félix}\n4. Niveau 3 : les amis de Chloé → {David, Gaël}\n\nChaque *niveau* correspond à une **distance sociale** par rapport à la source."
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 3. Visualisation avec Python\nCréons ce réseau et voyons comment le BFS le parcourt."
    },
    {
      "cell_type": "code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": "import networkx as nx\nimport matplotlib.pyplot as plt\n\n# Création du graphe\nG = nx.Graph()\nG.add_edges_from([\n    ('Alice', 'Bob'), ('Alice', 'Emma'),\n    ('Bob', 'Chloé'), ('Bob', 'Félix'),\n    ('Chloé', 'David'), ('Chloé', 'Gaël')\n])\n\nplt.figure(figsize=(6,4))\npos = nx.spring_layout(G, seed=0)\nnx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=1000)\nplt.title('Réseau social — Diffusion de la nouvelle')\nplt.show()"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 4. Explorer le réseau en largeur\nOn peut utiliser la fonction `nx.bfs_tree()` pour construire un arbre de parcours à partir d’un point de départ (ici, Alice)."
    },
    {
      "cell_type": "code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": "source = 'Alice'\nT = nx.bfs_tree(G, source=source)\n\nplt.figure(figsize=(6,4))\nnx.draw(T, with_labels=True, node_color='lightgreen', node_size=1000)\nplt.title(f'Arbre BFS à partir de {source}')\nplt.show()\n\nprint('Ordre du parcours BFS :')\nprint(list(nx.bfs_edges(G, source)))"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 5. Distances sociales depuis Alice\nLe BFS permet aussi de mesurer la **distance minimale** entre Alice et chaque autre personne."
    },
    {
      "cell_type": "code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": "distances = nx.single_source_shortest_path_length(G, source)\nprint('Distances sociales depuis Alice :')\nfor k, v in distances.items():\n    print(f'{k} : {v}')"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "### Interprétation sociologique\n- Les **valeurs faibles** indiquent des individus **proches** d’Alice (accès direct à l’information).\n- Les **valeurs élevées** indiquent des individus **périphériques** : ils n’apprennent la nouvelle que tardivement.\n\n→ Cela permet d’analyser la **vitesse de diffusion** ou la **position sociale** dans le réseau."
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 6. Comparaison intuitive : BFS vs DFS\nPour bien comprendre la logique du BFS, comparons-le brièvement à une autre stratégie : le **DFS**.\n\n| Stratégie | Métaphore | Manière d’explorer | Exemple |\n|:-----------|:-----------|:------------------|:---------|\n| BFS (largeur) | diffusion sociale | explore les cercles autour de la source | bouche-à-oreille, information publique |\n| DFS (profondeur) | exploration ciblée | suit un chemin jusqu’au bout avant de revenir | enquête individuelle, relation hiérarchique |\n\nLe BFS **propagera rapidement une information**, tandis que le DFS **creusera une piste en profondeur**."
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 7. Pour aller plus loin\n- Comment interpréteriez-vous un individu qui n’est **atteint par personne** (non connexe) ?\n- Si plusieurs personnes diffusent simultanément une info, que se passe-t-il ?\n- Quels phénomènes réels le BFS peut-il modéliser ? (rumeur, contagion, propagation d’un hashtag, etc.)"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## 8. Synthèse\n- Le **BFS** explore un réseau **par cercles successifs** à partir d’une source.\n- Il permet de mesurer la **distance sociale** et d’identifier les **positions centrales**.\n- Dans un graphe non connexe, certaines personnes ne reçoivent jamais l’information.\n- Le **DFS**, lui, suit une logique d’exploration **en profondeur**, utile pour détecter des **sous-groupes**.\n"
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.x"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}