Графовые алгоритмы для обнаружения арбитража: от Bellman-Ford до RICH

Представьте: вы стоите на оживлённом восточном базаре. У одного менялы доллар стоит 90 рублей, у второго — 92. Третий предлагает евро за доллары по 0.91, а четвёртый — рубли за евро по 102. Если быстро пробежать по кругу, обменивая валюты, можно вернуться к рублям с прибылью. Теперь увеличьте масштаб: 500 криптовалют, 30 бирж, тысячи торговых пар — спот, бессрочные фьючерсы, поставочные контракты, опционы. Как найти прибыльный маршрут в этом лабиринте? Ответ скрывается в теории графов — той самой, которую Эйлер придумал, решая задачу о Кёнигсбергских мостах три века назад.

Эта статья — первая часть серии «Сложные цепочки арбитража между фьючерсами и спотом». Мы разберём, как превратить хаотичный рынок в математическую структуру, где арбитражные возможности становятся буквально видимыми. И покажем, как современные алгоритмы — от классического Bellman-Ford до революционного RICH (VLDB 2025) — позволяют находить эти возможности быстрее, чем они успевают исчезнуть.

Ключевая идея: арбитраж как отрицательный цикл

Начнём с фундамента. Арбитражная возможность существует, когда последовательность обменов, начинающаяся и заканчивающаяся одним и тем же активом, приносит прибыль. Математически это выражается просто: если у нас есть цепочка обменных курсов r1, r2, ..., rk, арбитраж существует, когда:

r1 * r2 * ... * rk > 1

Проблема в том, что большинство графовых алгоритмов работают с суммами весов, а не с произведениями. Здесь на помощь приходит элегантное логарифмическое преобразование:

weight(A -> B) = -log(rate(A -> B))

Что это даёт? После преобразования:

• Сумма весов вдоль пути эквивалентна произведению курсов
• Отрицательный цикл (сумма весов < 0) соответствует прибыльному арбитражу (произведение курсов > 1)
• Стандартные алгоритмы кратчайших путей теперь напрямую обнаруживают арбитраж

Давайте разберём это на пальцах. Если BTC/USDT = 50000 (мы можем продать 1 BTC за 50000 USDT), то вес ребра BTC -> USDT равен -log(50000) ≈ -10.82. Если ETH/BTC = 0.06, вес ребра ETH -> BTC равен -log(0.06) ≈ 2.81. Обратно: USDT -> ETH по курсу 1/3001, вес равен -log(1/3001) ≈ 8.01. Сумма по циклу: -10.82 + 8.01 + 2.81 = 0.0 — нет арбитража. Но стоит ценам чуть разойтись — и сумма станет отрицательной, сигнализируя о прибыльной возможности.

Криптовалютный рынок как ориентированный взвешенный граф: вершины — активы, рёбра — обменные курсы в логарифмическом пространстве. Отрицательный цикл (выделен красным) = арбитраж.

Учёт комиссий

Комиссии уменьшают эффективный обменный курс. С комиссией f вес ребра становится:

weight(A -> B) = -log(rate(A -> B) * (1 - f))
                = -log(rate(A -> B)) - log(1 - f)

Поскольку log(1 - f) отрицателен, комиссии добавляют положительный вес к рёбрам, делая отрицательные циклы труднее находимыми. Это корректно отражает реальность: комиссии снижают прибыльность арбитража. Для трёхногой сделки с комиссией 0.1% на каждом шагу нужно, чтобы суммарная ценовая дискрепанция превышала 0.3% — и это ещё без учёта проскальзывания.

Bellman-Ford: классика, проверенная временем

Алгоритм Bellman-Ford — основа основ для обнаружения арбитража. Он вычисляет кратчайшие пути от одного источника ко всем остальным вершинам во взвешенном ориентированном графе. Критически важное свойство: он может работать с отрицательными весами рёбер и детектирует отрицательные циклы.

Сложность: O(|V| * |E|) по времени, O(|V|) по памяти.

Алгоритм работает в два этапа. Первый — |V|-1 итераций релаксации: для каждого ребра (u, v) с весом w проверяем, можно ли улучшить расстояние до v, пройдя через u. Второй — этап детектирования: запускаем ещё одну итерацию. Если какое-то расстояние всё ещё можно улучшить — мы нашли отрицательный цикл, а значит, арбитражную возможность.

Техника виртуального суперисточника

Наивный подход — запускать Bellman-Ford от каждой вершины отдельно. Это дало бы сложность O(|V|^2 * |E|) — слишком медленно. Вместо этого используется элегантный трюк: инициализируем все расстояния нулём. Это эквивалентно добавлению виртуального суперисточника с рёбрами нулевого веса ко всем вершинам. Теперь за один проход мы обнаруживаем отрицательные циклы, достижимые из любой вершины.

Виртуальный суперисточник S соединён с каждой вершиной ребром нулевого веса. Это позволяет одним проходом Bellman-Ford обнаружить все отрицательные циклы в графе.

Реализация на Rust

use std::collections::HashMap;

#[derive(Clone, Debug)]
struct ArbitrageGraph {
    n: usize,
    adj: Vec<Vec<(usize, f64)>>,
    asset_to_idx: HashMap<String, usize>,
    idx_to_asset: Vec<String>,
}

#[derive(Debug)]
struct ArbitrageResult {
    cycle: Vec<usize>,
    profit_ratio: f64,
}

/// Обнаружение арбитража через Bellman-Ford
fn detect_arbitrage_bellman_ford(graph: &ArbitrageGraph) -> Vec<ArbitrageResult> {
    let n = graph.n;
    let mut dist = vec![0.0_f64; n];    // Виртуальный суперисточник
    let mut pred = vec![usize::MAX; n];
    let mut results = Vec::new();

    // Собираем все рёбра
    let edges: Vec<(usize, usize, f64)> = graph.adj.iter().enumerate()
        .flat_map(|(u, neighbors)| {
            neighbors.iter().map(move |&(v, w)| (u, v, w))
        })
        .collect();

    // Фаза 1: n-1 итераций релаксации
    for _ in 0..n - 1 {
        let mut updated = false;
        for &(u, v, w) in &edges {
            if dist[u] + w < dist[v] - 1e-10 {
                dist[v] = dist[u] + w;
                pred[v] = u;
                updated = true;
            }
        }
        if !updated {
            break; // Ранняя остановка: нет отрицательных циклов
        }
    }

    // Фаза 2: детектирование отрицательных циклов
    let mut on_cycle = vec![false; n];
    for &(u, v, w) in &edges {
        if dist[u] + w < dist[v] - 1e-10 {
            // Нашли вершину на отрицательном цикле
            let mut x = v;
            for _ in 0..n {
                x = pred[x];
            }

            if on_cycle[x] {
                continue;
            }

            // Извлекаем цикл
            let mut cycle = Vec::new();
            let start = x;
            let mut current = start;
            loop {
                cycle.push(current);
                on_cycle[current] = true;
                current = pred[current];
                if current == start {
                    break;
                }
            }
            cycle.reverse();

            // Считаем прибыльность
            let profit_ratio = calculate_profit_ratio(graph, &cycle);
            if profit_ratio > 1.0 {
                results.push(ArbitrageResult { cycle, profit_ratio });
            }
        }
    }

    results.sort_by(|a, b| b.profit_ratio.partial_cmp(&a.profit_ratio).unwrap());
    results
}

/// Расчёт коэффициента прибыли для цикла
fn calculate_profit_ratio(graph: &ArbitrageGraph, cycle: &[usize]) -> f64 {
    let mut total_weight = 0.0;
    for i in 0..cycle.len() {
        let from = cycle[i];
        let to = cycle[(i + 1) % cycle.len()];
        if let Some(&(_, w)) = graph.adj[from].iter().find(|&&(t, _)| t == to) {
            total_weight += w;
        }
    }
    (-total_weight).exp()
}

Обратите внимание на 1e-10 — эпсилон для сравнения чисел с плавающей точкой. Без него ошибки округления будут генерировать ложные срабатывания. Это одна из тех деталей, которые отличают работающий продакшен-код от академического примера.

SPFA: когда Bellman-Ford слишком медленный

SPFA (Shortest Path Faster Algorithm) — оптимизация Bellman-Ford на основе очереди. Вместо того чтобы на каждой итерации перебирать все рёбра, SPFA поддерживает очередь вершин, расстояния до которых были обновлены, и релаксирует только рёбра, исходящие из этих вершин. Наихудшая сложность остаётся O(|V|*|E|), но на практике среднее время работы — O(|E|).

Представьте разницу так: Bellman-Ford — это обход всех комнат в здании на каждом раунде. SPFA — это обход только тех комнат, куда «постучались» на предыдущем шаге. Если обновление затронуло 3 вершины из 500, мы обработаем рёбра только этих 3 вершин, а не все рёбра графа.

Детектирование отрицательных циклов в SPFA

В SPFA мы отслеживаем длину пути до каждой вершины. Если путь до какой-то вершины содержит |V| или более рёбер — мы гарантированно нашли отрицательный цикл (по принципу «голубиных клеток»: в пути из |V| рёбер через |V| вершин хотя бы одна вершина повторяется).

use std::collections::VecDeque;

/// SPFA с ранним обнаружением отрицательных циклов
fn detect_arbitrage_spfa(graph: &ArbitrageGraph) -> Option<ArbitrageResult> {
    let n = graph.n;
    let mut dist = vec![0.0_f64; n];
    let mut pred = vec![usize::MAX; n];
    let mut path_len = vec![0_u32; n];
    let mut in_queue = vec![true; n];
    let mut queue: VecDeque<usize> = (0..n).collect();

    while let Some(u) = queue.pop_front() {
        in_queue[u] = false;

        for &(v, w) in &graph.adj[u] {
            if dist[u] + w < dist[v] - 1e-10 {
                dist[v] = dist[u] + w;
                pred[v] = u;
                path_len[v] = path_len[u] + 1;

                // Длина пути >= n => отрицательный цикл!
                if path_len[v] >= n as u32 {
                    let cycle = trace_cycle(v, &pred, n);
                    let profit_ratio = calculate_profit_ratio(graph, &cycle);
                    return Some(ArbitrageResult { cycle, profit_ratio });
                }

                if !in_queue[v] {
                    // SLF: если dist[v] < dist[front], в начало очереди
                    if let Some(&front) = queue.front() {
                        if dist[v] < dist[front] {
                            queue.push_front(v);
                        } else {
                            queue.push_back(v);
                        }
                    } else {
                        queue.push_back(v);
                    }
                    in_queue[v] = true;
                }
            }
        }
    }

    None
}

SLF и LLL: тонкая настройка очереди

Две оптимизации, которые значительно ускоряют SPFA на практике:

SLF (Smallest Label First): при добавлении вершины v в очередь, если dist[v] < dist[queue.front()], вставляем v в начало очереди вместо конца. Это приоритизирует более «перспективные» вершины — те, до которых уже найден короткий путь.

LLL (Large Label Last): поддерживаем среднее расстояние вершин в очереди. Если при извлечении вершина имеет расстояние выше среднего, отправляем её обратно в конец. Это предотвращает «застревание» на дальних вершинах.

Есть и более изощрённый подход — проверка графа зависимостей. Каждые n итераций проверяем, есть ли цикл в графе предшественников (pred). Если есть — в исходном графе гарантированно существует отрицательный цикл. Бенчмарки показывают разницу в порядки: 1737 мс для стандартного SPFA против практически мгновенного обнаружения для графов с 10^4 вершинами.

Bellman-Ford перебирает все рёбра на каждой итерации. SPFA обрабатывает только «активные» вершины, что на практике даёт многократное ускорение на разреженных графах.

RICH: революция в обнаружении арбитража (VLDB 2025)

А теперь — самое интересное. RICH (Real-time Identification of negative Cycles for High-efficiency arbitrage) — алгоритм, опубликованный на VLDB 2025, который показывает до 32.69-кратного ускорения по сравнению со стандартным Bellman-Ford для обнаружения арбитража.

RICH решает задачу k-hop Most Negative Cycle (kMNC): поиск отрицательного цикла длиной не более k рёбер с минимальным суммарным весом. Это именно то, что нужно для арбитража: мы хотим найти самый прибыльный цикл, причём ограниченной длины (на практике сделки длиннее 5-6 ног редко выгодны из-за комиссий и проскальзывания).

Техника раскраски (Color-Coding)

Ключевая инновация RICH — адаптация техники раскраски (color-coding), впервые предложенной Alon, Yuster и Zwick в 1995 году, для задачи обнаружения отрицательных циклов.

Идея на удивление красива:

1. Случайная раскраска. Присваиваем каждой вершине случайный цвет из множества {1, 2, ..., k}.
2. Поиск «красочных» циклов. Ищем циклы, в которых все вершины имеют различные цвета, используя динамическое программирование.
3. Вероятностная гарантия. Цикл длины k имеет вероятность k!/k^k быть «красочным». Запуская O(2^k) независимых испытаний, получаем высокую вероятность обнаружения.

Почему это работает? «Красочный» цикл — это цикл, в котором каждый цвет встречается ровно один раз. Если цикл длины k раскрашен k цветами, вероятность того, что все цвета различны, равна k!/k^k (это же задача о дне рождения!). Для k=5 эта вероятность составляет ~3.8%, что кажется мало. Но после 2^5 = 32 независимых попыток вероятность пропустить цикл экспоненциально мала.

Динамическое программирование в RICH

Для каждой вершины v и каждого подмножества цветов S:

dp[v][S] = минимальный вес пути, заканчивающегося в v,
           который использует ровно цвета из S (по одной вершине на цвет)

Переход:

dp[v][S] = min по всем рёбрам (u, v):
             dp[u][S \ {color(v)}] + w(u, v)
           где color(v) ∈ S

Обнаружение цикла:

Для каждой вершины v и полного набора цветов S = {1, ..., k}:
  Если dp[v][S] < 0 и существует ребро (v, начало_пути):
    Найден отрицательный k-цикл!

Ключевая оптимизация — битовое кодирование множеств цветов. Множество из k цветов представляется k-битной маской, все операции над множествами выполняются за O(1). Для k=6 множество хранится в одном байте, и проверка принадлежности — это одна побитовая операция.

Алгоритм RICH: (a) случайная раскраска вершин, (b) динамическое программирование по подмножествам цветов, (c) обнаружение отрицательного цикла. Битовые маски обеспечивают O(1) операции над множествами.

Почему RICH даёт 32x ускорение

Bellman-Ford ищет любой отрицательный цикл любой длины, делая |V|-1 итераций по всем рёбрам. RICH целенаправленно ищет циклы ограниченной длины k, и его DP-таблица имеет структуру, позволяющую:

1. Отсечение графа по цветам. Если вершина окрашена в цвет 3, она не может участвовать в путях, множество цветов которых не содержит 3. Это позволяет безопасно удалить большинство вершин и рёбер.
2. Инкрементальные обновления. При изменении веса ребра (обновление цены) пересчитываются только затронутые состояния DP, а не вся таблица.
3. Фокус на коротких циклах. На практике арбитражные циклы длиной 3-6 — самые прибыльные. RICH находит их за O(2^k * |V| * |E|), что при k=5 и умеренном размере графа радикально быстрее, чем O(|V| * |E|) для Bellman-Ford, который тратит время на исследование длинных, непрактичных путей.

Сложность RICH:

• Время: O(2^k * |V| * |E|) за одну итерацию, O(e^k) итераций для высокой вероятности
• Память: O(2^k * |V|)
• Ограничение: экспоненциальный фактор 2^k делает алгоритм непрактичным для k > 15

Для типичного арбитражного сканера с k=5 (пятиногие сделки — разумный максимум) это означает 2^5 = 32 состояния на вершину. На графе с 500 вершинами и 2000 рёбрами это ~32 * 500 = 16,000 состояний и ~32 * 2000 = 64,000 переходов за итерацию — молниеносно по сравнению с 499 * 2000 = 998,000 операций для Bellman-Ford.

Line Graph + MMBF: 23,868 путей вместо 19

Если RICH — это снайперская винтовка для коротких циклов, то MMBF (Modified Moore-Bellman-Ford) на линейном графе — это невод, который вылавливает все прибыльные маршруты, включая длинные и нециклические.

Что такое линейный граф

Линейный граф L(G) исходного графа G — это трансформация, в которой:

• Каждое ребро (торговая пара / пул ликвидности) в G становится вершиной в L(G)
• Две вершины в L(G) соединены, если соответствующие рёбра в G имеют общий токен

Исходный граф G:
  Токены: {A, B, C}
  Пулы:   {A-B, B-C, A-C}

Линейный граф L(G):
  Вершины: {AB, BC, AC}
  Рёбра:   AB--BC (общий токен B)
            AB--AC (общий токен A)
            BC--AC (общий токен C)

Почему это прорыв

Результаты на данных Uniswap V2 поражают:

Стандартный MBF нашёл 19 путей. MMBF — 23,868. Разница в три порядка! Почему? Стандартный Bellman-Ford «застревает» на первом найденном отрицательном цикле из 3-4 вершин. MMBF на линейном графе:

1. Находит циклы от любого указанного токена — можно искать арбитраж, начинающийся именно с USDT или ETH.
2. Обнаруживает больше циклов за один запуск — минимум один цикл от каждого стартового токена.
3. Находит нециклические пути — прибыльные маршруты A -> ... -> N, где N != A. Это полезно для ребалансировки портфеля.
4. Работает с длинными путями — до 15 хопов, где скрывается большая часть неочевидной прибыли.

Стандартный MBF находит единичные короткие циклы. MMBF на линейном графе обнаруживает на порядки больше прибыльных маршрутов, включая длинные цепочки и нециклические пути.

K кратчайших путей: ранжирование возможностей

Найти один арбитражный цикл — полдела. В реальной торговле мы хотим видеть топ-N лучших возможностей, чтобы выбрать оптимальную с учётом ликвидности, скорости исполнения и рисков.

Алгоритм Йена (Yen's algorithm) находит K кратчайших путей без петель от источника к цели. Адаптация для арбитража: для каждого актива A ищем K кратчайших путей от A к A самому себе. Каждый такой путь с отрицательным суммарным весом — арбитражная возможность.

Альтернативный подход — перечисление циклов через приоритетную очередь:

use std::collections::BinaryHeap;
use std::cmp::Reverse;
use ordered_float::OrderedFloat;

/// Поиск top-K арбитражных возможностей по всем активам
fn find_top_k_arbitrage(
    graph: &ArbitrageGraph,
    k: usize,
    max_hops: usize,
) -> Vec<ArbitrageResult> {
    let n = graph.n;
    let mut heap: BinaryHeap<Reverse<(
        OrderedFloat<f64>, usize, Vec<usize>, usize,
    )>> = BinaryHeap::new();
    let mut results: Vec<ArbitrageResult> = Vec::new();

    // Стартуем от каждой вершины
    for v in 0..n {
        heap.push(Reverse((
            OrderedFloat(0.0), v, vec![v], v,
        )));
    }

    while let Some(Reverse((weight, current, path, start))) = heap.pop() {
        // Вернулись к старту — цикл найден
        if path.len() > 1 && current == start {
            if weight.0 < -1e-10 {
                results.push(ArbitrageResult {
                    cycle: path,
                    profit_ratio: (-weight.0).exp(),
                });
                if results.len() >= k {
                    break;
                }
            }
            continue;
        }

        if path.len() > max_hops {
            continue;
        }

        // Расширяем соседей
        for &(next, edge_w) in &graph.adj[current] {
            if next != start && path.contains(&next) {
                continue; // Не повторяем вершины (кроме старта)
            }

            let mut new_path = path.clone();
            new_path.push(next);
            heap.push(Reverse((
                OrderedFloat(weight.0 + edge_w),
                next,
                new_path,
                start,
            )));
        }
    }

    results.sort_by(|a, b| b.profit_ratio.partial_cmp(&a.profit_ratio).unwrap());
    results
}

Этот подход прост и гибок: он находит циклы любой длины до max_hops, ранжированные по прибыльности. Однако его сложность растёт экспоненциально с глубиной поиска, поэтому для больших графов предпочтительнее RICH.

Построение мультиинструментального графа

Реальный арбитражный граф — это не просто «валюты и курсы». Он включает разные типы активов, биржи и способы конвертации.

Кросс-биржевая структура

Один и тот же актив на разных биржах — это разные вершины графа, соединённые рёбрами переводов:

Вершины:
  - (Актив, Биржа) пары: (BTC, Binance), (BTC, OKX), (ETH, Binance), ...

Рёбра:
  - Торговые: (BTC, Binance) -> (USDT, Binance), вес = -log(bid * (1-fee))
  - Переводы: (BTC, Binance) -> (BTC, OKX), вес = -log(1 - withdrawal_fee) + time_risk
  - Базисные: (BTC_spot) -> (BTC_perp), вес = -log(1 + basis - 2*fee)

Моделирование инструментов

Спот, бессрочные фьючерсы, поставочные фьючерсы и опционы моделируются как отдельные вершины:

#[derive(Clone, Debug, Hash, Eq, PartialEq)]
struct AssetNode {
    asset: String,
    exchange: String,
    asset_type: AssetType,
}

#[derive(Clone, Debug, Hash, Eq, PartialEq)]
enum AssetType {
    Spot,
    PerpetualFuture,
    DeliveryFuture { expiry: chrono::NaiveDate },
    Option { expiry: chrono::NaiveDate, strike: u64, is_call: bool },
}

#[derive(Clone, Debug)]
enum EdgeType {
    /// Обычная спот-торговля
    Trade { pair: String, bid: f64, ask: f64, bid_size: f64, ask_size: f64 },
    /// Межбиржевой перевод
    Transfer { fee: f64, estimated_time_secs: u64 },
    /// Базисная сделка спот-фьючерс
    BasisTrade { basis_bps: f64, funding_rate: f64, next_funding_time: u64 },
    /// Календарный спред между экспирациями
    CalendarSpread { near_expiry: chrono::NaiveDate, far_expiry: chrono::NaiveDate, spread_bps: f64 },
}

Такая модель позволяет находить сложные арбитражные цепочки, например:

5-leg: USDT -> BTC_spot (Binance) -> BTC_spot (OKX)
        -> ETH_spot (OKX) -> ETH_spot (Binance) -> USDT

Спот-фьючерс: USDT -> BTC_spot -> BTC_perp -> USDT
  (cash-and-carry арбитраж через базис)

Календарный: BTC_fut_Mar -> BTC_fut_Jun -> BTC_spot -> BTC_fut_Mar
  (если спред между экспирациями аномален)

Единый граф объединяет спотовые пары, бессрочные и поставочные фьючерсы, межбиржевые переводы. Каждый тип ребра имеет свою модель весов.

Учёт ликвидности

Критический нюанс: обменный курс из стакана имеет ограниченную ликвидность на каждом ценовом уровне. Если арбитражная возможность требует продать 10 BTC, а на лучшем уровне bid стоит только 0.5 BTC, реальный курс будет хуже.

/// Ребро с учётом объёма (несколько ценовых уровней)
struct VolumeAwareEdge {
    tiers: Vec<(f64, f64)>, // (кумулятивный_объём, маржинальный_курс)
}

impl VolumeAwareEdge {
    /// Эффективный курс для заданного объёма сделки
    fn effective_rate(&self, volume: f64) -> f64 {
        let mut remaining = volume;
        let mut total_output = 0.0;

        for &(tier_volume, rate) in &self.tiers {
            let fill = remaining.min(tier_volume);
            total_output += fill * rate;
            remaining -= fill;
            if remaining <= 0.0 {
                break;
            }
        }

        if remaining > 0.0 {
            return 0.0; // Недостаточно ликвидности
        }

        total_output / volume
    }
}

Обновления в реальном времени

Крипторынок не ждёт. Цены обновляются сотни раз в секунду через WebSocket-потоки. Граф должен обновляться инкрементально, не пересчитывая всё с нуля.

Инкрементальные обновления рёбер

При изменении цены в стакане обновляются только затронутые рёбра:

struct IncrementalGraphManager {
    graph: ArbitrageGraph,
    dirty_edges: Vec<(usize, usize)>,
    affected_vertices: HashSet<usize>,
}

impl IncrementalGraphManager {
    fn on_price_update(
        &mut self,
        base: &str,
        quote: &str,
        new_bid: f64,
        new_ask: f64,
        fee: f64,
    ) {
        let base_idx = self.graph.asset_to_idx[base];
        let quote_idx = self.graph.asset_to_idx[quote];

        let sell_weight = -(new_bid * (1.0 - fee)).ln();
        let buy_weight = -((1.0 / new_ask) * (1.0 - fee)).ln();

        self.graph.update_edge(base_idx, quote_idx, sell_weight);
        self.graph.update_edge(quote_idx, base_idx, buy_weight);

        self.dirty_edges.push((base_idx, quote_idx));
        self.affected_vertices.insert(base_idx);
        self.affected_vertices.insert(quote_idx);
    }

    fn detect_incremental(&mut self) -> Vec<ArbitrageResult> {
        if self.dirty_edges.is_empty() {
            return Vec::new();
        }

        // SPFA естественно фокусируется на затронутых вершинах
        let result = detect_arbitrage_spfa(&self.graph);

        self.dirty_edges.clear();
        self.affected_vertices.clear();

        result.into_iter().collect()
    }
}

Пакетная обработка обновлений

В высокочастотных сценариях обрабатываем пачку обновлений перед сканированием:

use std::time::{Duration, Instant};

struct BatchedScanner {
    graph_manager: IncrementalGraphManager,
    last_scan: Instant,
    min_scan_interval: Duration,
    pending_updates: usize,
    max_batch_size: usize,
}

impl BatchedScanner {
    fn on_update(&mut self, /* ... */) {
        self.graph_manager.on_price_update(/* ... */);
        self.pending_updates += 1;

        if self.pending_updates >= self.max_batch_size
            || self.last_scan.elapsed() >= self.min_scan_interval
        {
            let results = self.graph_manager.detect_incremental();
            self.pending_updates = 0;
            self.last_scan = Instant::now();

            for result in results {
                self.execute_or_queue(result);
            }
        }
    }
}

Конкурентные структуры данных в Rust

Для многопоточной арбитражной системы граф должен поддерживать одновременные чтения (сканирование) и записи (обновление цен). Мы используем три паттерна:

ArcSwap — лучший выбор для арбитража. Lock-free чтение, один писатель создаёт новый снимок графа и атомарно подменяет указатель. Идеально для паттерна «один писатель, много читателей»:

use arc_swap::ArcSwap;
use std::sync::Arc;

struct ConcurrentArbitrageGraph {
    graph: ArcSwap<ArbitrageGraph>,
}

impl ConcurrentArbitrageGraph {
    /// Lock-free чтение для потоков сканирования
    fn snapshot(&self) -> arc_swap::Guard<Arc<ArbitrageGraph>> {
        self.graph.load()
    }

    /// Обновление графа (вызывается потоком ценовых данных)
    fn update(&self, new_graph: ArbitrageGraph) {
        self.graph.store(Arc::new(new_graph));
    }
}

Crossbeam каналы для коммуникации между потоками:

use crossbeam_channel::{bounded, Sender, Receiver};

struct ArbitrageOpportunity {
    cycle: Vec<usize>,
    profit_ratio: f64,
    detected_at: std::time::Instant,
    graph_snapshot_age: std::time::Duration,
}

fn spawn_scanner_pool(
    graph: Arc<ConcurrentArbitrageGraph>,
    tx: Sender<ArbitrageOpportunity>,
    num_scanners: usize,
) {
    for scanner_id in 0..num_scanners {
        let graph = graph.clone();
        let tx = tx.clone();

        std::thread::spawn(move || {
            loop {
                let snapshot = graph.snapshot();
                let start = std::time::Instant::now();

                // Каждый сканер проверяет подмножество стартовых вершин
                let sources_per_scanner = snapshot.n / num_scanners;
                let start_vertex = scanner_id * sources_per_scanner;
                let end_vertex = if scanner_id == num_scanners - 1 {
                    snapshot.n
                } else {
                    (scanner_id + 1) * sources_per_scanner
                };

                for source in start_vertex..end_vertex {
                    if let Some(result) = detect_from_source(&snapshot, source) {
                        let _ = tx.send(ArbitrageOpportunity {
                            cycle: result.cycle,
                            profit_ratio: result.profit_ratio,
                            detected_at: std::time::Instant::now(),
                            graph_snapshot_age: start.elapsed(),
                        });
                    }
                }
            }
        });
    }
}

Общая архитектура выглядит так: WebSocket-фид обновляет граф через единственный поток-писатель. Он создаёт новый снимок и атомарно подменяет через ArcSwap. Пул потоков-сканеров берёт последний снимок (lock-free!) и запускает SPFA от разных стартовых вершин. Найденные возможности отправляются через crossbeam-канал в движок исполнения.

WebSocket-фид -> Graph Builder (единственный писатель) -> ArcSwap (lock-free подмена) -> пул сканеров (SPFA) -> Opportunity Queue (crossbeam) -> Execution Engine.

Практическое руководство: какой алгоритм когда использовать

После всей теории — конкретные рекомендации. Мы составили матрицу выбора на основе нашего опыта:

Матрица решений

Сравнение сложностей

┌──────────────────────┬───────────────┬────────────┬──────────────────────────┐
│ Алгоритм             │ Время         │ Память     │ Лучший случай            │
├──────────────────────┼───────────────┼────────────┼──────────────────────────┤
│ Bellman-Ford         │ O(VE)         │ O(V)       │ Простой, надёжный        │
│ SPFA                 │ O(VE) / O(E)  │ O(V)       │ Быстрый на практике      │
│ Floyd-Warshall       │ O(V³)         │ O(V²)      │ Плотные рынки            │
│ Johnson's            │ O(V²lgV + VE) │ O(V²)      │ Все пары, разреженный    │
│ RICH (color-coding)  │ O(2^k·VE)     │ O(2^k·V)   │ k-bounded лучший цикл   │
│ MMBF (line graph)    │ O(M·E_L)      │ O(E_L)     │ Все пути + нециклические │
│ Yen's K-shortest     │ O(KN(M+NlgN)) │ O(KN)      │ Топ-K возможностей       │
└──────────────────────┴───────────────┴────────────┴──────────────────────────┘

Практические бенчмарки

Честное предупреждение

Несколько важных ограничений, о которых молчат большинство статей:

Фантомный арбитраж. Последовательные API-запросы создают временную рассинхронизацию. Цены меняются между запросами, создавая видимость арбитража из устаревших данных. WebSocket-фиды смягчают, но не устраняют проблему.

Комиссии съедают прибыль. Исследования показывают, что обнаруженные возможности часто дают лишь 0.05-0.087% прибыли — ниже порога комиссий. На DEX добавляется gas fee: за 11 месяцев на Uniswap из 34,429 ETH выручки 8,458 ETH ушло на газ.

Статистика DEX-арбитража: 85% циклических арбитражных транзакций — трёхногие. Это совпадает с нашей рекомендацией использовать RICH с k=3-5.

Риски фьючерсов: базисный риск (спот и фьючерс могут разойтись при экстремальных условиях), ликвидационный риск (левередж), переменность funding rate (ставка меняется каждые 8 часов).

Что дальше

В следующих частях серии мы разберём:

• Часть 2: Funding rate арбитраж — как моделировать временные рёбра и оптимизировать доходность cash-and-carry стратегий
• Часть 3: GNN-подходы — графовые нейросети для предсказания арбитража до его появления
• Часть 4: Полная реализация на Rust — от WebSocket-фида до исполнения ордеров

Графовые алгоритмы — это не просто элегантная математика. Это рабочий инструмент, который превращает хаос крипторынков в структурированное пространство поиска. Bellman-Ford даёт надёжный фундамент. SPFA ускоряет его на практике. RICH выводит на новый уровень для ограниченных циклов. А MMBF раскрывает возможности, которые классические методы просто не видят. Выбирайте инструмент под задачу — и пусть граф работает на вас.

Полезные ссылки

1. RICH: Real-Time Identification of Negative Cycles for High-Efficiency Arbitrage (VLDB 2025)
2. An Improved Algorithm to Identify More Arbitrage Opportunities on DEXes (Zhang et al., 2024)
3. Cyclic Arbitrage in Decentralized Exchanges (Wang, WWW 2022)
4. Graph Algorithms and Currency Arbitrage — Reasonable Deviations
5. Using the SPFA to Find Negative Cycles — KonaeAkira
6. petgraph — графовая библиотека для Rust
7. kucoin_arbitrage — Event-Driven арбитраж на Rust
8. Color-Coding: A New Method for Finding Simple Paths, Cycles (Alon, Yuster, Zwick)
9. Bellman-Ford Algorithm — cp-algorithms
10. ArcSwap — lock-free замена Arc в Rust
11. Crossbeam — конкурентное программирование на Rust
12. The Ultimate Guide to Funding Rate Arbitrage — Amberdata

Цитирование

@software{soloviov2026grapharbitragealgorithms,
  author = {Soloviov, Eugen},
  title = {Графовые алгоритмы для обнаружения арбитража: от Bellman-Ford до RICH},
  year = {2026},
  url = {https://marketmaker.cc/ru/blog/post/complex-arbitrage-graph-algorithms},
  version = {0.1.0},
  description = {Как преобразовать криптовалютные рынки в взвешенный ориентированный граф, находить арбитражные возможности через детектирование отрицательных циклов, и почему алгоритм RICH (VLDB 2025) даёт 32-кратное ускорение по сравнению с классическим Bellman-Ford.}
}