Réseaux sociaux : distances, diamètre et centre d'un graphe

Dans les exemples de cette leçon, on étudie un graphe connexe, non orienté et non pondéré : toute personne est reliée aux autres par une chaîne, l’amitié est réciproque et chaque lien compte pour un. Un réseau social se représente ici par un graphe : chaque personne est un sommet, et deux sommets sont reliés par une arête quand les deux personnes sont amies.

La distance entre deux personnes est le plus petit nombre de liens à suivre pour aller de l'une à l'autre. Exemple, avec six personnes :

Ana et Dina ne sont pas amies, mais Ana → Bruno → Dina les relie en deux liens : leur distance est 2. Ana et Fanny sont à distance 4 (Ana → Bruno → Dina → Ethan → Fanny).

Sur le graphe connexe étudié, tous les sommets sont accessibles. Dans un réseau non connexe, on travaille séparément par composante ; le programme donné ne définit pas une distance finie vers une personne inaccessible.

• L'écartement d'une personne est sa plus grande distance à une autre personne du réseau.
• Le diamètre du graphe est le plus grand des écartements.
• Le rayon est le plus petit des écartements.
• Le centre est formé des personnes dont l'écartement est égal au rayon.

Le programme ci-dessous est une vérification facultative ; sa syntaxe avancée n’est pas un attendu à maîtriser en SNT. Il calcule les distances depuis chaque personne en explorant le réseau couche par couche (les amis, puis les amis des amis…), puis en déduit ces grandeurs :

amis = {
    "Ana": ["Bruno", "Clara"],
    "Bruno": ["Ana", "Clara", "Dina"],
    "Clara": ["Ana", "Bruno"],
    "Dina": ["Bruno", "Ethan"],
    "Ethan": ["Dina", "Fanny"],
    "Fanny": ["Ethan"],
}

def distances(depart):
    dist = {depart: 0}
    file = [depart]
    while file:
        p = file.pop(0)
        for q in amis[p]:
            if q not in dist:
                dist[q] = dist[p] + 1
                file.append(q)
    return dist

ecart = {p: max(distances(p).values()) for p in amis}
print(ecart)
print("diamètre", max(ecart.values()), "rayon", min(ecart.values()))
print("centre", [p for p in amis if ecart[p] == min(ecart.values())])

{'Ana': 4, 'Bruno': 3, 'Clara': 4, 'Dina': 2, 'Ethan': 3, 'Fanny': 4}
diamètre 4 rayon 2
centre ['Dina']

Dina est le centre : aucune personne n'est à plus de deux liens d'elle.

Petit monde. Les expériences de chaînes de connaissances de Milgram, décrites notamment par Travers et Milgram en 1969, ont observé des chaînes courtes parmi celles ayant atteint une personne cible. L’échantillon était particulier et de nombreuses chaînes n’ont pas abouti : cela ne prouve pas une distance universelle entre deux personnes quelconques. La longueur d’un chemin dans un graphe compte des liens ; elle ne mesure pas une vitesse réelle de diffusion, qui dépend aussi des délais, des choix et de l’activité des personnes.

Énoncé. Dans le réseau précédent, quel est l'écartement de Bruno ?

Méthode : par couches.

1. Distance 1 : ses amis Ana, Clara, Dina.
2. Distance 2 : les amis de ceux-ci, pas encore atteints : Ethan (ami de Dina).
3. Distance 3 : Fanny (amie d'Ethan).

Toutes les personnes sont atteintes ; la plus éloignée, Fanny, est à distance 3. L'écartement de Bruno est 3.

La dernière colonne donne les écartements : le plus grand (4) est le diamètre, le plus petit (2) le rayon.