Aller au contenu

TP : Les 6 degrés de Kevin Bacon — Le petit monde des réseaux

Thème : Parcours de graphes et théorie des réseaux sociaux

Contexte

En 2026, les réseaux sociaux connectent des milliards de personnes. TikTok, Instagram, LinkedIn... Mais saviez-vous que vous êtes probablement relié(e) à n'importe quelle célébrité par seulement 6 intermédiaires ?

C'est la théorie des "Six degrés de séparation", popularisée par le jeu "Six Degrees of Kevin Bacon" : tout acteur d'Hollywood peut être relié à Kevin Bacon en moins de 6 films.

Dans ce TP, vous allez explorer cette théorie en utilisant les algorithmes de parcours de graphes.

Partie 1 : Comprendre le problème

Le nombre de Bacon

Le nombre de Bacon d'un acteur est la distance minimale (en nombre de films) qui le sépare de Kevin Bacon.

  • Kevin Bacon a un nombre de Bacon de 0
  • Un acteur qui a joué avec Kevin Bacon a un nombre de Bacon de 1
  • Un acteur qui a joué avec quelqu'un qui a joué avec Kevin Bacon a un nombre de Bacon de 2
  • Et ainsi de suite...

Exemple

Tom Hanks ──[Apollo 13]── Kevin Bacon
         → Nombre de Bacon = 1

Natalie Portman ──[Heat]── Robert De Niro ──[Sleepers]── Kevin Bacon
                → Nombre de Bacon = 2

Questions préliminaires

  1. Si un acteur A a joué avec un acteur B, quelle est la relation entre eux dans un graphe ?

  2. Quel algorithme de parcours permet de trouver le plus court chemin entre deux sommets ?

  3. Pourquoi BFS est-il préférable à DFS pour ce problème ?

Partie 2 : Modélisation du problème

Le graphe des acteurs

Nous allons modéliser Hollywood comme un graphe où : - Chaque sommet représente un acteur - Chaque arête relie deux acteurs qui ont joué dans le même film

Mini-base de données

Voici une petite base de données de films :

films = {
    "Apollo 13": ["Tom Hanks", "Kevin Bacon", "Bill Paxton"],
    "Forrest Gump": ["Tom Hanks", "Robin Wright", "Gary Sinise"],
    "The Dark Knight": ["Christian Bale", "Heath Ledger", "Gary Oldman"],
    "Inception": ["Leonardo DiCaprio", "Tom Hardy", "Marion Cotillard"],
    "Interstellar": ["Matthew McConaughey", "Anne Hathaway", "Jessica Chastain"],
    "Mystic River": ["Sean Penn", "Kevin Bacon", "Tim Robbins"],
    "X-Men First Class": ["James McAvoy", "Michael Fassbender", "Kevin Bacon"],
    "The Shawshank Redemption": ["Tim Robbins", "Morgan Freeman"],
    "Se7en": ["Morgan Freeman", "Brad Pitt", "Kevin Spacey"],
    "Fight Club": ["Brad Pitt", "Edward Norton", "Helena Bonham Carter"],
    "Harry Potter": ["Daniel Radcliffe", "Emma Watson", "Gary Oldman"],
    "Batman Begins": ["Christian Bale", "Liam Neeson", "Gary Oldman"],
    "Taken": ["Liam Neeson", "Maggie Grace"],
    "Lost in Translation": ["Bill Murray", "Scarlett Johansson"],
    "The Avengers": ["Scarlett Johansson", "Robert Downey Jr", "Chris Evans"],
    "Captain America": ["Chris Evans", "Sebastian Stan", "Robert Downey Jr"]
}

Exercice 1 : Construire le graphe

Complétez la fonction suivante qui construit le graphe des acteurs à partir de la base de films :

def construire_graphe_acteurs(films):
    """
    Construit un graphe où chaque acteur est un sommet
    et deux acteurs sont reliés s'ils ont joué dans le même film.

    Paramètre:
        films (dict): dictionnaire {nom_film: [liste_acteurs]}

    Retourne:
        dict: graphe sous forme de dictionnaire d'adjacence
    """
    graphe = {}

    for film, acteurs in films.items():
        # Pour chaque paire d'acteurs dans le film, créer une arête
        # À compléter...
        pass

    return graphe

Indice : Utilisez itertools.combinations(acteurs, 2) pour obtenir toutes les paires d'acteurs.

Partie 3 : Algorithme BFS pour le nombre de Bacon

Rappel : Parcours en largeur (BFS)

Le BFS explore le graphe niveau par niveau. Il est idéal pour trouver le plus court chemin dans un graphe non pondéré.

Exercice 2 : Implémenter le calcul du nombre de Bacon

Complétez la fonction suivante :

from collections import deque

def nombre_de_bacon(graphe, acteur, bacon="Kevin Bacon"):
    """
    Calcule le nombre de Bacon d'un acteur.

    Paramètres:
        graphe (dict): graphe des acteurs
        acteur (str): nom de l'acteur
        bacon (str): nom de la référence (Kevin Bacon par défaut)

    Retourne:
        int: le nombre de Bacon, ou -1 si non connecté
    """
    if acteur == bacon:
        return 0

    if acteur not in graphe or bacon not in graphe:
        return -1

    # BFS
    file = deque([(bacon, 0)])  # (sommet, distance)
    visite = {bacon}

    while file:
        # À compléter...
        pass

    return -1  # Non trouvé

Exercice 3 : Trouver le chemin

Modifiez l'algorithme pour retourner non seulement la distance, mais aussi le chemin (la liste des acteurs intermédiaires) :

def chemin_vers_bacon(graphe, acteur, bacon="Kevin Bacon"):
    """
    Trouve le plus court chemin entre un acteur et Kevin Bacon.

    Retourne:
        list: liste des acteurs formant le chemin, ou None si non connecté
    """
    # À compléter...
    pass

Partie 4 : Analyse du réseau

Exercice 4 : Statistiques globales

Écrivez des fonctions pour calculer les statistiques suivantes :

def nombre_bacon_moyen(graphe, bacon="Kevin Bacon"):
    """Calcule le nombre de Bacon moyen de tous les acteurs."""
    # À compléter...
    pass

def acteur_le_plus_eloigne(graphe, bacon="Kevin Bacon"):
    """Trouve l'acteur avec le plus grand nombre de Bacon."""
    # À compléter...
    pass

def acteurs_non_connectes(graphe, bacon="Kevin Bacon"):
    """Liste les acteurs qui ne sont pas connectés à Kevin Bacon."""
    # À compléter...
    pass

Exercice 5 : Visualisation

Utilisez la bibliothèque networkx pour visualiser le graphe :

import networkx as nx
import matplotlib.pyplot as plt

def visualiser_graphe(graphe, acteur_central="Kevin Bacon"):
    """
    Affiche le graphe avec des couleurs selon la distance à l'acteur central.
    """
    G = nx.Graph(graphe)

    # Calculer les distances
    distances = nx.single_source_shortest_path_length(G, acteur_central)

    # Couleurs selon la distance
    couleurs = [distances.get(node, -1) for node in G.nodes()]

    # Affichage
    plt.figure(figsize=(12, 8))
    pos = nx.spring_layout(G, seed=42)
    nx.draw(G, pos, with_labels=True, node_color=couleurs,
            cmap=plt.cm.RdYlGn_r, node_size=500, font_size=8)
    plt.title(f"Graphe des acteurs (distance à {acteur_central})")
    plt.show()

Partie 5 : Extension — Votre propre réseau

Exercice 6 : Réseau social de la classe

Créez un graphe représentant les relations d'amitié dans votre classe (ou un réseau fictif) et calculez :

  1. Qui est le "Kevin Bacon" de la classe (la personne la plus centrale) ?
  2. Quel est le diamètre du graphe (la plus grande distance entre deux personnes) ?
  3. Y a-t-il des personnes isolées ?
def centralite(graphe):
    """
    Trouve la personne la plus centrale du graphe
    (celle qui minimise la somme des distances aux autres).
    """
    # À compléter...
    pass

def diametre(graphe):
    """
    Calcule le diamètre du graphe
    (la plus grande distance entre deux sommets connectés).
    """
    # À compléter...
    pass

Partie 6 : Réflexion

Questions de synthèse

  1. Six degrés de séparation : Pourquoi pensez-vous que le nombre 6 revient souvent dans les réseaux sociaux réels ?

  2. Croissance des connexions : Si chaque personne connaît en moyenne 100 personnes, combien de personnes peut-on atteindre en 2, 3, puis 6 étapes ? (Ordre de grandeur)

  3. Limites du modèle : Notre graphe est non pondéré. Comment pourrait-on le modifier pour tenir compte de la "force" des liens (amis proches vs simples connaissances) ?

  4. Application réelle : Citez une application concrète de ces algorithmes dans un réseau social moderne (LinkedIn, Facebook, etc.).

Débat : La centralité du pouvoir

Dans un réseau social, les personnes très centrales ont un "pouvoir" particulier : elles peuvent diffuser rapidement une information à tout le réseau.

  • Est-ce un avantage ou un danger pour la société ?
  • Comment les plateformes comme TikTok ou Instagram utilisent-elles cette notion de centralité ?

Bonus : Oracle de Bacon en ligne

Le site The Oracle of Bacon permet de calculer le nombre de Bacon de n'importe quel acteur dans une base de données de millions de films.

Testez avec vos acteurs préférés !

Question bonus : L'acteur moyen a un nombre de Bacon d'environ 2.9. Qu'est-ce que cela nous dit sur la structure du réseau des acteurs d'Hollywood ?

Résumé des notions

Concept Application dans ce TP
Graphe non orienté Réseau d'acteurs
Sommet Un acteur
Arête Deux acteurs ont joué ensemble
BFS Calcul du plus court chemin
Distance Nombre de Bacon
Centralité L'acteur le plus "connecté"
Diamètre La plus grande distance dans le graphe

Annexe : Solution de l'exercice 1

Cliquez pour afficher 
from itertools import combinations

def construire_graphe_acteurs(films):
    graphe = {}

    for film, acteurs in films.items():
        # Créer les sommets si nécessaire
        for acteur in acteurs:
            if acteur not in graphe:
                graphe[acteur] = set()

        # Créer les arêtes (toutes les paires d'acteurs)
        for a1, a2 in combinations(acteurs, 2):
            graphe[a1].add(a2)
            graphe[a2].add(a1)

    # Convertir les sets en listes
    return {k: list(v) for k, v in graphe.items()}

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.