Faire calculer la machine
Tu as calculé à la main le diamètre d'un graphe de 6 sommets. Ça t'a pris un moment.
Le graphe d'amitiés de ta classe en compte une trentaine. Celui de Facebook, trois milliards. À la main, c'est terminé : il faudrait des siècles.
C'est exactement pour ça qu'on programme. Cette séance ne t'apprend aucune notion nouvelle de Python : elle te montre ce que tu sais déjà faire, appliqué à quelque chose d'impossible autrement.
Cours ici, exercices sur Capytale
Cette page est le cours. Les exercices sont sur Capytale.
Un vocabulaire que d'autres ont écrit pour nous
Souviens-toi : une fonction, c'est un mot ajouté au vocabulaire du langage. Quand tu as écrit carre(hortense, 100), tu avais toi-même défini le mot carre.
Mais rien n'oblige à définir ses mots soi-même. D'autres l'ont fait avant toi, et ils partagent leur travail. Pour les graphes, tout un vocabulaire existe déjà, dans une boîte à outils qui s'appelle NetworkX. On va s'en servir, exactement comme on est allé chercher Turtle dans turtle, ou Image dans PIL :
nx est simplement un surnom qu'on donne à la boîte à outils, pour écrire moins.
Déclarer un graphe : une arête à la fois
Pour donner un graphe à la machine, on lui déclare ses arêtes, une par ligne. Reprenons notre graphe G2 :
import networkx as nx
G2 = nx.Graph()
G2.add_edge("A", "B")
G2.add_edge("A", "E")
G2.add_edge("B", "C")
G2.add_edge("C", "D")
G2.add_edge("C", "F")
G2.add_edge("D", "F")
G2.add_edge("E", "F")
dessine(G2)
G2 = nx.Graph()crée un graphe vide et lui donne un nom. C'est le même geste quehortense = Turtle(): on crée un objet et on le range.G2.add_edge("A", "B")se lit « G2, ajoute une arête entre A et B ». Tu reconnais la notation pointée : on parle au graphe.- Il n'y a rien d'autre à faire. Les sommets apparaissent tout seuls dès qu'on les nomme dans une arête.
dessine(G2)affiche le graphe. C'est une fonction fournie dans le notebook.
Sept arêtes, sept lignes. Le graphe est maintenant dans la machine.
Ne t'étonne pas du dessin
La machine place les sommets où elle veut : ton dessin sur le cahier et le sien n'auront pas la même allure. Peu importe. Ce qui compte, ce sont les arêtes, pas la position des cercles. Vérifie simplement que chaque sommet a bien les bons voisins.
Vérifier ce qu'on a trouvé à la main
Voici les mots que NetworkX met à ta disposition. Chacun correspond exactement à une définition que tu as apprise :
| Ce que tu as calculé à la main | Le mot en Python |
|---|---|
| la distance entre deux sommets | distance(G2, "A", "D") |
| l'excentricité de chaque sommet | nx.eccentricity(G2) |
| le centre du graphe | nx.center(G2) |
| le rayon | nx.radius(G2) |
| le diamètre | nx.diameter(G2) |
Ce sont des appels de fonction, rien de plus : un nom, des parenthèses, et ce sur quoi on travaille. Tu sais faire ça depuis la tortue.
print("Excentricités :", nx.eccentricity(G2))
print("Centre :", nx.center(G2))
print("Rayon :", nx.radius(G2))
print("Diamètre :", nx.diameter(G2))
affiche :
Excentricités : {'A': 3, 'B': 2, 'C': 2, 'D': 3, 'E': 2, 'F': 2}
Centre : ['B', 'C', 'E', 'F']
Rayon : 2
Diamètre : 3
Compare avec ton cahier. Ce sont tes résultats. La machine n'a rien inventé : elle a appliqué les mêmes définitions que toi, simplement beaucoup plus vite.
Pourquoi c'est important
Tu viens de faire quelque chose de très sérieux : tu as vérifié un programme avec ta tête, et pas l'inverse.
Un programme qui donne un résultat que tu ne sais pas juger, c'est un programme auquel tu es obligé de croire. C'est parce que tu as fait le calcul à la main sur un petit cas que tu peux maintenant faire confiance à la machine sur un grand cas. Toujours dans cet ordre.
Passer à l'échelle
Maintenant, le vrai intérêt. On charge le graphe d'amitiés d'une classe entière depuis un fichier (une amitié par ligne, deux prénoms séparés par une virgule) :
Sur vingt-quatre élèves, le calcul à la main prendrait une heure. Le programme, lui, ne change pas d'une ligne.
Quand la machine refuse de répondre
Sauf que, si tu demandes le diamètre de cette classe, tu obtiens une erreur :
« Longueur de chemin infinie, car le graphe n'est pas connexe. »
Ce n'est pas un bug. La machine vient de te dire quelque chose de vrai sur cette classe : elle est coupée en deux. Quatre élèves ne sont reliés au reste par personne. Il n'existe donc aucun chemin entre eux et les autres, et la distance est infinie.
Souviens-toi de la séance sur le petit monde : sans lien de bridging, deux mondes ne se parlent plus du tout. Tu l'as lu comme une idée ; ici, tu le mesures.
Un message d'erreur est une information
Le réflexe du débutant est de fuir les messages d'erreur. Le réflexe du programmeur est de les lire : celui-ci ne dit pas « tu t'es trompé », il dit « ta question n'a pas de réponse, et voici pourquoi ».
On isole alors le grand groupe pour pouvoir travailler dessus, et on retient ce que l'erreur nous a appris.
La leçon de la séance
Programmer, ce n'est pas savoir des mots compliqués. C'est appliquer une méthode que tu comprends à une quantité de données que tu ne pourrais jamais traiter toi-même.
Le diamètre du réseau, tu sais ce que c'est. La machine, non : elle ne « comprend » rien. Elle applique juste ta définition, des millions de fois, sans se tromper et sans se fatiguer.
Et le petit monde ?
Tu vas pouvoir vérifier Milgram toi-même. Demande à la machine la distance moyenne entre deux membres du réseau :
Sur la classe, tu trouveras environ 2,5. Sur un vrai réseau social relevé par un sociologue (le club de karaté, 34 membres), environ 2,4, pour un diamètre de 5.
Le résultat est petit, très petit au regard de la taille du réseau. C'est le petit monde, mesuré, sur de vraies données, par toi.
Suggérer des amis
Dernière chose, et c'est celle qui va te faire comprendre ton fil d'actualité.
Souviens-toi du principe : les amis de mes amis sont probablement mes amis. En vocabulaire de graphe, on cherche les personnes situées à distance 2 de toi : pas encore tes amies, mais reliées à toi par un intermédiaire.
Le notebook te fournit le mot suggestions :
qui affiche :
Malo : 3 ami(s) en commun
Hugo : 2 ami(s) en commun
Noah : 1 ami(s) en commun
Enzo : 1 ami(s) en commun
Ce sont les personnes à distance 2 de Gabin, classées par nombre d'amis communs. Malo arrive en tête parce qu'il a trois amis en commun avec Gabin : c'est, de loin, la suggestion la plus probable.
Ce n'est pas de la magie
C'est, dans son principe, ce que font Facebook, Instagram et LinkedIn quand ils te proposent « des personnes que tu connais peut-être ». Ils cherchent les sommets à distance 2 dans le graphe, et les classent par nombre d'amis communs.
Les vrais algorithmes ajoutent des raffinements (le lycée, la ville, qui tu as regardé, à qui tu as écrit), mais le cœur est exactement celui-là, et tu viens de le comprendre.
Retiens ceci : quand une application semble « deviner » quelque chose sur toi, ce n'est jamais de la magie. C'est un calcul sur un graphe, et tu sais désormais lequel.
Ce qu'on retient
- Une boîte à outils comme NetworkX fournit un vocabulaire déjà défini : on ne redéfinit pas des mots que d'autres ont écrits.
- On déclare un graphe une arête à la fois :
G.add_edge("A", "B"). Les sommets apparaissent tout seuls. - Les mesures apprises en débranché ont chacune leur mot :
nx.eccentricity,nx.center,nx.radius,nx.diameter. - On vérifie d'abord la machine à la main, sur un petit cas, avant de lui faire confiance sur un grand. Jamais l'inverse.
- Un message d'erreur est une information : « graphe non connexe » signifie que le réseau est coupé en groupes séparés, entre lesquels la distance est infinie. Sans lien de bridging, pas de chemin.
- Programmer ici, ce n'est pas apprendre de la syntaxe : c'est appliquer à des millions de données une méthode qu'on comprend.
- Suggérer des amis = chercher les sommets à distance 2 et les classer par nombre d'amis communs. C'est tout.
Et ensuite
Tu sais comment un réseau social te représente, te mesure et te suggère des contacts. Reste la question qui fâche : pourquoi fait-il tout ça ? Qui paye, et qu'est-ce qu'il gagne ?