Методы обработки больших графов

Существует три канонических типа методов обработки больших графов (Large graph mining methods), которые охватывают подавляющее большинство используемых вариантов и алгоритмов.

Обработка на основе геодезических окрестностей включает в себя некоторую вершину, соседние ей вершины и ребра между ними. Методы такого типа являются одними из самых простых для масштабирования на большие графы и поддерживают удивительное разнообразие различных приложений, например, обнаружение аномалий. Эти методы, как правило, очень легко масштабировать до больших графов при одновременной обработке всех вершин. Чтобы определить, будет ли алгоритм, который использует этот примитив, масштабироваться до еще больших графов, основной проблемой является размер узла наивысшей степени. Двумя примерами задач, которые можно решить с помощью методов обработки на основе геодезических окрестностей, являются подсчет треугольников и вычисление экстремальных собственных значений у всех окрестностей.

Обработка на основе диффузионных окрестностей можно рассматривать как более мягкую или нечеткую версию вычислений на основе геодезических окрестностей. Использование графовых диффузий при обработке графов обычно является формализацией следующей идеи: значение течет от исходной вершины по дугам графа к смежным ей вершинам. Механизм поведения диффузии на дуге графа определяет конкретный тип диффузии. Хорошо известными примерами являются: диффузия PageRank, диффузия Каца, диффузия теплового ядра, диффузия усеченных случайных блужданий. Эти методы можно использовать для ответов на такие вопросы, как «Как выглядит область данного графа вокруг данного конкретного объекта?». Их легко также масштабировать на большие графы, потому что здесь не нужно исследовать весь граф. Например, случайные блуждания с перезапуском являются примером этой идеи. Следует подумать о том, чтобы запускать эти диффузии в окрестностях не у всех, а только у [math]\displaystyle{ O(\log n) }[/math] или [math]\displaystyle{ O(\sqrt n) }[/math] вершин.

Обработка на основе обобщенных произведений матрица-вектор является одним из самых гибких и масштабируемых способов обработки больших графов. Как следует из названия, эти методы возникают из обобщенного понятия матрично-векторного произведения на обобщениях матрицы смежности графа. В более общем смысле матрично-векторный произведение можно рассматривать как частный случай следующего вычислительного примитива: обновлять данные вершины на основе некоторой заданной функции от данных смежных ей вершин. Стандартное матрично-векторное произведение использует суммирование в качестве данной функции. Итерационные последовательности этих операций, с различными функциями, вычисляют связанные компоненты, кратчайшие пути из одного источника, распространение меток, эффективные диаметры и гистограммы расстояний. Такие операции, как минимальные остовные деревья, паросочетания максимального веса и методы передачи сообщений, также вписываются в эту же схему. Все эти методы и алгоритмы применяются в пакетных системах, а не в онлайн-системах.

Литература=

• Buhlmann P., Drineas P., Kane M., van der Laan M. (eds.) Handbook of Big Data. — CRC Press, 2016.