Problème — Amis communs et suggestions dans un réseau social

La première question est une intersection d'ensembles de voisins. La seconde exploite le fait que les bonnes suggestions sont les amis d'amis : on compte, pour chaque candidat, combien d'amis il partage avec a.

def amis_communs(reseau, a, b):
    return set(reseau[a]) & set(reseau[b])

def suggestions(reseau, a):
    amis_de_a = set(reseau[a])
    scores = {}   # candidat -> nombre d'amis communs avec a
    for ami in reseau[a]:
        for candidat in reseau[ami]:
            if candidat != a and candidat not in amis_de_a:
                scores[candidat] = scores.get(candidat, 0) + 1
    # tri par score decroissant
    return sorted(scores, key=lambda c: scores[c], reverse=True)

reseau = {
    "Alice":  ["Bob", "Chloe"],
    "Bob":    ["Alice", "Chloe", "David"],
    "Chloe":  ["Alice", "Bob", "Eve"],
    "David":  ["Bob"],
    "Eve":    ["Chloe"],
}
print(amis_communs(reseau, "Alice", "Bob"))  # {'Chloe'}
print(suggestions(reseau, "Alice"))          # ['David', 'Eve']

David (ami de Bob) et Eve (amie de Chloé) sont suggérés à Alice. Le calcul des suggestions parcourt les amis d'amis, soit une complexité de l'ordre de $O\left({\sum }_u\mathrm{deg}(u)\right)$ autour du voisinage de a.