L’omniprésence des graphes

On peut dire qu’au moins qu’une problématique de datascience sur deux peut se traiter à l’aide d’un graphe. Il peut s’agir d’un arbre de décision, d’un graphe d’induction, d’une ontologie, etc. Les graphes offrent une grande variété de formes et de types dont l’approche sera mathématiquement très différente. De fait les algorithmes de graphe constituent une dimension incontournable que doit maitriser tout bon datascientist.

Selon wikipedia (extraits) :

  • La théorie des graphes est une théorie informatique et mathématique.
  • Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.) et dans bien d’autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d’une fonction), est général.
  • De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu’elle laisse ouvertes, comme la conjecture d’Hadwiger, en font une branche vivace des mathématiques discrètes.

Plus simplement, un graphe est un ensemble de points appelés indifféremment « nœuds » ou « sommets » et de liens entre ces points appelés indifféremment « arcs », « segments » ou « arêtes ». Les arcs peuvent être orientés ou non.

Typologie des graphes

La typologie des graphes est fonction de leur structuration

  • Réguliers : les sommets et les arrêtes reproduisent un schéma régulier.
  • Arborescents ou hiérarchiques : il y a des nœuds parents et des nœuds enfants, un enfant ne peut avoir qu’un seul parent
  • Cycliques : certains chemins sont circulaires.
  • Polaires ou multipolaires : de nombreux nœuds sont rattachés directement à quelques nœuds appelés pôles.
  • Non-structurés : sans topologie remarquable.

Il existe deux grandes familles de graphes :

  • Les graphes homogènes dont les nœuds sont tous de même nature
  • Les graphes hétérogènes ou les nœuds sont de natures différentes. Ces graphes peuvent former des couches dans lesquelles le graphe est localement homogène

Les études menées en mathématique et en informatique et les algorithmes élaborés ne couvrent qu’une partie de la première famille. Les problématiques liées aux graphes homogènes telles que les optimisations, les parcours des graphes sont réputées mathématiquement difficiles (problèmes NP-complets par exemple) ce qui explique que le domaine des graphes homogènes ne soit que partiellement couvert et que celui des graphes hétérogènes soit à peine entamé.

Les graphes réguliers ont été particulièrement étudiés mais n’ont que très peu d’applications pratiques. Les graphes arborescents sont relativement simples à exploiter. Les graphes cycliques posent des problèmes de parcours nécessitant généralement des approches systémiques. Les graphes polaires ont des applications concrètes dans les réseaux et dans la sociologie et ont été de fait exploités par les réseaux sociaux ou l’urbanisme.

Les arbres sont des graphes d’un type relativement simple. On les trouve notamment dans les arbres de décision, les arbres de remontée de panne, etc… Mais contrairement à leur nom, les arbres généalogiques ne sont pas des arbres (un enfant n’a pas un unique parent), sauf si l’on restreint l’arbre à la lignée mâle par exemple.

Les problématiques des graphes

Certaines problématiques complexes ont été particulièrement étudiées. Parmi celles-ci on trouve la coloration des graphes. Il s’agit d’affecter une couleur à chaque nœud de telle sorte que deux nœuds reliés entre eux ne soient pas de la même couleur. Si cette problématique est mathématiquement intéressante et a capté l’attention de nombreux chercheurs, elle ne trouve que relativement peu d’applications concrètes.

Les problématiques rencontrées dans le monde réel concernent principalement la réduction des graphes, la répartition de la charge des graphes, la polarisation des graphes et le parcours des graphes. Les graphes auxquels nous avons à faire sont généralement des graphes non homogènes, non structurés, présentant des cycles et des pôles locaux.

La problématique liée à la réduction des graphes consiste à produire un graphe équivalent disposant de moins d’arcs. Cette problématique se rencontre dans les réseaux notamment. Comment optimiser le nombre de points de raccordement de mon réseau de gaz pour diminuer le cout de l’installation et de la maintenance par exemple.

La problématique de répartition de la charge des graphes consiste à rechercher un graphe équivalent dans lequel les coefficients affectés aux arcs soient dans des intervalles de valeurs plus resserrées. Comment équilibrer la charge de mon réseau de distribution de l’électricité pour satisfaire les besoins évolutifs des consommateurs par exemple.

La problématique de polarisation de graphe consiste à remplacer le graphe par un graphe polaire équivalent. En formant des « grappes » on peut optimiser le réseau internet, par exemple en utilisant des gros tuyaux entre des pôles puis des ramifications vers les points de raccordement individuels.

La problématique de parcours des graphes consiste à rechercher le meilleur chemin entre deux nœuds. Par exemple pour optimiser le transport pour une société de logistique ou au contraire pour allonger la visite d’un client dans un centre commercial.

Les forêts de graphes

Même si le principe constitutif des graphes (nœuds et arcs) parait simple, manipuler un graphe relève de techniques complexes. La problématique se renforce encore lorsque le graphe peut se présenter sous plusieurs instances. On parle alors de forêts de graphes (généralisation du terme forêt d’arbres utilisés initialement pour les graphes arborescents).

Plusieurs approches aboutissent à la constitution d’une forêt de graphe. Par exemple lorsque les arcs sont de natures différentes. Dans le cas d’un graphe de connexions entre des villes, on peut former le réseau d’eau, celui du gaz, celui de l’électricité, du téléphone, des routes, etc… ceci constitue une forêt. On ne peut pas raisonner sur un seul des graphes car il existe des interrelations entre ces graphes.

Un autre cas concerne des instances grégaires. Par exemple dans les réseaux sociaux les personnes sont connectées entre elles pour certains sujets (profession, cinéma, sport, …). Des liens peuvent exister entre deux personnes dans plusieurs graphes (par exemple personnel et professionnel).

Les graphes nexialistes

Les graphes nexialistes représentent les connexités existant entre plusieurs éléments. Par exemple la connexité entre des produits d’un magasin (un PC et un câble), (une imprimante et une cartouche d’encre) et de façon moins universelle : (une chemise et une cravate assorties selon certaines modes).

Ces graphes sont généralement produits par apprentissage, par exemple sur les expériences de consommation. Dans ce cas l’algorithme d’apprentissage doit également respecter les règles de construction des graphes ce qui rajoute à la complexité naturelle d’un algorithme d’apprentissage.

Les graphes nexialistes se présentent souvent sous forme de forêts de graphes car les connexités sont généralement typées et multiples.

Des graphes nexialistes pour représenter les images mentales

Une des problématiques que l’on peut rencontrer en datascience différentiative est de représenter toutes les images mentales que se font des individus d’un même objet, à partir desquelles il sera possible de fournir une réponse personnalisée. Ce peut être, par exemple le cas de l’organisation d’un magasin dans la grande distribution, ou celui de l’image que se font des étudiants des métiers dans le cadre de l’orientation scolaire, pour ne citer que ces cas.

Dans le premier cas, chaque consommateur organise son parcours dans son magasin favori en fonction de son image mentale du magasin. Certains commenceront par les vêtements car ils sont compulsifs sur ces articles. D’autres termineront par les vêtements pour ne pas les salir. D’autres n’auront pas conscience que l’on peut acheter des vêtements dans ce magasin. Le graphe peut se construire au fur et à mesure des observations de parcours dans le magasin.

En orientation scolaire, le graphe décrira les motivations des élèves qui considèrent que certains métiers sont proches parce qu’ils partagent une caractéristique à laquelle d’autres ne seront pas sensibles, lesquels les trouveront de fait très éloignés.

L’image mentale est également impactée par la psychologie de l’individu. Par exemple certains consommateurs catégorisent plus facilement les produits selon les marques, selon les usages, selon les gammes de prix, etc. Certains étudiants catégorisent les métiers selon le salaire, la mobilité, les horaires, etc. Si l’on voulait pousser le principe à l’extrême, il faudrait créer un graphe par individu, nous disposerions alors d’une image complète de son champ de conscience pour les produits ou les métiers du catalogue. Dans la pratique une forêt de graphes établis pour des classes d’individus est généralement suffisante.

Cette approche de matérialisation des images mentales sous forme de graphe est applicable à tous les domaines ou des individus sont en contact avec des objets ou des sujets. Le graphe de par ses règles de construction apporte une grande cohérence à la manipulation de données très variées.

Les conseillers exploitent aussi des graphes nexialistes sans le savoir

Le conseiller dans un magasin procède toujours de la même façon :

  • Il repère la catégorisation que fait le consommateur, sa sensibilité (marque, usage, matière, etc…)
  • Il l’oriente dans un rayon où il prend soin d’occulter certains produits voisins pour concentrer le consommateur sur ceux directement liés à sa situation et à son comportement.
  • Il argumente. C’est ici que le consommateur mesure le « service » rendu par le conseiller
  • Il propose une sélection. C’est sur ce panel restreint que le consommateur fait son choix.

Le conseiller d’orientation procède aussi de cette façon en argumentant en fonction de sa perception de l’intérêt et des possibilités de l’élève. Ce faisant les conseillers exploitent des graphes des images mentales des individus concernés d’autant plus riches que leur expérience est plus grande.

Un data-intelligence system construit autour d’une machine apprenante exploitant un tel graphe permettra après une période d’apprentissage, de conduire des recommandations, des prédictions, de lancer des alertes, au même titre que le fait un conseiller après une période de formation.

Mieux, les treillis (graphes dotés d’au moins une relation d’ordre) présentent une performance accrue lors des opérations d’exploration, la recherche pouvant être abandonnées dès que l’inéquation devient fausse. En procédant par encadrement la performance est décuplée.

Notre avenir se dessine autour des graphes et treillis nexialistes, il est important de particulièrement bien maitriser les techniques de construction et de manipulation de ces objets. De nombreux algorithmes verront le jour à l’avenir, fruit de nos brillants chercheurs, tant ces explorations s’avèrent indispensables et ce domaine en plein essor.

Jean Pierre MALLE