© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Le but de l’activité est de modéliser les relations d'un réseau social à l'aide de graphes, et d'introduire les notions de matrice d'adjacence et de diamètre d'un graphe.
1. a. Des relations d'amitiés au sein d'un réseau social sont présentées ci-dessus. La relation d'amitié considérée est une relation réflexive (réciproque). A l'aide de la vidéo suivante, donner:
Pour les corrections de cette question, voir les résultats des saisies Python.
1. b. On code en Python le graphe précédent à l'aide de la structure G1 ci-dessous. Expliquer brièvement comment sont stockées les informations du graphe dans G1.
G1 donne la correspondance entre chaque sommet et la liste des sommets qui lui sont adjacents.
Attention : Penser ensuite à exécuter la zone ci-dessous (et les suivantes) avec SHIFT+Entrée.
G1 = { 'A':['C','F'] ,
'B':['C','D','E','F'] ,
'C':['A','B','F'] ,
'D':['B','E'] ,
'E':['B','D'] ,
'F':['A','B','C']
}
1. c. La fonction Python repr_graphe ci-dessous permet de représenter un graphe à partir de sa structure en Python. Tester l'appel à cette fonction pour G1 et vérifier qu'on obtient bien le graphe initial.
#import des modules pour les calculs et graphiques
from math import*
import numpy as np
import matplotlib.pyplot as plt
def non_oriente(Graphe):
"""
Fonction qui indique si un graphe n'est pas orienté
"""
for S in Graphe:
for adj in Graphe[S]:
if S not in Graphe[adj]: return False
return True
def repr_graphe(Graphe, r_sommets=0.1):
"""
Fonction qui représente un graphe stocké sous forme d'un dictionnaire
(la fonction trace des arêtes orientées si le graphe est orienté)
"""
#couleurs du graphique
col_p='black'
col_t='white'
#récupération du nombre de sommets
n_sommets=len(Graphe)
#préparation du graphique: axes masqués
fig, ax = plt.subplots() ; axes = plt.gca()
for dir in ['left','right','bottom','top']: ax.spines[dir].set_visible(False)
aff=1+r_sommets*1.1
plt.xlim(-aff,aff) ; axes.xaxis.set_ticks_position('none') ; axes.xaxis.set_ticklabels([])
plt.ylim(-aff,aff) ; axes.yaxis.set_ticks_position('none') ; axes.yaxis.set_ticklabels([])
#calcul des coordonnées des sommets:
x_sommet={} ; y_sommet={}
k=0
for S in Graphe:
angle=2*pi*k/n_sommets
x_sommet[S]=cos(angle)
y_sommet[S]=sin(angle)
k+=1
#tracé des arêtes
for S in Graphe:
for adj in Graphe[S]:
if non_oriente(Graphe):
#arête simple si le graphe n'est pas orienté
plt.plot([x_sommet[S],x_sommet[adj]],[y_sommet[S],y_sommet[adj]],color=col_p)
else:
#arête orientée sinon
x_vect=x_sommet[adj]-x_sommet[S] ; y_vect=y_sommet[adj]-y_sommet[S]
ax.arrow( x_sommet[S] , y_sommet[S] , x_vect*(1-2*r_sommets/sqrt(x_vect**2+y_vect**2)) , y_vect*(1-2*r_sommets/sqrt(x_vect**2+y_vect**2)) , head_width=r_sommets*2/3, head_length=r_sommets, fc=col_p, ec=col_p)
#tracé des sommets
k=0
for S in Graphe:
ax.add_patch(plt.Circle((x_sommet[S],y_sommet[S]), radius=r_sommets , color=col_p )) #disque représentant le sommet
plt.text(x_sommet[S]-r_sommets/4,y_sommet[S]-r_sommets/4,S, color=col_t) #nom du sommet
k+=1
#affichage général
plt.show()
#Appel à la fonction pour le graphe G1
repr_graphe(G1)
1. d. Les fonctions Python mat_adjacence, distance et diametre données ci-dessous permettent d'obtenir respectivement la matrice d'adjacence associée à un graphe, la distance entre deux de ses sommets et le diamètre de ce graphe. Effectuer les appels à ces fonctions et vérifier qu'on retrouve les réponses à la question 1.a.
#Pour utiliser l'ordre alphabétique
Alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def mat_adjacence(Graphe):
"""
Fonction qui renvoie la matrice d'adjacence d'un graphe (ordre alphabétique) avec liste ordonnée des noms de sommets
"""
#génération de la liste des sommets dans l'ordre alphabétique
Liste_sommets = [lettre for lettre in Alphabet if lettre in Graphe]
return np.matrix([ [ 1 if sommet_colonne in Graphe[sommet_ligne] else 0 for sommet_colonne in Liste_sommets ] for sommet_ligne in Liste_sommets ]),Liste_sommets
def distance(Graphe,debut,fin):
"""
Fonction qui renvoie la distance entre deux sommets
(renvoie infini par défaut si aucune chaîne n'existe)
"""
ADJ=mat_adjacence(Graphe)
M=ADJ[0]
try: rang_deb=ADJ[1].index(debut) ; rang_fin=ADJ[1].index(fin)
except: return float('inf')
for k in range(len(Graphe)):
if (M**k)[rang_deb,rang_fin]>0: return k
return float('inf')
def diametre(Graphe):
"""
Fonction qui renvoie le diamètre d'un graphe
"""
return max(distance(Graphe,s1,s2) for s2 in Graphe for s1 in Graphe)
#Appel pour obtenir la matrice d'adjacence associée à G1
mat_adjacence(G1)
#Appel pour obtenir la distance entre C et E
distance(G1,'C','E')
#Appel pour obtenir le diamètre du graphe G1
diametre(G1)
1. e. Le tableau ci-dessous recense des liens d'amitié existant dans un réseau social.
Voir le résultat de la saisie Python.
#Créer la structure G2 (structure similaire à G1)
G2 = { 'A':['E','G'] ,
'B':['C','F'] ,
'C':['B','D','E','G'] ,
'D':['C','G'] ,
'E':['A','C','F'] ,
'F':['B','E'] ,
'G':['A','C','D']
}
#Effectuer l'appel à la fonction repr_graphe
repr_graphe(G2)
Voir les résultats des saisies Python.
#Effectuer l'appel à la fonction mat_adjacence
mat_adjacence(G2)
#Effectuer l'appel à la fonction diametre
diametre(G2)
2. a. Certaines relations d'un réseau social ne sont pas réflexives (pas réciproques), c'est le cas par exemple du "Follow" sur Twitter. Le tableau ci-dessous recense des connaissances au sein d'un réseau social. Réaliser le graphe correspondant à cette situation (les arêtes seront orientées, représentées par des flèches), ainsi que la matrice d'adjacence associée.
Pour les réponses à cette question, voir les résultats des saisies Python.
2. b. Créer une structure Python G3 correspondant à ce graphe. Effectuer ensuite l'appel à la fonction Python repr_graphe permettant de construire le graphe, puis un appel à la fonction mat_adjacence. Pour finir, vérifier la cohérence avec la réponse à la question 2.a.
#Créer la structure G3 (structure similaire à G1 et G2)
G3 = { 'A':['B','E','F'] ,
'B':['D'] ,
'C':['A','G'] ,
'D':['B','C'] ,
'E':['D'] ,
'F':['B','E'] ,
'G':['C','D']
}
#Effectuer l'appel à la fonction repr_graphe
repr_graphe(G3)
#Effectuer l'appel à la fonction mat_adjacence
mat_adjacence(G3)
2. c. Quelle est la propriété d'une matrice d'adjacence d'un graphe non orienté (partie 1) qu'on ne retrouve pas dans le cas d'un graphe orienté (partie 2) ?
La matrice d'adjacence d'un graphe non orienté a une propriété de symétrie par rapport à sa diagonale principale, alors que ce n'est pas le cas pour la matrice d'adjacence associée à un graphe orienté.
3. a. La fonction et l'appel Python suivants permettent de générer une structure G4 correspondant à une situation aléatoire de 20 utilisateurs possédant chacun 5 connaissances vers d'autres utilisateurs (liens non nécessairement réciproques). A l'aide de la fonction Python repr_graphe, obtenir la représentation de ce graphe.
#Pour le choix au hasard des amis
from random import sample
#Pour utiliser l'ordre alphabétique
Alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def genere_graphe(n_sommets,n_liens):
Sommets=Alphabet[:n_sommets]
return { S:sample( [A for A in Sommets if A!=S] , n_liens ) for S in Sommets }
G4=genere_graphe(20,5)
G4
# Effectuer l'appel à la fonction repr_graphe
repr_graphe(G4)
3. b. Effectuer un appel à la fonction Python diametre pour ce graphe. Si on choisit deux utilisateurs au hasard, combien d'intermédiaires seront nécessaires pour former une chaîne de connaissances qui les relie?
#Effectuer l'appel à la fonction diametre
diametre(G4)
3. c. Relancer les zones Python des questions 3.a et 3.b pour simuler d'autres situations de 20 utilisateurs ayant 5 liens de connaissances, et comparer les résultats obtenus à la question 3.b.
En dehors de quelques cas où le diamètre est infini (certains utilisateurs ne sont pas reliés), on peut constater qu'il ne suffit souvent que de 2 à 3 utilisateurs intermédiaires pour obtenir une chaîne de connaissance (diamètre 3 ou 4).
Synthèse:
L'expérience du petit monde de Milgram est une hypothèse selon laquelle même si des personnes sont très nombreuses et ont un nombre assez limité de connaissances, le nombre de liens nécessaires pour former une chaîne entre deux personnes quelconques sera faible.
© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.