Algorithmes des Graphes - L3 Sociologie Quantitative
Cours d'algorithmes des graphes pour les étudiants de L3 en sociologie quantitative.
Objectifs
Comprendre et utiliser les graphes pour analyser les réseaux sociaux et les relations entre individus : - Modéliser des interactions sociales - Identifier les individus influents - Détecter des communautés - Analyser la diffusion d'information
Ouvrir les notebooks
| Outil | Installation |
|---|---|
| Basthon | En ligne, sans installation |
| Jupyter Notebook | pip install notebook puis jupyter notebook |
| Google Colab | colab.research.google.com |
Programme — 12 séances (24h)
Aligné sur le programme officiel de la maquette (BCC5, EC "Algorithme des graphes"). Une séance tampon (11) est explicitement réservée pour absorber le retard selon le niveau réel de la promo plutôt que de préparer un second parcours en parallèle, notamment s'il y a du retard sur Python.
| # | Séance | Statut |
|---|---|---|
| 1 | Définitions, typologie des graphes, prise en main de NetworkX | Fait |
| 2 | Représentations : matrice et liste d'adjacence, matrice/liste d'incidence | Fait |
| 3 | Mesures statistiques avancées (clustering, distribution des degrés...) | Fait |
| 4 | Parcours BFS/DFS | Fait |
| 5 | Composantes connexes + diffusion d'information (BFS) | Fait |
| 6-7 | Graphes pondérés et algorithme de Dijkstra (allégé) | Fait |
| 8 | Centralité (degré, proximité, intermédiarité) | Fait |
| 9 | Coloration de graphes | Fait |
| 10 | Page-rank et propagation d'étiquettes (label propagation) | Fait |
| 11 | Séance tampon / rattrapage | réservée, pas de contenu fixe |
| 12 | Révisions + partiel blanc | Fait |
Applications sociologiques (fil rouge de tout le cours)
- Analyse des réseaux sociaux, identification des individus influents
- Détection de communautés
- Étude des inégalités d'accès aux ressources
- Diffusion des idées et innovations
Structure du dépôt
├── COURS.md # Chapitre 1 : introduction contextuelle
├── FONDAMENTAUX.md # Chapitre 2 : concepts de base
├── Seance_1.ipynb / Seance_1_TP.ipynb # Séance 1 : prise en main de NetworkX
├── Seance_2_Representations.ipynb # Séance 2 : matrice/liste d'adjacence, incidence
├── Seance_3_Mesures_Statistiques.ipynb # Séance 3 : mesures statistiques avancées
├── Seance_4_BFS_DFS.ipynb # Séance 4 : parcours & distances (BFS/DFS)
├── Seance_5_Composantes_Diffusion.ipynb (+ Corrigé) # Séance 5 : composantes connexes & diffusion
├── Dijkstra/ # Séance 6 (recap + intuition), Séance 7 (implémentation), annexes optionnelles (preuve/complexité, version dictionnaire)
├── Seance_8_Centralite.ipynb # Séance 8 : centralité
├── Seance_9_Coloration.ipynb # Séance 9 : coloration de graphes
├── Seance_10_PageRank_LabelPropagation.ipynb # Séance 10 : page-rank & label propagation
├── Exercices_1.md, Exercices_2.md # Exercices complémentaires
├── Seance_12_Partiel.md / Seance_12_Partiel_Corrige.md # Partiel blanc et son corrigé
├── Exercices/, copies/ # Travaux et rendus d'étudiants
└── assets/ # Images et schémas
Ressources
- Introduction contextuelle (cours)
- Concepts fondamentaux (cours)
- Exercices — série 1
- Exercices — série 2
- Partiel blanc (le corrigé reste privé, non publié)
Licence
Ce cours est sous licence CC BY-NC-SA 4.0.
Florian Mathieu
Dernière mise à jour : 24/07/2026