Системы обработки больших графов

Обрабатывать большие графы можно с помощью специального программного обеспечения, разработанного для каждой задачи. Однако в настоящее время существует целый ряд систем обработки больших графов (Large graph mining systems) (и их число продолжает расти), которые направлены на упрощение этого процесса. Эти системы абстрагируются от стандартных деталей и предоставляют интерфейс более высокого уровня для управления алгоритмами, работающими на графе. Выделяется следующие три важных свойства, которые различают такие системы.

Пакетные или онлайн системы (Batch or online systems). Пакетная система должна обрабатывать весь граф целиком для любой задачи, тогда как онлайн система обеспечивает более быстрый доступ к произвольным областям графа.

Системы со списком смежных вершин или дуг (Systems with adjacency or edge list). Система, которая разрешает доступ к смежным вершинам, позволяет получать всех соседей любой заданной вершины. Система, которая разрешает доступ к списку дуг, предоставляет только множество дуг.

Распределенные или централизованные системы (Distributed or centralized systems). Если система обработки больших графов является распределенной, то предоставляется доступ только к локальным областям графа, которые хранятся на некотором заданном компьютере, а данные, необходимые для понимания оставшейся части графа, могут быть удалены и трудны для доступа; централизованная система имеет более целостное представление о графе.

Например, MapReduce является пакетной, распределенной системой, которая предоставляет либо список дуг, либо доступ к смежным вершинам, GraphLab является распределенной, онлайн системой со списками смежных вершин, а Ligra является централизованной, онлайн системой со списками смежных вершин.

Литература=

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