Algorithmes de graphes pour la détection d'arbitrage : de Bellman-Ford à RICH

Partie 1 de la série « Chaînes d'arbitrage complexes entre futures et spot »

Imaginez le marché des cryptomonnaies comme un organisme vivant où des milliers de prix changent chaque seconde sur des centaines d'exchanges. Dans ce chaos apparaissent des écarts de prix temporaires — des « inefficiences » — qui permettent de réaliser un profit sans risque. C'est l'arbitrage. Mais nous ne parlons pas de simples échanges en deux étapes. Nous plongeons dans des chaînes complexes multi-actifs où un profit ne peut être trouvé qu'en passant du BTC à l'ETH, puis au SOL, puis à l'USDT, et enfin de retour au BTC.

Comment trouver ces chaînes parmi des millions de possibilités en temps réel ? La réponse réside dans la théorie des graphes.

Dans cet article, nous parcourrons le chemin qui va des algorithmes classiques jusqu'aux recherches académiques les plus récentes, en implémentant le tout en Rust pour une performance maximale.

Une visualisation high-tech d'un graphe d'arbitrage : les nœuds représentent des actifs, et les arêtes représentent des paires de trading. Un cycle mis en évidence représente une opportunité rentable détectée.

1. Le marché comme graphe

Pour appliquer des algorithmes de graphes, nous devons d'abord représenter le marché correctement.

1.1 Sommets et arêtes

• Sommets (nœuds) : Actifs (BTC, ETH, USDT, etc.).
• Arêtes (liens) : Paires de trading (BTC/USDT, ETH/BTC).
• Poids : Le taux de change.

Si nous avons un taux $R(i, j)$ (combien de l'actif $j$ nous obtenons pour 1 unité de l'actif $i$), une opportunité d'arbitrage existe si un cycle $(i_1, i_2, \dots, i_k, i_1)$ produit : $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 De la multiplication à l'addition

Les ordinateurs sont bien plus rapides pour additionner que pour multiplier, et la plupart des algorithmes de plus court chemin sont conçus pour des sommes. Nous utilisons une astuce mathématique simple : le logarithme. Puisque $\ln(a \times b) = \ln(a) + \ln(b)$, la condition devient : $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Ou, en inversant le signe pour trouver un cycle négatif : $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Désormais, chaque arête a un poids $w = -\ln(R)$. Notre tâche consiste à trouver un cycle dont le poids total est négatif.

2. Approche classique : Bellman-Ford

L'algorithme de Bellman-Ford est le « Hello World » de la détection d'arbitrage. Il est conçu pour trouver les plus courts chemins et peut naturellement détecter les cycles négatifs.

2.1 L'algorithme en Rust

En utilisant le crate petgraph, nous pouvons l'implémenter efficacement :

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::bellman_ford;

fn find_arbitrage_bellman_ford(
    graph: &DiGraph<&str, f64>, 
    start_node: NodeIndex
) -> Option<Vec<NodeIndex>> {
    // Bellman-Ford returns distances or an error if a negative cycle is found
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // No negative cycles
        Err(error) => {
            // In a real implementation, we would reconstruct the cycle 
            // using the predecessor map from the error
            println!("Arbitrage detected!");
            None 
        }
    }
}

2.2 Complexité et limites

Bellman-Ford s'exécute en $O(V \times E)$, où $V$ est le nombre d'actifs et $E$ le nombre de paires de trading.

• Avantages : Garantit de trouver un cycle s'il en existe un.
• Inconvénients : Trop lent pour le trading haute fréquence (HFT) lorsque le nombre d'actifs augmente. Il ne trouve également qu'un seul cycle à la fois.

3. SPFA : une alternative plus rapide

Le Shortest Path Faster Algorithm (SPFA) est une version optimisée de Bellman-Ford qui utilise une file d'attente pour éviter les calculs redondants.

use std::collections::VecDeque;

fn spfa_negative_cycle(n: usize, adj: &Vec<Vec<(usize, f64)>>) -> bool {
    let mut dist = vec![0.0; n];
    let mut count = vec![0; n];
    let mut in_queue = vec![false; n];
    let mut queue = VecDeque::new();

    for i in 0..n {
        in_queue[i] = true;
        queue.push_back(i);
    }

    while let Some(u) = queue.pop_front() {
        in_queue[u] = false;
        for &(v, weight) in &adj[u] {
            if dist[v] > dist[u] + weight {
                dist[v] = dist[u] + weight;
                count[v] = count[u] + 1;
                if count[v] >= n {
                    return true; // Negative cycle detected
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

En pratique, SPFA s'exécute souvent en $O(k \times E)$ où $k \ll V$, ce qui le rend beaucoup plus rapide pour les graphes de marché épars.

4. Recherche moderne : l'algorithme RICH

En 2024, des chercheurs ont proposé l'algorithme RICH (Rapid Identification of Cyclic High-profitability). Contrairement à Bellman-Ford, RICH est spécifiquement optimisé pour les graphes financiers où :

1. Le graphe est de taille petite à moyenne (des centaines d'actifs).
2. Les poids changent toutes les millisecondes.
3. Nous devons trouver le cycle le plus rentable, et pas seulement un cycle quelconque.

4.1 Innovations clés de RICH

• Élagage (Pruning) : Il élimine immédiatement les chemins qui ne peuvent en aucun cas mener à un cycle rentable, en se basant sur le meilleur chemin actuellement connu.
• Recherche par couches : Il recherche des cycles de longueur croissante (3, 4, 5 étapes) à l'aide d'optimisations par masques de bits.
• Mises à jour incrémentales : Plutôt que de relancer l'algorithme complet, il ne met à jour que les parties du graphe affectées par un changement de prix.

5. Défis d'implémentation : frais et liquidité

Le trading réel n'est pas gratuit. Un cycle à plusieurs étapes $(A \to B \to C \to A)$ entraîne trois frais de transaction distincts.

5.1 Intégration des frais

Nous devons ajuster les poids de nos arêtes : $w = -\ln(R \times (1 - \text{fee}))$ Cela élague considérablement le graphe, car de nombreux cycles théoriques sont annulés par le coût d'exécution.

5.2 Liquidité et slippage

Plus vous achetez d'un actif, plus le prix monte (slippage). Un cycle qui semble rentable pour 100 $peut être une perte pour 10 000$. Les modèles de graphes avancés utilisent des poids paramétriques, où $w$ est une fonction du volume $V$. Cela transforme le problème d'une simple recherche de plus court chemin en un problème d'optimisation convexe sur un graphe.

6. Pourquoi Rust ?

Dans le monde de l'arbitrage, 100 microsecondes font la différence entre un profit et une opportunité « manquée ».

• Sécurité mémoire : Pas de pauses du ramasse-miettes (GC) qui pourraient figer le bot à un moment critique.
• Abstractions à coût nul : Nous pouvons utiliser des structures de graphes de haut niveau sans perdre la performance des pointeurs bruts.
• Concurrence : La « Fearless Concurrency » de Rust nous permet d'analyser en parallèle les flux WebSocket de 10 exchanges et de mettre à jour le graphe partagé en toute sécurité.

Conclusion

Les algorithmes de graphes constituent le moteur de l'arbitrage crypto moderne. Alors que Bellman-Ford pose les bases, les systèmes modernes utilisent des variantes optimisées comme SPFA ou des algorithmes spécialisés comme RICH.

Dans la prochaine partie de cette série, nous examinerons l'arbitrage futures-spot, où nous étendrons notre graphe des simples échanges d'actifs pour inclure les taux de financement (funding rates) et les stratégies cash-and-carry.

Vous construisez des systèmes de trading à faible latence ? Consultez notre modèle Rust HFT open source.