Эксперименты с графами 😊

Борувка (GraphBLAS, Gunrock, Pregel+)

Эксперимент 1

Цель: Найти зависимость между плотностью графа (где удалено N-е количество ребер) и скоростью работы алгоритма на выбранной библиотеке.

Ход эксперимента:

1. Берём граф из датасета.
2. Начинаем менять количество рёбер в нём так, чтобы можно было построить график зависимости производительности библиотеки от плотности графа (1%, 3%, 5%, 7%, 10%, 13% и 15% от исходного числа рёбер).
3. Сохраняем эти графы в том же формате, в котором были исходные графы и используем для тестов.
4. Проверяем, будет ли сохраняться эта зависимость на всех графах из датасета.

Как меняем графы:

• Не трогаем мосты
• В приоритете менее значимые ребра (по весу и центральности)
• Для каждого получившегося графа выполняем дополнительную проверку на корректность

Эксперимент 2

Цель: Проанализировать производительность библиотеки на графах с одинаковой топологией, но разным распределением весов.

Ход эксперимента:

1. Берём из датасета пару: одинаковые по топологии графы с разным распределением весов.
2. Запускаем алгоритм и смотрим, будет ли различие в производительности (за вычетом погрешности).
3. Проверяем, будет ли сохраняться разница на всех парах графов из датасета.
4. Дополнительно расширяем датасет графами с другим распределением весов и опять проводим тот же анализ.

Эксперимент 3

Цель: Посмотреть, при каком количестве вычислительных узлов (контейнеров) будет оптимальная производительность Pregel+ для “среднего” графа из датасета.

Ход эксперимента:

1. Берём граф из датасета.
2. Запускаем Pregel+ с 1, 2, 4, 8 и 16 контейнерами на этом графе.
3. Измеряем время выполнения.
4. Оцениваем результаты для всех графов.

Подробнее

Результаты для GraphBLAS