Программные продукты и системы

. Обработка больших графов требует большого количества ресурсов, особенно если структура графа неизвестна заранее или существенно меняется в ходе вычислений. Примером задачи, требующей создания графа с нуля по частям, является восстановление сети связей между узлами по наблюдаемому распространению инфекций среди населения или распространению новостей и мемов в социальных сетях. За последнее время было разработано большое количество систем, обрабатывающих большие графы на одном компьютере с приемлемой производительностью. Однако в основном они плохо подходят для ситуаций, когда структура графа неизвестна заранее, а также существенно изменяется в процессе работы. Большинство таких систем, включая GraphChi, TurboGraph, VENUS, требуют специального преобразования графа в представление, подходящее для эффективной обработки. Это преобразование необходимо повторять при существенных изменениях структуры графа, что ведет к значительным накладным расходам. Графовые БД, являющиеся наиболее подходящими системами для работы с динамическими графами, в целом имеют невысокую скорость доступа к данным. Доработанные системы обработки графов на отдельном компьютере, такие как GraphChi-DB, также показывают невысокую производительность.

  Подробное описание дается в статье «Системы и подходы для обработки информации, представленной большими динамическими графами», автор Гуляевский С.Е. (Институт систем информатики им. А.П. Ершова СО РАН, г. Новосибирск).