Six degrés de séparation — mesurer un petit monde

On estime la distance moyenne en sélectionnant un échantillon représentatif de sources et en exécutant des BFS :

import random

def distance_moyenne(G: dict, nb_sources: int = 50) -> float:
    total, compte = 0, 0
    for s in random.sample(list(G), nb_sources):
        d = distances(G, s)  # BFS complet
        total += sum(d.values())
        compte += len(d) - 1
    return total / compte

L'introduction de seulement 1 % d'arêtes aléatoires (raccourcis) divise la distance moyenne par un facteur 5, illustrant de façon algorithmique le concept des "six degrés de séparation".