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

1. Introduction contextuelle

Les graphes en sciences sociales : modélisation des relations, réseaux sociaux, exemples Facebook/Twitter.

2. Types de graphes

Type	Description	Exemple
Non dirigé	Relations réciproques	Amitié Facebook
Dirigé	Relations orientées	Followers Twitter
Pondéré	Force des relations	Fréquence d'interaction
Biparti	Deux types d'entités	Individus ↔ Opinions

3. Concepts fondamentaux

• Sommets et arêtes
• Degré d'un sommet
• Chemins et cycles
• Connexité

4. Algorithmes

Algorithme	Usage
Parcours en largeur (BFS)	Plus court chemin, exploration
Parcours en profondeur (DFS)	Détection de cycles, composantes
Dijkstra	Plus court chemin pondéré
Centralité	Identifier les nœuds influents

5. Applications sociologiques

• Analyse des réseaux sociaux
• 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

├── FONDAMENTAUX.md      # Concepts de base
├── Djikstra/            # Algorithme de Dijkstra
├── Exercices/           # Exercices pratiques
├── Corrige1/, 2/, 3/    # Corrigés
├── copies/              # Travaux étudiants
└── assets/              # Images et schémas

Ressources

• 📖 Introduction contextuelle (cours)
• 📄 Cours complet (PDF)
• 📄 Algorithmes des graphes (PDF)
• 📝 Exercices

Licence

Ce cours est sous licence CC BY-NC-SA 4.0.

---

Florian Mathieu