Grands graphes en ocamlgraph.

Objectifs

Le projet Argos [1] cherche à construire des outils d'analyse et de traçabilité de blockchains [2]. Ces analyses des flux transactionnels nécessitent de construire le graphe des transactions à partir des adresses que l'on désire tracer. Ce graphe peut être de très grande taille selon la qualité du regroupement des adresses. Pour construire de tels graphes et les manipuler dans des langages de programmation, il est nécessaire d'adaptater les biliothèques standards sur les graphes. On s'intéresse ici au langage OCaml et à la bibliothèque ocamlgraph [3] pour laquelle il sera intéressant de proposer des représentations pour des grands graphes. Une des questions importantes est de voir comment de tels graphes peuvent-ils être manipulés dans le tas OCaml ou faut-i en sont les limites pour prévoir un nouveau mécanisme dans ces cas-là, en particulier avec le clustering d'adresses.

L'objectif de ce stage est de comprendre comment adapter la bibliothèque ocamlgraph pour la création et la manipulation de grands graphes et s'en servir dans le cadre de grands graphes issus des transactions de blockchains.

Tâches à réaliser

Deux premières tâches sont à réaliser en parallèle : d'une part prendre en main et mesurer les limites de taillle de graphe de la bibliothèque ocamlgraph et d'autre part de comprendre comment construire certains graphes des comportements décrits dans [4] sur la traçabilité de blockchains. Ensuite la bibliothèque ocamlgraph pourra être étendue pour traiter ces derniers en mesurant l'efficacité dans la recherche de motifs sur de tels grands graphes.

Prérequis

• bonne connaissance de prgrammation en OCaml
• connaissance de l'algorithmique sur les graphes
• la connaissance des mécanisme des blockchains est un plus

Références

1. Functori. Introduction to Argos. https://www.functori.com/blog/introduction-to-argos.html. 2024.
2. cours sur les blockchains - M2 STL - 2021/2022.
3. bibliothèque ocamlgraph. https://github.com/backtracking/ocamlgraph/tree/master.
4. Traçabilité des blockchains - Sylvain Conchon - Université Paris Saclay - 2025.

Le stagiaire devra être d'accord pour que ses contributions soient distribuées sous licence libre.

Contacts : Antoine Genitrini & Emmanuel Chailloux & Boubacar Sall