L’art de dessiner des graphes

“L’important n’est pas le but, mais le chemin qui y conduit.”

Lao Tseu

À priori, rien de plus facile que de tracer un graphe. Il suffit de prendre deux points et de les relier entre eux par un trait. Le point de départ et le point d’arrivée peuvent être nommés, A et B par exemple. Mais les choses se compliquent lorsque les points et les liens sont nombreux ou doivent contenir des informations supplémentaires. Un point peut symboliser un emplacement géolocalisé par exemple (Graphe 1, Graphe 2). Il peut aussi être une représentation d’un mobile comme un piéton se déplaçant sur un sentier, ou bien un animal marin portant une balise GPS.

Maillage
Graphe 1 : Réseau géodésique français, avec méridienne de Paris, pour la réalisation de la carte d’État-major au 1/40 000 élaborée entre 1825 et 1866. Lien
paris-metro
Graphe 2  : Diagramme de Sankey 3D du flux de passagers dans le métro parisien par Etienne Come avec mapbox.com. Lien

Dérivé du grec ancien γράφος, gráphos « écrit ou dessiné», le graphe correspond à un ensemble de nœuds (sommets) reliés par des arêtes (arcs) qui servent de modèle pour décrire des mouvements dans le temps et l’espace, pour indiquer des relations de causalités ou bien des sémantiques. Les arbres, les chaînes, les réseaux et les cycles sont des sortes de graphes. Euler propose dès 1735 une étude sur les chemins rendus possibles par les sept ponts de Königsberg desservant deux îles centrales de la cité. Il fonde ainsi la théorie des graphes, branche des mathématiques discrètes dont les applications s’étendent à de multiples domaines (Ghys 2010, Zeste de savoir 2016).

Les mathématiques proposent des abstractions si bien qu’un sommet peut symboliser n’importe quoi dans un ensemble. Classiquement, il peut s’agir d’une station de métro, d’un document d’archive ou de bibliothèque, d’une expression linguistique, d’une organisation, d’un objet, d’une molécule, d’un être vivant, d’une espèce, d’un composant électronique. Les arêtes indiquent des relations, des liens. Elles peuvent symboliser un trajet, un pont, un fleuve, une relation parentale, une relation temporelle, un lien hypertexte, une relation entre champs de tables dans une base de données, une cause ou un effet. Un point peut également correspondre à quelque chose de plus abstrait, élément parmi d’autres, l’ensemble formant un tout. Un exemple pourrait être une connaissance, une discipline scientifique.

Globalement, la valeur d’un graphe dépend de sa capacité à décrire le réel et à répondre à des objectifs. Ainsi une carte routière devient plus intéressante lorsque des informations (des métadonnées) comme des limites de vitesse ou des lieux d’embouteillage sont indiqués sur les arêtes. L’estimation de l’heure d’arrivée sera meilleure.

Lorsque les nœuds et les arêtes sont nombreux, on parle alors de réseau.  Des réseaux guident les transports des passagers et des marchandises (réseaux routiers, de voies navigables et aériennes), de l’énergie et des fluides (eau, gaz, électricité), de l’information (Internet, téléphonie, monnaie, neurone). Des réseaux distincts sont susceptibles de montrer des dynamiques, de cohabiter, coopérer, fusionner ou bien au contraire d’entrer en compétition.

Les graphes modélisent des actions guidées par des intentions, comme le montre la chaîne de production mise en place dans le cadre d’une fabrication automobile (Graphe 3), ou bien le graphe des flux de capitaux entre pays produisant des biens et les centres financiers offshore (Graphe 4). Basés sur l’expérience et la pratique, des graphes et des réseaux guident les jeux, l’apprentissage et l’action. Quelques graphes glanés dans cinq disciplines différentes sont sélectionnés et commentés.

  1. L’informatique
  2. Gestion des connaissances
  3. Réseaux sociaux
  4. Biologie
  5. Art et symbolique
chaine_fabrication_auto
Graphe 3 : Les trois stades de la fabrication dans une chaîne automobile. Chaque avancée du produit sur la chaîne correspond à un cycle d’actions répétées localement de manière cyclique.
41598_2017_6322_Fig3_HTML
Graphe 4 : Centres financiers offshore: conduits et puits dans le réseau des propriétaires d’entreprises multinationales. Lien

1. L’informatique

Les graphes intéressent l’informatique à plus d’un titre. Un graphe arborescent classique correspond au système de fichiers rangé dans un dossier. Des bases de données sont dites relationnelles, orientées graphe (Neo4J) ou bien délivrent des graphes en réponse à des requêtes du type graphe, comme dans le cas des triple stores. Les formats de langages balisés tels que HTML, XML, TEI ou JSON fournissent une organisation de l’information en arbre binaire dans laquelle des marqueurs particuliers indiquent symétriquement l’ouverture et la fermeture d’un bloc.

Penser graphe (modéliser des relations, classer, normaliser, trouver un chemin optimisé) de manière normalisée s’avère intéressant dans plusieurs cas de figure. Il peut s’agir d’un côté de respecter des formats largement adoptés. Cette opération rend possible l’interopérabilité, c’est à dire le partage d’objets numériques et leur lecture par des outils standards comme un navigateur par exemple. Il peut s’agir encore de créer de nouveaux standards comme sont amenés à le faire le W3C et d’autres organismes. Ainsi, le langage d’API GraphQL proposé en 2012 par Facebook détrônera-t-il peut être prochainement le protocole REST actuellement en usage.

L’histoire d’un logiciel peut également être évoquée à l’aide d’un graphe. Ainsi, l’étonnant logiciel Gource génère à partir des logs d’un gestionnaires de code source tel que « git » la vidéo d’un arbre animé, image de l’activité des développeurs d’un projet informatique sur les différents modules d’un logiciel. Linux, espèce d’un nouveau genre en constante évolution, se différencie pour former un arbre du type cladogramme (Graphe 6).

linux-timeline
Graphe 6 : La frise chronologique des distributions Linux : Lien

2. Gestion des connaissances

Penser graphe s’avère de nouveau utile lorsque de vastes ensembles de connaissance doivent être gérés de manière professionnelle (Graphe 7). Ainsi, pour Diderot, l’entendement – la faculté de comprendre – se trouve à la base de toute discipline scientifique. Succédant aux articles des grandes encyclopédies du XVIIIème siècle, les entrées de Wikipédia peuvent être considérés comme des feuilles liées entre elles d’un arbre de connaissance multilingue dont l’anglais s’avère être parfois la langue la mieux renseignée.

Dans le domaine des archives, Martin Grandjean (Grandjean 2014) considère que les dossiers, collections et documents d’archives sont des éléments d’un vaste graphe de connaissance. L’archive devient alors un entrepôt de savoirs dans lequel des sources primaires servent de preuve lors d’études historiographiques, géographiques (Leturcq 2016), généalogiques ou sociales. Au-delà des sciences de l’information, la gestion et l’organisation des connaissances concerne de nombreux domaines, incluant les bibliothèques, les musées, les disciplines académiques et l’industrie.

genealogie-sciences
Graphe 7 : Une distribution généalogique des sciences et des arts principaux. Encyclopédie de Diderot, 1751.

L’idée principale du web sémantique est que toute connaissance peut être représentée sous forme d’un triplet RDF (Resource Description Framework) dans lequel un sujet est relié à un objet par un prédicat (Graphe 8). Des opérations logiques du type inférence deviennent alors possibles sur de multiples triplets éléments d’un même graphe stocké dans un dispositif. Des ressources externes peuvent être considérées et liées aux ressources internes. Des ontologies écrites en OWL (Langage d’ontologie du web) formalisent les classes de nœuds possibles, le nom des arêtes (prédicats) est encore appelé propriété ou bien champs. Le web sémantique devient alors complémentaire des traditionnels moteurs de recherche, introduisant de manière possible de nouvelles et fort spécialisées syntaxes d’interrogations.

Triplet RDF
Graphe 8 : Un triplet RDF

3. Réseaux sociaux

Tout le monde a bien conscience de faire partie de plusieurs réseaux relationnels définissant des familles, des cercles, des communautés. Des groupes d’individus partagent des liens de parenté, des liens générationnels, de travail ou de loisir, des langages, des émotions, des lieux, des routines, des modes de vie et des événements, bref des cultures et des histoires. Quelques réseaux classiquement étudiés par les historiens des sciences s’avèrent emblématiques.

De manière expérimentale, Moreno propose dès 1934 l’usage du sociogramme pour décrire les relations entre enfants de différentes classes d’âge placés en milieu scolaire. Un graphe décrit leurs relations amicales. Des graphes reflètent les structures de groupe telles qu’elles se développent et évoluent dans un groupe d’écoliers en période d’apprentissage (GrandJean 2014).

Le psychosociologue Milgram élabore en 1967 la théorie du « petit monde ». Son hypothèse de départ est que tout individu habitant les États Unis est relié à un autre par un nombre limité de relations interpersonnelles, de l’ordre de 6. Une expérience dans laquelle des personnes se transmettent de main à la main un document est effectuée afin d’éprouver la théorie.

Introduit dans les années 2000, le nombre d’Erdős enfin est un indicateur bibliométrique spécifique des mathématiques. Il évalue la distance d’un auteur dans le cadre de publications conjointes à Paul Erdős, le fameux hongrois aux 1500 articles et plus de 500 collaborations, théoricien lui-même du graphe aléatoire. Structurées en cycles, arbres et réseaux interconnectés, les sociétés apparaissent plus petites que notre intuition ne le laisse penser de manière commune.

La «République des Lettres», de la Renaissance au Siècle des Lumières, constitue un exemple de réseau social bien étudié. Un espace d’échanges épistolaire et de rencontres dans des salons et académies réunit des littéraires et des scientifiques européens autour d’idées de la diffusion de nouvelles connaissances, de nouvelles idées.

Deviennent alors éditées en italien, en allemand, en français, en anglais et en russe les premières encyclopédies. Plus de 150 érudits et savants ainsi que quatre éditeurs collaborent ainsi à l’Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers. D’Alembert et Diderot coordonnent l’édition de l’ouvrage publié en 1751. A cette même époque effervescente en matière de mouvement des personnes, des belles lettres et de partage des savoirs, Voltaire et Locke entretiennent une volumineuse correspondance. Leurs réseaux sont cartographiés (Dan Edelstein, 2010, Graphe 9).

voltaire-locke
Graphe 9 : Correspondance de Locke en bleu et de Voltaire en orange avec Palladio

Le développement rapide d’Internet, des réseaux téléphoniques et du commerce en ligne ont focalisé l’intérêt sur la question des communautés sociales, professionnelles et marchandes. Wikipédia, Google, Facebook, Twitter, Amazon, Uber, AirBnB, Meetic et d’autres deviennent des objets d’études et le graphe s’impose comme outil de représentation des données, personnes ou bien objets et produits du commerce. Les résultats d’une recherche de livres sur Amazon, ou de vidéo sur Youtube sont ainsi visualisés sous forme de graphe (Graphe 10) alors que le choix d’un item déclenche l’action d’un moteur de recommandation. Pour le théoricien des sciences de l’information Marshall McLuhan, le « message est le medium » et le « village est global ».

aws-graph
Graphe 10 : Recherche chez Amazon des livres en anglais relatifs à la visualisation des graphes. Exploration de vidéos sur YouTube. Les résultats sont présentés sous forme d’un graphe avec le framework javascript VivaGraphJS d’Andrei Kashcha. Changez de sujet à l’aide du formulaire situé en haut à gauche de la page.

4. Biologie

Terminons ce rapide tour d’horizon des graphes et de quelques unes de leurs applications par un mot de biologie. Des graphes sont utilisés pour modéliser le fonctionnement de différents appareils et systèmes chez l’homme comme l’appareil circulatoire, respiratoire, urinaire ou le squelette. Structurés en plaques tournantes modulaires, des réseaux de neurones transmettent un flux nerveux à la base de la pensée, de la communication et des mouvements moteurs. En biologie moléculaire, les interactions entre protéines peuvent encore être décrites à l’aide de graphes, avec des outils tels que Gene Cloud par exemple. Des maladies infectieuses se propagent en suivant les logiques des réseaux sociaux (Basileu 2012). Du côté de l’évolution des espèces, Darwin imagine dès 1837 le cladogramme (Graphe 11), objet principal de la cladistique et de la phylogénie en biologie. 

darwin-1837
Graphe 11 : « Transmutation Notebook B » – « I think », juillet 1837, Darwin, Archives de Cambridge

5. Art et symbolique

Pour l’amateur de philosophie antique romaine, Janus est le dieu des passages et des portes. Une sculpture à deux visages fixe simultanément deux directions opposées et orne les portes et passages romains. La divinité aux double visage préside aux commencements et aux fins, aux choix et au temps. Janus est invoqué lors des naissances et des échanges et se trouve fréquemment associé à Portunus, dieu des portes et des ports dont l’attribut est la clé. Le citoyen antique fait appel à cette autre divinité mineure lors des transactions commerciales, des voyages et des embarquements.

Les symboliques véhiculées par les graphes s’avèrent multiples. Des concepts colorés comme le lien, le voyage, le pont, la porte, le passage, la gare évoquent les éléments d’un graphe. Des nœuds disposés en cercle peuvent symboliser l’égalité, l’unité, comme le propose le plasticien du numérique Christopher Baker (Graphe 12).

De nombreux types d’arbres, de buissons, de réseaux et de cycles sont évoqués dans des textes religieux (Torrens, 2013). La symbolique des réseaux apparaît également vaste et ancienne (Musso 1999). Arbres et cycles représentent deux types de graphes distincts qui décrivent des relations se jouant de l’espace et du temps, dans la partie et le tout. Du graphe au graphisme (Peinture 1) pour en terminer, il n’y a que trois lettres, mais qui nous éloignent un peu trop du sujet de ce billet.

mymap_daterange
Graphe 12 : Réseau d’échange de mails par Christopher Baker (plasticien du numérique), 2007
jan_vermeer_van_delft_011
Peinture 1 : L’Art de la peinture par Vermeer. Le peintre peint sa fille costumée en muse dans une œuvre aux symboliques à la fois personnelles et politiques : Lien

Conclusion

Retracer des passés oubliés, optimiser des trajets, concevoir des objets, organiser des connaissances, envisager des possibles, faciliter des recherches : voilà le genre de choses pour lesquelles penser, dessiner ou se laisser guider par un graphe semble bienvenu. A l’artisan de trouver une représentation efficace et plaisante. Pour tracer de beaux arbres, de jolis cycles et de magnifiques réseaux quelques outils bien affûtés s’avèrent nécessaires, un soupçon de théorie, une pointe de scepticisme envers les données, la pratique d’outils adaptés.

Côté informatique et plus particulièrement de javascript, le web rend aisément accessible de nombreux langages informatiques et logiciels spécialisés dans la représentation des graphes, des réseaux et des cycles. Graphviz, Gephi, Cytoscape, langage R ou vis.js peuvent être cités. Des frameworks javascript tels que VivaGraphJS, D3.js ou SigmaJS se distinguent. Basé sur Node.js et D3.js notamment, le service web Palladio intéressera sans doute les historiens amateurs de numérique.

Des sociétés telles que Linkurious, Elastic (Graph) ou Amazon (Neptune) proposent des produits adaptés aux données volumineuses. Des forces de répulsion concurrentes des liens donnent à un réseau une forme et un comportement quelque peu analogue à ce qui peut être observé dans le vivant (Graphe 13, cliquer le lien). Certains modèles s’avèrent remarquablement précis, comme si la nature obéissait aux mathématiques, alors que celles-ci ne sont que des paquets de conventions élaborées pour tenter de la comprendre. 

hb-blckhole
Graphe 13 : Un réseau dynamique simulant les propriétés physiques d’un organisme. Graphe HB/blckhole (2121 noeuds, 6370 arêtes) d’après Andrei Kashcha, avec ViviGraphJS. http://www.yasiv.com/graphs#HB/blckhole

Webographie

Un peu de technique

2 commentaires

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s