Архив статей журнала
В статье сделан обзор ключевых особенностей и преимуществ основных существующих подходов и систем обработки больших графов на персональном компьютере, таких как GraphChi, TurboGraph, GraphChi-DB и другие, а также распределенных систем, таких как Apache GraphX. Особое внимание уделено задачам, требующим в процессе вычислений существенных изменений в структуре графа, и особенностям реализации таких задач в системах обработки графов. Проведены сравнительные эксперименты с использованием известного алгоритма восстановления сети связей между узлами по наблюдаемому распространению инфекций среди населения или распространению новостей и мемов в социальных сетях. В используемом алгоритме для получения оценок изменяющейся во времени структуры и временной динамики предполагаемой сети применяется стохастический градиент. Алгоритм был реализован для моделей вычисления GraphChi и Apache Spark, измерена скорость выполнения для различных наборов реальных и синтетических данных, описаны ограничения для этих моделей вычисления, обнаруженные в процессе экспериментов. Для реализации GraphChi вычисления проведены на одиночном компьютере, для Apache Spark - на различном количестве серверов в кластере. Показано, что существующие системы разделяются на три класса: быстрые системы со статическим разбиением графа на разделы и дорогим переразбиением при существенных изменениях структуры; в среднем более медленные системы, способные эффективно обрабатывать большие объемы изменений; еще более медленные, но хорошо масштабируемые системы, компенсирующие низкую удельную производительность возможностью масштабировать вычисления на кластеры из большого количества узлов. Сделан вывод, что проблема эффективного хранения и обработки динамических графов в полной мере не решена и требует дополнительного исследования.