Introduction au traitement des graphes volumineux

Les graphes sont une solution de choix pour modéliser des problèmes de la vie réelle, car ils sont intuitifs, flexibles (plus que des tables dans un SGBD relationnel), et parce que la théorie des graphes évolue depuis déjà quelques siècles. C’est la raison pour laquelle plusieurs bases de données en graphe existent, la plus connue étant sans doute Neo4j.

Un constat similaire peut s’appliquer au traitement en masse des graphes. Les algorithmes sont nombreux, bien connus et ont des applications immédiates : recherche de plus court chemin, de trajets, détection de boucles, identification de sous-graphes, ... en sont des exemples. Neo4j embarque ainsi une petite collection d’algorithmes dans le package graphalgo.

Les problèmes commencent avec le traitement de très gros graphes, de l’ordre du milliard de sommets fortement connectés. Un tel graphe ne peut être traité en une fois sur une seule machine, et le recours se trouve du côté du batch distribué sur un cluster. Un algorithme de processing typique suit les arcs du graphe, raison pour laquelle une implémentation naïve peut fortement pâtir de la communication inter-machines que suppose cette stratégie (le partitionnement optimal du graphe, sans heuristiques sur sa structure, est un problème difficile).

Dans cet article nous présentons l’algorithme BSP (Bulk-Synchronous Parallel), qui est souvent cité comme réponse possible au problème de traitement des gros graphes. Puis nous passerons en revue une liste d’outils et de frameworks dédiés à ce type de traitements, qu’ils reposent sur BSP ou sur d’autres approches.

La suite de cet article est sur la section anglophone de notre blog.