Aller au contenu

Exercices sur les Algorithmes des Graphes

Ces exercices sont destinés aux étudiants en sociologie quantitative pour découvrir les bases des algorithmes des graphes et leur application dans l'analyse des réseaux sociaux.

Exercice 1 : Représentation d’un réseau social avec des graphes

Objectif : Initier les étudiants à la modélisation de réseaux à l’aide de graphes.

Énoncé

Imaginez un groupe de personnes et leurs relations d’amitié, où chaque personne est représentée par un nœud, et chaque relation d'amitié par une arête (lien) entre deux nœuds. Construisez un graphe représentant les relations suivantes : - Alice est amie avec Bob et Carla. - Bob est ami avec Alice, Carla et Dan. - Carla est amie avec Alice, Bob et Eve. - Dan est ami avec Bob et Eve. - Eve est amie avec Carla et Dan.

  1. Représentez ce réseau sous forme de graphe en dessinant les nœuds et les arêtes.
  2. Utilisez une matrice d’adjacence pour représenter ce réseau (matrice où chaque ligne et colonne représente une personne et où les cases contiennent 1 si deux personnes sont amies, 0 sinon).
  3. Utilisez une liste d’adjacence pour représenter le même réseau (liste où chaque personne est associée à une liste de ses amis).

Question : Quelle représentation (matrice d’adjacence ou liste d’adjacence) serait, selon vous, la plus adaptée pour analyser des réseaux sociaux de grande taille ? Expliquez pourquoi.

Exercice 2 : Recherche de chemins dans un graphe

Objectif : Introduire la recherche de chemins dans un graphe et sa pertinence dans la sociologie quantitative.

Énoncé

Dans le réseau social précédent, vous devez trouver le plus court chemin entre Alice et Eve, c’est-à-dire le nombre minimum d’étapes (arêtes) pour aller de l’une à l’autre.

  1. Tracez le graphe du réseau.
  2. Utilisez une recherche en largeur (BFS) pour trouver le chemin le plus court entre Alice et Eve.
  3. Énumérez le chemin que vous avez trouvé et précisez le nombre d’étapes nécessaires.

Question : En sociologie, pourquoi serait-il pertinent de savoir qu'un individu peut rejoindre un autre en un nombre minimum d'étapes dans un réseau social ?

Exercice 3 : Identification de communautés dans un réseau

Objectif : Faire réfléchir les étudiants à la détection de communautés dans un réseau.

Énoncé

Dans le réseau social présenté dans le premier exercice, imaginez que les relations ne sont pas toutes égales en force : certaines amitiés sont plus fortes que d’autres, ce qui peut influencer la formation de groupes ou de communautés. Une manière simple de détecter les communautés est de voir si certaines personnes ont plus d’amis en commun entre elles qu’avec les autres.

  1. Identifiez les groupes de personnes qui ont plus de connexions entre elles qu'avec les autres (essayez d’isoler les sous-groupes formés de relations plus fortes).
  2. Proposez une méthode pour diviser le graphe en communautés et expliquez pourquoi certaines personnes sont plus susceptibles de former une communauté.

Question : En quoi cette notion de communauté peut-elle être utile pour analyser des phénomènes sociaux dans les études quantitatives ?

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