Comments 2
Очень интересно, но многое осталось непонятным. Критерий разделения графа на части (какие ребра перекусывать) самому надо задавать, или для этого есть какие-то встроенные алгоритмы кластеризации? Что, если данные, привязанные к графу, меняются по ходу обработки? Если граф не scale-free, а полносвязный или близкий к этому, как его разбивать на части?
Спасибо за интерес к моей статье.
Критерий разделения графа на части (какие ребра перекусывать) самому надо задавать, или для этого есть какие-то встроенные алгоритмы кластеризации?
Если граф не scale-free, а полносвязный или близкий к этому, как его разбивать на части?
Как было отмечено в статье, разбивать граф можно двумя способами: по вершинами и по ребрам, причём разбиение по вершинам более предпочтительно, т.к позволяет избежать проблем с перекосом (skew) данных. Разбиение по вершинам выполняется достаточно тривиально: просто делим таблицу с ребрами на части, хотя локальность данных будет не очень хорошая. Задача разбиения графа является NP-полной, но существуют несколько алгоритмов, которые позволяют найти приемлимое разбиение.
Я попробую осветить этот вопрос в одной из последующих статей, но, чтобы не ждать, предлагаю поискать в интернете информацию по слову "ParMeTiS" или найти статью "A Coarse-Grain Parallel Formulation of Multilevel k-way Graph Partitioning Algorithm" на Google Scholar.
Что, если данные, привязанные к графу, меняются по ходу обработки?
Итеративная природа алгоритмов на графах для Pregel не препятствует изменению графа в процессе, т.к программы обычно являются Stateless. Так, новые данные будут доступны на следующей итерации. GraphLab и PowerGraph используют разделяемую память и могут кэшировать какую-то информацию, поэтому отслеживание изменений в графе ложится на плечи разработчика алгоритма.
Обработка больших и очень больших графов