{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons.\n\n Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"},{"metadata":{},"cell_type":"markdown","source":"# Réseaux sociaux et graphes"},{"metadata":{},"cell_type":"markdown","source":"*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.*\n"},{"metadata":{},"cell_type":"markdown","source":"## 1. Relation d'amitié réflexive : Graphe non orienté"},{"metadata":{},"cell_type":"markdown","source":"![Reseau_social_amities](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/ReseauSocial_1.png)\n\n__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:__\n\n\n\n - la matrice d'adjacence associée à ce graphe ;
\n - la distance de C à E ;
\n - le diamètre de ce graphe.
\n
\n\n\n"},{"metadata":{},"cell_type":"markdown","source":"__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.__\n\n\nAttention : Penser ensuite à exécuter la zone ci-dessous (et les suivantes) avec SHIFT+Entrée."},{"metadata":{"trusted":false},"cell_type":"code","source":"G1 = { 'A':['C','F'] , \n 'B':['C','D','E','F'] , \n 'C':['A','B','F'] , \n 'D':['B','E'] , \n 'E':['B','D'] , \n 'F':['A','B','C'] \n }","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__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.__\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"#import des modules pour les calculs et graphiques\nfrom math import*\nimport numpy as np\nimport matplotlib.pyplot as plt\n\ndef non_oriente(Graphe):\n \"\"\"\n Fonction qui indique si un graphe n'est pas orienté\n \"\"\"\n for S in Graphe:\n for adj in Graphe[S]:\n if S not in Graphe[adj]: return False\n return True\n \ndef repr_graphe(Graphe, r_sommets=0.1):\n \"\"\"\n Fonction qui représente un graphe stocké sous forme d'un dictionnaire\n (la fonction trace des arêtes orientées si le graphe est orienté)\n \"\"\"\n #couleurs du graphique\n col_p='black' \n col_t='white' \n \n #récupération du nombre de sommets\n n_sommets=len(Graphe)\n \n #préparation du graphique: axes masqués\n fig, ax = plt.subplots() ; axes = plt.gca()\n for dir in ['left','right','bottom','top']: ax.spines[dir].set_visible(False)\n aff=1+r_sommets*1.1\n plt.xlim(-aff,aff) ; axes.xaxis.set_ticks_position('none') ; axes.xaxis.set_ticklabels([])\n plt.ylim(-aff,aff) ; axes.yaxis.set_ticks_position('none') ; axes.yaxis.set_ticklabels([])\n \n #calcul des coordonnées des sommets:\n x_sommet={} ; y_sommet={}\n k=0\n for S in Graphe:\n angle=2*pi*k/n_sommets\n x_sommet[S]=cos(angle)\n y_sommet[S]=sin(angle)\n k+=1\n \n #tracé des arêtes\n for S in Graphe:\n for adj in Graphe[S]:\n if non_oriente(Graphe):\n #arête simple si le graphe n'est pas orienté\n plt.plot([x_sommet[S],x_sommet[adj]],[y_sommet[S],y_sommet[adj]],color=col_p)\n else:\n #arête orientée sinon\n x_vect=x_sommet[adj]-x_sommet[S] ; y_vect=y_sommet[adj]-y_sommet[S]\n 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)\n \n #tracé des sommets\n k=0\n for S in Graphe:\n ax.add_patch(plt.Circle((x_sommet[S],y_sommet[S]), radius=r_sommets , color=col_p )) #disque représentant le sommet\n plt.text(x_sommet[S]-r_sommets/4,y_sommet[S]-r_sommets/4,S, color=col_t) #nom du sommet\n k+=1 \n \n #affichage général\n plt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Appel à la fonction pour le graphe G1\nrepr_graphe(G1)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__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.__ "},{"metadata":{"trusted":false},"cell_type":"code","source":"#Pour utiliser l'ordre alphabétique\nAlphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n\ndef mat_adjacence(Graphe):\n \"\"\"\n Fonction qui renvoie la matrice d'adjacence d'un graphe (ordre alphabétique) avec liste ordonnée des noms de sommets\n \"\"\"\n #génération de la liste des sommets dans l'ordre alphabétique\n Liste_sommets = [lettre for lettre in Alphabet if lettre in Graphe]\n \n 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\n \ndef distance(Graphe,debut,fin):\n \"\"\"\n Fonction qui renvoie la distance entre deux sommets\n (renvoie infini par défaut si aucune chaîne n'existe)\n \"\"\"\n ADJ=mat_adjacence(Graphe)\n M=ADJ[0]\n try: rang_deb=ADJ[1].index(debut) ; rang_fin=ADJ[1].index(fin)\n except: return float('inf')\n \n for k in range(len(Graphe)):\n if (M**k)[rang_deb,rang_fin]>0: return k\n \n return float('inf')\n \ndef diametre(Graphe):\n \"\"\"\n Fonction qui renvoie le diamètre d'un graphe\n \"\"\"\n return max(distance(Graphe,s1,s2) for s2 in Graphe for s1 in Graphe)\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Appel pour obtenir la matrice d'adjacence associée à G1\nmat_adjacence(G1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Appel pour obtenir la distance entre C et E\ndistance(G1,'C','E')","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Appel pour obtenir le diamètre du graphe G1\ndiametre(G1)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__1. e. Le tableau ci-dessous recense des liens d'amitié existant dans un réseau social.__ \n\n![Reseau_social_amities_2](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/ReseauSocial_2.png)\n\n\n- Réaliser le graphe correspondant à cette nouvelle situation.
\n
\n"},{"metadata":{},"cell_type":"markdown","source":"\n- Créer une structure Python G2 correspondant à ce graphe, puis effectuer l'appel à la fonction Python repr_graphe permettant de construire le graphe. Vérifier la cohérence avec la réponse précédente.
\n
"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Créer la structure G2 (structure similaire à G1)\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction repr_graphe\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n- Déterminer, à la main, la matrice d'adjacence associée à ce graphe et son diamètre, puis vérifier vos résultats à l'aide d'appels aux fonctions Python mat_adjacence et diametre.
\n
\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction mat_adjacence \n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction diametre\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 2. Relation de connaissance non réflexive : Graphe orienté"},{"metadata":{},"cell_type":"markdown","source":"__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.__\n\n\n![Reseau_social_connaissance](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/ReseauSocial_3.png)"},{"metadata":{},"cell_type":"markdown","source":"__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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Créer la structure G3 (structure similaire à G1 et G2)\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction repr_graphe\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction mat_adjacence\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__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) ?__\n\n"},{"metadata":{},"cell_type":"markdown","source":"## 3. Expérience du petit monde de Milgram"},{"metadata":{},"cell_type":"markdown","source":"__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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Pour le choix au hasard des amis\nfrom random import sample\n\n#Pour utiliser l'ordre alphabétique\nAlphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n\ndef genere_graphe(n_sommets,n_liens):\n Sommets=Alphabet[:n_sommets]\n return { S:sample( [A for A in Sommets if A!=S] , n_liens ) for S in Sommets } \n \nG4=genere_graphe(20,5)\nG4 ","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Effectuer l'appel à la fonction repr_graphe\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__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?__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer l'appel à la fonction diametre\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__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.__\n\n\n__Synthèse:__\n\n\nL'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.\n\n\n![Stanley_Milgram](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/Milgram.png)\n\nStanley Milgram, psychologue social américain\n"},{"metadata":{},"cell_type":"markdown","source":"© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons."}],"metadata":{"celltoolbar":"Raw Cell Format","kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.7.10"}},"nbformat":4,"nbformat_minor":2}