Exercice-Graphe-Réseaux sociaux

ex

La 'star' d'un réseau est la personne qui est suivie par le plus grand nombre et qui suit le moins de monde.
Quelle est la star de ce réseau?

On donne le script suivant, quel est son rôle :

In [ ]:
friend=\
[[0,0,1,1,0,0,1],
[0,0,0,0,1,1,0],
[1,0,0,1,1,1,0],
[1,0,1,0,0,0,1],
[0,1,1,0,0,1,0],
[0,1,1,0,1,0,0],
[1,0,0,1,0,0,0]]

Nom=["Alice","Bob","Chloé","David","Emma","Fred","Zoé"]

for i in range(0,7,1):
    nombamis=0
    for j in range(0,7,1):
        if friend[i][j]==1:
            nombamis=nombamis+1
    print(Nom[i],"a",nombamis, "amis")

En vous inspirant du précédent programme, écrire un programme qui donne le nombre de 'followers' de chaque personne

On souhaite calculer le nombre d'amis d'amis de chaque personne. Par exemple : Alice a 6 amis d'amis : Tout le monde sauf Bob

Le nombre d'amis d'amis d'une personne $i$ est exactement le nombre de sommets $j$
dont la distance à $i$ est inférieure ou égale à 2

Déterminer par une méthode de votre choix (que vous expliquerez) Le nombre d'amis d'amis de chaque personne:

Complément

Dans la théorie des graphes pour déterminer le nombre de chemin menant d'un sommet à un autre en deux étapes il suffit de calculer le carré de la matrice d'adjacence : calcul réalisé sur ce site

calcul

Interprétation du résultat :

3 0 1 2 1 1 1 : signifie qu'il y a 3 chemins pour aller de Alice à Alice en 2 étapes, aucun pour atteindre Bob , 1 pour atteindre Chloé etc...

Au total 6 amis d'amis pour Alice
4 pour Bob
7 pour Chloé
6 pour David, Emma et Fred
Et 4 pour Zoé
En vous inspirant de cette méthode:

Quels sont les personnes qui n'ont pas 7 amis d'amis d'amis ?