Как искать узкие места в графах

Что проверяют

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

Как отвечать

Начните с уточнения: что за граф и что значит «узкое». Дальше назовите инструмент под каждый смысл:

• посредническая центральность (betweenness): доля кратчайших путей между парами вершин, проходящих через вершину или ребро. Алгоритм Брандеса считает её за O(V·E) на невзвешенном графе, в NetworkX это nx.betweenness_centrality и nx.edge_betweenness_centrality, параметр k включает приближение по выборке вершин;
• точки сочленения и мосты: вершины и рёбра, без которых граф распадается на компоненты. Находятся за линейное время обходом в глубину, в NetworkX nx.articulation_points и nx.bridges для неориентированного графа;
• минимальный разрез: если у рёбер есть пропускная способность, узкое место между источником и стоком это минимальный разрез, и по теореме Форда-Фалкерсона его величина равна максимальному потоку. Алгоритмы Эдмондса-Карпа или Диница, в NetworkX nx.minimum_cut;
• критический путь: в DAG пайплайна данных узкое место это самая долгая цепочка задач, nx.dag_longest_path с весами по времени выполнения.

Для графов, не влезающих в память одной машины, упомяните Neo4j Graph Data Science, графовые библиотеки поверх Spark и приближённые методы. Найденное узкое место подтверждают метриками реальной нагрузки, а не только топологией.

Где спотыкаются

Называют Дейкстру и Флойда-Уоршелла как способ найти узкие места. Это алгоритмы кратчайших путей, загрузку они сами по себе не показывают, а Флойд-Уоршелл за O(V³) на реальном графе просто не досчитается.

Путают центральность по степени с посреднической. Вершина с тысячей соседей может сидеть внутри одного плотного кластера, а настоящий мост между кластерами иметь всего две связи.

Запускают точную betweenness на миллионах вершин и удивляются, что расчёт не заканчивается. Про выборку и приближения нужно сказать заранее.