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 être géolocalisé par exemple (Graphe 1, Graphe 2). Il peut être mobile comme un piéton se déplaçant sur un chemin.

Maillage
Graphe 1 : Réseau géodésique français 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 réel ou imaginaire. Pour le mathématicien, les arbres, les chaînes, les réseaux et les cycles sont des sortes de graphes. Euler propose dès 1735 une étude pour décrire 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 ou encore d’une table de données. 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. 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 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 liées aux 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). Des réseaux distincts sont susceptibles de montrer des dynamiques, de cohabiter, coopérer, fusionner ou bien 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 de cinq disciplines 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 une mémoire. 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. Des formats tels que HTML, XML, TEI ou JSON fournissent une organisation de l’information en arbre binaire dans laquelle des marqueurs 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.

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

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).

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 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és dans un triple store ou dans une base de donnée orientée graphe. Des ressources externes peuvent être considérées. Des ontologies écrites en OWL (Langage d’ontologie du web) formalisent la nature des nœuds (sujet ou objet) et des arêtes (prédicats), spécifient des classes et des propriétés. Le web sémantique devient alors complémentaire des traditionnels moteurs de recherche, introduisant des syntaxes d’interrogation spécialisées.

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 émotions, des langages, des lieux, des routines, des modes de vie et des événements, bref des cultures. Quelques réseaux classiquement étudiés par les historiens des sciences s’avèrent emblématiques. La «République des Lettres», de la Renaissance au Siècle des Lumières, constitue un exemple très classique de réseau social. 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.

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

Sont éditées alors 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 et de partage des savoirs, Voltaire et Locke entretiennent une volumineuse correspondance. Leurs réseaux sont cartographiés (Dan Edelstein, 2010, Graphe 9).

De manière expérimentale, Moreno propose en 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). En 1967,  le psychosociologue Milgram élabore 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 de relations interpersonnelles limité, 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 laissait penser. 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 et l’animal comme l’appareil circulatoire, respiratoire, urinaire ou le squelette. Transitant par des 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. Les interactions entre protéines peuvent encore être décrites à l’aide de graphes, à l’aide de services web tels que Gene Cloud par exemple. Des maladies infectieuses se propagent en suivant les logiques des réseaux sociaux (Basileu 2012). Darwin confronté à l’évolution dans le temps des espèces imagine dès 1837 le cladogramme (Graphe 11), objet principal de la cladistique et de la phylogénie. 

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 fixant simultanément deux directions opposées orne les portes et passages romains. Janus préside aux commencements et aux fins, aux choix et au temps. En tant que dieu des transitions, il est invoqué lors des naissances et des échanges. Il se trouve fréquemment associé à Portunus, dieu des portes et des ports dont l’attribut est la clé. Le citoyen antique fait appel à ce dieu mineur lors des transactions commerciales, des voyages et des embarquements.

Lorsque nous dessinons, ou bien lors de l’écriture, que faisons nous sinon tracer des graphes qui voyagent pour former un message ? 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, il n’y a que trois lettres…

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 multiples : 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 méritent d’être signalés. Basé sur Node.js et D3.js notamment, le service web Palladio intéressera sans doute certains historiens.

Des sociétés telles que Linkurious, Elastic (Graph) ou Amazon (Neptune) proposent des produits adaptés à des données volumineuses. Des forces de répulsion concurrentes des liens donnent à un réseau une forme et un comportement 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 qu’une sorte de langage élaboré pour tenter de la comprendre. 

hb-blckhole
Graphe 13 : Graphe HB/blckhole (2121 noeuds, 6370 arêtes) d’après Andrei Kashcha, avec ViviGraphJS. http://www.yasiv.com/graphs#HB/blckhole

Webographie

Pour les curieux

Bonus

Les services web rendent possible la manipulation des données, la création d’images de graphes et le test de bibliothèques javascripts à l’aide d’un simple navigateur.

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