“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).
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 le réel et tenter d’en prédire certains comportements. 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 individu, 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, un lien hypertexte, une relation entre champs de tables dans une base de données. 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 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 l’arbre utilisé pour l’enseignement du secourisme (Graphe 3), la chaîne de production mise en place dans le cadre d’une fabrication automobile (Graphe 4), ou bien le graphe des flux de capitaux entre pays produisant des biens et les centres financiers offshore (Graphe 5). Basés sur l’expérience et la pratique, des graphes et des réseaux guident les jeux, l’apprentissage et l’action.
L’informatique
En informatique, les graphes modélisent différentes choses. Des fréquences d’horloge rythment des circuits, synchronisent l’action de composants électroniques tels que des mémoires, des circuits logiques et des réseaux de machines. Des fichiers sont stockés dans des arborescences, alors que 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 interne 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é) 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. Comme pour les expressions de langage ou les achats, certains aspects sociaux semblent régir l’usage des langages et des formats informatiques.
L’histoire des matériels et des logiciels peut être évoquée avec un graphe. Quoi de plus facile que de copier ou développer une information numérique, particulièrement si celle-ci est en accès libre. 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. Linux, espèce d’un nouveau genre en constante évolution, se différencie pour former un arbre du type cladogramme (Graphe 6).
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). Succédant aux entrées des grandes encyclopédies du XVIIIème siècle, les articles 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 historiques, géographiques (Leturcq 2016), généalogiques ou sociales. Au-delà des sciences de l’information, la gestion des savoirs concerne de nombreux domaines, incluant les bibliothèques, les musées, les disciplines académiques et l’industrie.
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 ontologies écrites en OWL (Langage d’ontologie du web) formalisent la nature des nœuds (sujet ou objet) et des arêtes (prédicats). Le web sémantique devient alors complémentaire des traditionnels moteurs de recherche, introduisant des syntaxes d’interrogation spécialisées comme SPARQL.
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, 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 et les sociologues s’avèrent emblématiques. La «République des Lettres» s’étend de la Renaissance au Siècle des Lumières. 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 diffusion de la connaissance. 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 de correspondance sont cartographiés (Dan Edelstein, 2010, Graphe 9).
Moreno propose en 1934 l’usage du sociogramme pour décrire les relations sociales entre enfants de différentes classes d’âge placés en milieu scolaire. Un graphe décrit les 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). Pour le théoricien McLuhan, en matière d’information le « message est le medium », en matière de communication le « village est global ».
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. Des maladies infectieuses se propagent en suivant les logiques des réseaux sociaux (Basileu 2012). 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. Darwin confronté à l’évolution dans le temps des espèces imagine dès 1837 le cladogramme (Graphe 11), objet principal de la cladistique.
Art et symbolique
A quoi sert le graphe ? Tout comme le dessin, l’écriture ou une équation mathématique, le graphe est susceptible de décrire le réel voire l’imaginaire et les relations qui les constituent. Les symboliques du graphe s’avèrent multiples. Des notions comme le lien, le voyage, le pont, la porte, le passage, la gare peuvent être des éléments d’un graphe. Les notions de parenté ou de distinction, de relation, de mouvement sont alors mis en évidence. Des nœuds disposés en cercle peuvent symboliser l’égalité, l’unité, comme le propose Christopher Baker (Graphe 12).
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. 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 romain fait appel à ce dieu mineur lors des transactions commerciales, des voyages et des embarquements.
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) alors qu’une philosophie des réseaux intéresse certains philosophes. Arbres et cycles ne sont ils pas deux types de graphes distincts qui permettent de représenter de manières complémentaire les notions d’espace et de temps ?
Conclusion
Retracer des passés oubliés, optimiser des trajets, concevoir des objets, envisager des possibles, faciliter des recherches : voilà le genre de choses pour lesquelles penser, dessiner ou se laisser guider par un graphe est 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 sont nécessaires, un soupçon de théorie, une pointe de scepticisme envers les données, la pratique d’outils adaptés.
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 ou Cytoscape peuvent être cités. Des frameworks javascript tels que VivaGraphJS, D3.js, vis.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 outils web comme jsfiddle.net facilitent les tests de frameworks javascripts. 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 comparable à ce qui est observé dans le vivant (Graphe 13). Certains modèles s’avèrent remarquablement précis. Comme si la nature obéissait aux mathématiques, alors que celles-ci sont créées collectivement pour tenter de la comprendre.
[A suivre…]
Webographie
- Étienne Ghys, 2010, Représenter les mondes II., Mathématique : http://images.math.cnrs.fr/representer-les-mondes-ii.html
- Zeste de savoir, 2016, Graphe et représentation de graphe : https://zestedesavoir.com/tutoriels/681/a-la-decouverte-des-algorithmes-de-graphe/727_bases-de-la-theorie-des-graphes/3352_graphes-et-representation-de-graphe/
- Samuel Leturcq et Romain Raveaux, 2016, Les graphes pour étudier les dynamiques spatiales à partir des séries fiscales médiévales et modernes. Etat des lieux de l’expérience Modelespace, Histoire, Mathématique : https://cem.revues.org/13805
- Martin Grandjean, 2013, L’archive mise en réseau : la visualisation de données en sciences humaines est un moyen, pas une fin !, Histoire : http://www.martingrandjean.ch/archive-reseau-visualisation-donnes-sciences-humaines/
- Martin Grandjean, 2014, La connaissance est un réseau : perspective sur l’organisation archivistique et encyclopédique, Histoire, Théorie de la connaissance : https://halshs.archives-ouvertes.fr/halshs-01525545
- Martin Grandjean, 2014, Social network analysis and visualization: Moreno’s Sociograms revisited, Psychologie sociale, http://www.martingrandjean.ch/social-network-analysis-visualization-morenos-sociograms-revisited/
- Dan Edelstein, 2010, Mapping the Republic of Letters, Voltaire and the Enlightment : http://republicofletters.stanford.edu/casestudies/voltaire.html
- Cynthia Basileu, 2012, Modélisation structurelle des réseaux sociaux, application à un système d’aide à la décision en cas de crise sanitaire, Thèse, Mathématique, Epidémiologie, Sociologie, : https://tel.archives-ouvertes.fr/tel-00755031/document
- Erica Torrens, Ana Barahona, 2013, Darwin’s muses behind his 1859 diagram, Histoire des sciences : http://arbor.revistas.csic.es/index.php/arbor/article/view/1873/2026
- Pierre Musso, 1999, La symbolique du réseau, Quaderni, Volume 38, Numéro 1, pp. 69-98, Réseau, Symbolique : http://www.persee.fr/doc/quad_0987-1381_1999_num_38_1_1396
Pour les curieux
- En français : Collaborateurs de l’Encyclopédie, L’Encyclopédie en ligne, Étude du petit monde, Sociogramme, Cladistique, Philosophie des réseaux, Phylogénie, Arbre de décision (apprentissage), Gestion des connaissances, Neo4j, Triplestore, GraphQL, Graphviz, Gephi, D3.js, VivaGraphJS, Sigma js, Cytoscape.js, Principales bibliothèques javascript : we love graphs (anvaka), graphes dans ExpoViz, Visualisation en biologie
- En anglais : Small-world network, Graph-drawing, Force-directed graph drawing, Flow map, Data visualization, Social graph, Diagrammatic reasoning, Knowledge graph, Network theory, Network science, Tree of life, Google Network Graph, Comparison of JavaScript charting frameworks,
- People : Leonhard Euler, Charles Darwin, Paul Erdős, Jacob Levy Moreno, Stanley Milgram, Marshall McLuhan, Mike Bostock, Martin Grandjean, Etienne Come, Andrei Kashcha
- Vidéo : Gource, Evolution of sigma.js
- Génétique : Interactions moléculaire de PER1, un gène impliqué dans le rythme circadien, avec Gene Cloud
- Solutions informatiques commerciales : Neo4j, Linkurious, Elastic (Graph)
Services web
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.
- Génération de graphe avec Graphviz : webgraphviz, GraphvizOnine
- Diagramme de Sankey : Sankeymatic (D3)
- Testez vos bibliothèques javacript : jsfiddle.net, carte de liaisons aériennes (amcharts), arborescence verticale (D3), réseau social « Les Misérables » (D3)
- Pour les historiens, importez vos données dans Palladio et transformez les en cartes et graphes : Palladio (D3)
