Qu'est-ce que la théorie des graphes ?

En effet, la modélisation par la théorie des graphes est très efficace pour analyser les problèmes qui mettent en scène des ensembles d'entités entre lesquelles il existe des liens. On peut se demander quelle est la définition de la théorie des graphes et comment elle intervient dans la résolution des problèmes du Big data. On peut voir comment effectuer une formation data pour connaître cette théorie.

Théorie des graphes : définition

La théorie des graphes est une discipline mathématique et informatique. Elle s'occupe de l'étude des graphes. Elle a été créée par le mathématicien suisse Leonhard Euler en 1774 et permet de travailler sur les relations entre les données.

Le graphe est défini comme une collection d'éléments qui sont mis en relation entre eux. Leur représentation géométrique se fait à travers des modèles constitués par des points (appelés encore sommets ou nœuds) reliés par des lignes de courbes (appelée aussi arêtes, liens ou flèches). Les arêtes peuvent être non symétriques et sont alors considérées comme des flèches ou des arcs. Quand on choisit de les orienter et/ou leur attribuer un poids, les graphes sont dits orientés ou pondérés.

La théorie des graphes étudie alors les nombreuses propriétés de ces représentations. Il s'agit de l'existence de chemins les plus courts, les chemins les moins coûteux, le nombre d'intersections dans le plan, les problèmes de coloriage, les cycles particuliers, etc.

‍

Pourquoi l'utiliser en dehors de l'univers mathématique ?

La Data Science est aussi une discipline mathématique. La théorie des graphes étudie les relations qui existent entre les éléments précis. Son intégration dans le traitement des informations du Big Data est donc très intéressante.

Elle permet d'analyser les données plus rapidement, pour par exemple appliquer des contre-mesures immédiates en cas de fraude ou identifier des anomalies dans les données qui seraient passées inaperçues.

Une étude classique des données consiste à les présenter sous la forme de tableau, d'une matrice adjacente. Avec un système de base de données traditionnel (qui n'utilise pas de graphe natif), on va devoir croiser l'ensemble des données des lignes et des colonnes. Cela permet de relever les connexions avant l'algorithme métier correspondant à la mission du Data Scientist, et cela avant chaque appel de l'algorithme en question.

En ajoutant une donnée supplémentaire, le système traditionnel implique aussi l'intégration d'une colonne et d'une ligne à la matrice pour rendre possible cette analyse croisée. Dans la pratique, le volume de données à traiter est exponentiel avec le fonctionnement traditionnel. Le volume de données devient rapidement gigantesque, même si elles appartiennent à un sous-ensemble des données métiers plus modestes. Pour résoudre le problème de temps de calcul, le professionnel de la data va devoir sélectionner les données à analyser. Il ne faut pas bloquer le système ou impliquer des temps de traitement trop longs avec des résultats obtenus seulement une fois la fraude réalisée.

En utilisant la théorie des graphes, la donnée est directement représentée par un « nœud », sans avoir à générer des doublons inutiles et encombrants. Pour ajouter une donnée dans un graphe, on n'aura pas besoin de multiplier la taille de la base de façon exponentielle. Cela permet au Data Scientist de traiter toutes les données qui lui sont utiles sans limiter les performances de son système d'analyse. Pour faire plus simple, la théorie des graphes est un principe mathématique très ancien.

Son intégration aux technologies disponibles aujourd'hui permet d'améliorer le travail en data science et de faciliter la tâche aux professionnels de ce secteur.

Elle n'a donc pas pour intérêt de remplacer les outils du Data Scientist, mais de les compléter grâce à l'utilisation des analyses connectée, contextuelle et en temps réel.

Comment fonctionne-t-elle schématiquement ?

De façon générale, la notion de graphe en mathématique renvoie à une opération d'application qui possède deux acceptions à savoir :

• Le graphe d'une fonction ;
• Un objet qui représente la relation binaire existant entre les éléments d'un ensemble (hypergraphe pour des relations entre plusieurs éléments).

La théorie des graphes fait recours à la deuxième définition. Schématiquement, le graphe dispose de sommets (appelés aussi nœuds) et d'arêtes (ou arc). Une arête permet de relier deux sommets entre eux : un sommet de départ et un sommet d'arrivée.

Sur une figure, les sommets pourront être représentés par des points (ou des cercles) et les arcs par des lignes de courbe ou des flèches.

On distingue plusieurs types de représentations graphiques. Le Data Scientist se doit de comprendre le type de graphique avec lequel il travaille lorsqu'il résout par programmation un problème qui demande l'utilisation de la théorie des graphes.

‍

Graphes non orientés

Les graphes non orientés sont ceux qui ne spécifient aucune direction fixe entre les nœuds. Dans ce cas, une arête du nœud A à B serait identique à l'arête de B à A. Ce type de graphe peut servir à représenter par chaque nœud une destination fixe, et par les arêtes les routes bidirectionnelles pour les atteindre.

Graphes orientés

Les graphes orientés permettent de visualiser une orientation ou une direction entre les différents nœuds. Cela veut dire que lorsqu'une arête (représenté ici par une flèche) qui un nœud A vers un nœud B, on ne pourra se déplacer que de A vers B. L'inverse sera possible seulement si une seconde flèche qui B pour A.

En utilisant toujours l'exemple avec les destinations, on peut obtenir une direction d'une ville A vers une ville B. Cela traduit le fait qu'on peut conduire de la ville A à B, mais pas revenir à la ville A, lorsqu'il n'y a pas d'indication sur un chemin menant de B à A.

Graphiques pondérés.

Les graphiques pondérés ont des arêtes contenant un poids associé et qui représente une implication du monde réel. Ce type de graphique peut être orienté ou non orienté.

Dans l'exemple avec les destinations, cette nouvelle variable peut être le coût du transport d'une ville à une autre, le temps de trajet, ou encore la distance, selon les données traitées. Les graphiques pondérés seront ainsi souvent utilisés dans la programmation des GPS et les moteurs de recherche. Ils servent à la planification de voyage et proposent des comparaisons entre les temps et les coûts de vol.

Devenir un professionnel de la data requiert donc la maîtrise de toutes ces notions de base qui interviennent dans le traitement de données. Suivre une formation sur la théorie des graphes devient pratiquement indispensable pour le Data Scientist. Cela fait le plus souvent partie des enseignements de notre formation en Data Analysis, qu'il s'agisse d'un cursus académique classique ou de cours pratique de type bootcamp.

‍

Quels métiers l'utilisent et comment s'y former ?

La théorie des graphes peut servir à la modélisation des relations et des processus au sein des systèmes d'information, des systèmes physiques, biologiques ou encore sociaux. La formation sur la théorie des graphes est importante, car les graphiques possèdent un large éventail d'applications utiles :

• Les cartes GPS/Google pour s'orienter et retrouver le chemin le plus court vers sa destination ;
• En chimie pour l'étude des molécules et des atomes ;
• Le séquençage ADN en biologie,
• Retrouver des communautés dans les réseaux (recommandations d'amis/de connexion dans les médias sociaux) ;
• Le classement de liens hypertexte dans les moteurs de recherches ;
• La sécurité des réseaux informatiques, etc.

Il est donc primordial de passer par une formation data afin de pouvoir maîtriser la théorie des graphes. Que ce soit en présentiel ou en ligne, un futur Data Scientist pourra parfaire ses connaissances. Il saura ainsi employer la théorie des graphes de la meilleure manière qui soit dans plusieurs cas d'usage.

Dans quels use cases la retrouve-ton ?

Les bases de données graphiques sont très efficaces pour analyser les interconnexions. C'est pour cela que l'utilisation de la théorie des graphes dans l'extraction des données des médias sociaux a un grand intérêt.

Son application permet par exemple de décrire chaque utilisateur sous forme de nœud, alors que les informations qu'ils s'échangent entre eux sont représentées sous forme de liens. Les modèles d'algorithmes conçus à partir de cette théorie permettent ainsi de découvrir le chemin le plus court entre les nœuds par rapport à un thème éditorial ou un type d'interaction bien précis, servant donc l'identification de sous-communautés sociales, plus denses selon ce que l'on recherche.

Le fait de mesurer la distance qui existe entre les nœuds permet de générer des modèles multidimensionnels qui révèlent ce qui caractérise un utilisateur particulier.

Les modèles se basant sur ce principe ont été largement utilisés dans l'univers informatique au cours de ces dernières années. Aujourd'hui, il est par exemple facile de faire des recherches automatisées pour savoir les caractéristiques importantes d'une communauté qui s'intéresse par exemple aux jeux de hasard, au football, ou au tourisme dans un pays donné.

Ce sont des informations pertinentes qui intéressent en première position les chefs d'entreprises dans l'univers du marketing. Elles sont de plus en plus mises en œuvre par les outils de Machine Learning. Les entreprises exploitent ces données pour développer des campagnes marketing adaptées à leurs cibles dont ils connaissent déjà les principales caractéristiques.

Dans le commerce en ligne, les bases de données graphiques interviennent aussi dans le traitement des données. C'est un domaine qui implique des relations complexes et un schéma dynamique, tel que la gestion des chaînes d'approvisionnement, l'identification de la source d'un problème, et plus particulièrement dans la création de recommandations (les clients qui ont acheté ce produit ont aussi regardé…). Ce sont là quelques-unes des applications les plus évidentes de la théorie des graphes dans le traitement de données.

La Data Science étant également une discipline mathématique, il est tout à fait normal qu'elle exploite ses propriétés pour arriver à ses fins. Voilà pourquoi il est important de passer par une formation sur la théorie des graphes afin d'en exploiter tout son potentiel.

‍