Кратко и по делу — сравнение трёх подходов по памяти, времени и параллелизации, и когда что лучше.
1) Смежные списки (включая CSR/CSC)
- Память: примерно $O(|V|+|E|)$ (в CSR — массивы вершин и ребер). Очень экономно для разреженных графов.
- Время (в среднем): обход соседей вершины $v$ — $O(\mathrm{deg}(v))$; проверка существования ребра $(u,v)$ — $O(\mathrm{deg}(u))$ (если не использовать хеш/индексы); добавление/удаление ребра — $O(1)$ амортизированно с подходящими структурами или $O(\mathrm{deg}(u))$ в упорядоченном списке.
- Параллелизация: хорош для многопоточного/внутримашинного использования; при распределении требуется разбиение вершин (edge-cut) или репликация пограничных данных; нагрузка чувствительна к степеням вершин (высокие степени — «горячие» места). CSR удобен для SIMD/GPU при пакетной обработке соседей.
- Когда предпочтительнее: аналитика и алгоритмы на больших разреженных графах (BFS, DFS, Dijkstra, PageRank на одной машине или в рамках распределённой системы), динамические графы (частые изменения) — проще обновлять, чем матрицу.
- Минусы: проверка существования ребра может быть медленнее; сложнее применять линейно-алгебраические оптимизации напрямую.
2) Матрица смежности (плотная или разреженная как sparse matrix)
- Память: плотная матрица — $O(|V{|}^2)$ (битовая матрица — примерно $|V{|}^2/8$ байт), разрежённые форматы (CSR/CSC для матриц) — $O(|V|+|E|)$.
- Время: проверка существования ребра — $O(1)$; перебор соседей — $O(|V|)$ в плотной форме (неэффективно для разреженных). Операции на матрицах (умножение, спектральные методы) хорошо оптимизируются: операции линейной алгебры на GPU/BLAS очень быстры.
- Параллелизация: отличная поддержка через матричные библиотеки и GPU; хорошие результаты для алгоритмов, сводимых к матрично-векторным операциям (PageRank, спектральные задачи, некоторые счёты треугольников).
- Когда предпочтительнее: плотные графы или умеренное $|V|$ где $|V{|}^2$ влезает в память; алгоритмы, использующие матричную алгебру (спектральный анализ, некоторые ML-процессы); GPU-ускорение.
- Минусы: непригодна для очень больших разреженных графов в плотном представлении; обновления дорогостоящи в плотной матрице.
3) Распределённые графовые платформы / графовые БД (Pregel/Giraph/GraphX, Neo4j, JanusGraph и т.п.)
- Память и хранение: граф разбивается по узлам кластера; затраты — суммарно $O(|V|+|E|)$ плюс накладные расходы на метаданные, индексы, репликацию и «ghost»-узлы; реальная память = данные + сетевой/репликационный overhead.
- Время и пропускная способность: масштабируются на большие $|V|,|E|$, но производительность зависит от коммутационных затрат между машинами; алгоритмы типа Pregel (суперступени = barrier) платят за синхронизацию. Латентность запросов в графовых БД (транзакционные трэвелы) оптимизирована, но выше, чем у in-memory структур.
- Параллелизация: предназначены для масштабирования и отказоустойчивости; ключевые проблемы — балансировка нагрузки (vertex-cut vs edge-cut), репликация высокостепенных вершин, minimization of cross-partition edges. Хороши для массовых итеративных вычислений (PageRank, Connected Components) и для OLTP/OLAP графовых запросов на больших датасетах.
- Когда предпочтительнее: графы, которые не помещаются в память одной машины; распределённая аналитика на кластере; онлайн-графовые запросы и транзакции (если использовать специализированную графовую БД); сценарии, где важна доступность и отказоустойчивость.
- Минусы: сетевые накладные расходы, сложность настройки и оптимального партицирования; возможны проблемы с очень высокими степенями вершин (hotspots).
Резюме/рекомендации
- Если граф разреженный и помещается в память одной машины — использовать CSR/смежные списки для экономии памяти и быстрой итерации соседей.
- Если граф плотный или надо использовать матричную алгебру/GPU — матрица смежности (или разрежённая матрица с оптимизированными BLAS-операциями) предпочтительнее.
- Если граф слишком велик для одной машины или требуются отказоустойчивость и распределённая аналитика/онлайн-запросы — использовать распределённые графовые движки/БД, при этом проектировать партицирование и учитывать коммуникационные издержки.
- Для транзакционных, низколатентных path/traversal запросов — специализированные графовые БД (Neo4j и т.п.). Для массовых итеративных аналитик — граф-парадигмы типа Pregel/GraphX.
Короткая шпаргалка по сложностям:
- память: матрица $O(|V{|}^2)$, списки/CSR $O(|V|+|E|)$;
- обход соседей: списки $O(\mathrm{deg}(v))$, матрица $O(|V|)$;
- проверка ребра: матрица $O(1)$, списки $O(\mathrm{deg}(u))$ или $O(1)$ с хешем;
- параллелизация: матрица/GPU и распределённые системы — сильная параллелизация при соответствующей постановке задачи; списки — хороши для single-node multithreaded.
Если нужно, могу сопоставить конкретные алгоритмы (BFS, PageRank, shortest paths, triangle counting, GNN) с оптимальным представлением.