Здесь, в Lab41, мы недавно заинтересовались динамическими графиками, и последние несколько месяцев мы пытались понять, какие инструменты мы можем использовать для их анализа - мы называем это проектом SkyLine. Мы пишем в этом блоге, чтобы объяснить, почему мы думаем, что динамические графики интересны, и что мы узнали на данный момент.

Что такого хорошего в динамических графиках?

Мы уже говорили об этом раньше и скажем еще раз: «Графики - отличный способ моделировать мир вокруг нас - от ссылок в Интернете до проводки нашего мозга, наших дружеских отношений и отношений». Графики естественным образом представляют связи, и связи имеют центральное значение для каждой из этих вещей. Но это еще не все: мир постоянно меняется, как и эти связи. Веб-страницы удаляются, а ссылки добавляются каждый день; наш мозг постоянно перестраивается по мере того, как мы познаем и познаем мир.

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

Мы можем многому научиться, применяя методы анализа графов к динамическим графам. Например, алгоритм динамически связанных компонентов может сообщать нам, когда кто-то присоединяется к определенной группе друзей или уходит из нее; применение PageRank к сети может показать нам, как веб-страницы растут или опускаются в памяти. Кроме того, мы можем отслеживать закономерности в графе - например, серию вершин и ребер, соответствующих конкретному интересующему запросу - отмечать их по мере их появления и отслеживать их до тех пор, пока они сохраняются. Мы называем эту функцию «запуском», потому что она позволяет нам реагировать на определенные виды изменений на графике, используя их для «запуска» соответствующих действий, как в примере ниже:

Представьте, что у нас есть граф, вершины которого - это веб-страницы, а ребра - это ссылки, соединяющие их. У нас может быть такой триггер, как «Отправлять уведомление всякий раз, когда страница с« собаками »в URL-адресе соединяется со страницей с« кошками »в URL-адресе, которая связана со страницей с« попугаями »в URL-адресе».

Исходный график ниже не содержит этого пути и, следовательно, не будет запускать этот триггер:

Однако более позднее обновление может добавить границу между «example.com/cats» и «example.com/parakeets», что должно инициировать отправку уведомления пользователю, поскольку он соответствует пути, выделенному красными стрелками [«example. com / dogs »,« example.com/cats »,« example.com/parakeets »]:

[«Example.com/dogs», «example.com/cats», «example.com/parakeets»] и уведомление должно быть отправлено пользователю.

Итак, сколько пакетов с открытым исходным кодом нужно для анализа динамического графика?

К сожалению, на сегодняшний день графическая аналитика в основном имеет дело со статическими графами - графами, которые не обновляются со временем, - и большая часть соответствующего программного обеспечения разработана для этого случая использования. Есть несколько исключений, но даже они малоизвестны, поэтому мы решили выяснить, что возможно сегодня.

Мы начали с изучения всех пакетов аналитики графов с открытым исходным кодом, которые смогли найти. Нашей целью было выяснить, какие функции предлагает каждый из них, какие варианты использования поддерживаются и как они выдерживают нагрузку реальной динамики (возможно, меняющейся сотни тысяч раз в секунду). Ниже представлена ​​обобщенная версия того, что мы обнаружили, и вы можете увидеть результаты во всех их мельчайших подробностях здесь.

В таблице ниже мы включили несколько категорий, которые, по нашему мнению, были важными при принятии решения о том, какой инструмент использовать. Вот что означает каждое из них:

Соответствие ACID / конечная согласованность: каждая операция тем или иным образом зависит от состояния нижележащего графа. Какие гарантии предоставляет эта платформа, что каждая операция будет видеть все изменения, сделанные ее предшественниками / не будет прерывать или конфликтовать с другой операцией, происходящей одновременно?

Поддерживает графики большего размера, чем память. Достаточно понятно, может ли эта платформа обрабатывать графики большего размера, чем память компьютера, на котором она работает?

Поддерживает метки ребер / вершин: Можем ли мы прикрепить дополнительную информацию к каждому ребру и вершине, помимо того, с какими вершинами / ребрами они связаны?

Поддерживает динамические графики / потоковую передачу. Может ли эта платформа обрабатывать изменения рассматриваемого графика без необходимости его полной перезагрузки?

Поддерживает запуск. Если ответ на указанную выше функцию - да, есть ли способ запускать какой-либо фрагмент кода каждый раз, когда происходит изменение определенного типа (например, каждый раз, когда добавляется вершина с Атрибут «name» установлен на «Боб»)?

Качество документации: по шкале «Я могу чизбургер?» в Британскую энциклопедию, насколько доступной и всеобъемлющей является документация? А по шкале от Сумерек до Шекспира насколько он читабелен?

Глядя на эту таблицу, становится ясно, что только некоторые из рассматриваемых пакетов пытаются поддерживать все динамические графики, потоковые обновления и запуск:

Titan: ведущая графическая база данных, созданная и поддерживаемая командой Aurelius (теперь DataStax) и используемая в таких местах, как Cisco Systems и Los Alamos National Labs.

Stinger: проект с открытым исходным кодом, начатый командой Технологического института Джорджии, основанный на их работе над эффективными структурами данных графов. Цель Stinger - поддерживать высокопроизводительную аналитику на динамических графиках!

Weaver: новое распределенное хранилище графиков с открытым исходным кодом, разработанное командой Cornell’s Systems Group, которое разбивает график на несколько серверов и поддерживает высокоэффективные транзакции и обновления.

Как только мы увидели Уивера, мы влюбились в стоящее за ним видение. Это выглядит как действительно солидная идея, над которой работает очень умная группа участников. К сожалению, он находится в зачаточном состоянии, и из часто задаваемых вопросов ясно видно, что Weaver не готов к производству, поэтому нам пришлось пока вставить в него булавку. Тем не менее, мы будем внимательно следить за ним в ближайшем будущем и будем рады увидеть, что станет с проектом.

Остается Титан и Стингер. Поскольку наша первая проблема связана со способностью платформы эффективно обрабатывать обновления графа, мы решили измерить скорость, с которой каждый из них может обрабатывать заданный поток изменений в начальном графе (фактически, начальный набор несвязанных вершин).

Мы написали сценарий Python для создания графиков, которые представляют интересующие нас рабочие нагрузки: множество узлов и ребер, потенциально длинные циклы, атрибуты вершин и т. Д. Чтобы сделать это эффективно, наш сценарий начинался с генерации большого числа деревьев, а затем случайным образом добавляя предков к каждому узлу из набора узлов, более близких, чем он к корню. Затем наш скрипт выбирал и объединял случайные пары узлов и выбирал последовательности узлов, которые он объединял вместе для создания циклов (все необходимые вероятности и ограничения были настроены, а генератору случайных чисел было присвоено постоянное начальное значение 0xcafebabe для воспроизводимости). Эта случайная генерация графов немного отличается от нашей предыдущей работы со стохастическими естественными графами Кронекера, которые для тех, кому интересно, можно найти здесь.

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

  1. Никакое ребро не создавалось, если не существовало вершин на каждом конце.
  2. Каждая созданная вершина (после вершин в начальном наборе) будет иметь ребро, соединяющее ее с существующей вершиной не более чем на один шаг позже в потоке.

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

Повторение:

  1. Выберите путь на границе. Назовем выбранный путь P.
  2. Уберите P с границы.
  3. Для каждого соседа узла в конце P расширите P до этого соседа и добавьте расширенный путь к границе.

Пока граница не опустеет. (По материалам http://artint.info/tutorials/search/search_1.html)

Если граница определяется как набор узлов или ребер, которые необходимо исследовать, и изначально устанавливается для всех узлов, которые примыкают к корню (находятся на другом конце ребра от корневого узла) или просто для всех ребер, исходящих из корневого узла. корень.

Затем мы изменили этот алгоритм так, чтобы граница располагалась в случайном порядке. Убедившись, что ни один узел никогда не попадет на границу (и, следовательно, не будет добавлен в поток) раньше, чем хотя бы один из его предшественников, мы отразили случайный порядок, который демонстрируют реальные потоки.

(В конце концов, в реальном мире мы можем легко предсказать, что отец будет существовать до своего сына, но не то, у какого отца будет сын первым!) Затем мы скармливали полученные потоки как Titan (используя бэкэнд Berkeley DB), так и Стингер и измерил общее время, затраченное на их обработку. Ниже представлены наши выводы.

Затем мы отправили полученные потоки в Titan (используя бэкэнд Berkeley DB) и Stinger и измерили общее время, затраченное на их обработку. Ниже представлены наши выводы.

Как видим, Стингер проигрывает лучшим из них. В наших тестах было ясно, что он работает намного лучше. К сожалению, он может обрабатывать только графы с заранее определенным числом вершин (которое по умолчанию очень мало). С другой стороны, Titan, хотя примерно на порядок медленнее (с использованием настроек по умолчанию и параметров транзакции), был в состоянии обрабатывать графы без видимых ограничений на количество вершин или ребер. Очевидно, есть несколько факторов, которые могут объяснить разницу в производительности, которую мы наблюдали на графиках сопоставимого размера. Одна из причин этого различия заключается в том, что Stinger работает в памяти, а Titan - это транзакционная база данных на диске, хотя есть возможности для настройки этих транзакций. Другие причины включают тот факт, что Stinger написан на C, тогда как Titan использует Java (что может усугубить общее снижение производительности).

В любом случае, мы, вероятно, остановимся на Titan по ряду причин, помимо производительности. Во-первых, он соответствует требованиям ACID, а Stinger - нет. Во-вторых, из двух проектов он гораздо более надежен и готов к производству. Он также лучше документирован, более активно поддерживается и вносится. Наконец, он имеет гораздо лучшую поддержку для специальных запросов и интеграции с другими аналитическими инструментами, такими как стек TinkerPop и мощная платформа визуализации Gephi.

Ну и что дальше?

Мы очень рады «запускающему» сценарию, который мы описали выше. Возможность выявлять закономерности, которые появляются при обновлении графика, и предпринимать действия на основе этих шаблонов многообещающе для различных областей применения. Механизмы бизнес-правил, например, делают именно это, но с реляционно структурированными данными, а не с графиками; в качестве альтернативы, возможность аннотировать модели человеческого транскриптома с новыми открытиями и иметь машину, уведомляющую ученых, когда появляются закономерности, которые их интересуют (например, этот ген, который увеличивает связность в веретенообразной извилине при нокауте, имеет мутантные вариации, которые коррелируют ниже экспрессии этих других генов, влияющих на рост. Да, я это только что выдумал.)

Пока что мы рассмотрели эту проблему только предварительно. Мы упростили наши шаблоны, превратив их в цепочки фиксированной длины, где каждая ссылка определяет предикат, которому должен удовлетворять соответствующий узел или ребро в потенциальном совпадающем пути. Даже в этом случае проблема довольно сложная. Даже простые подходы к индексации сталкиваются с проблемами, такими как высокие требования к памяти - если вы кешируете частичные пути по мере их возникновения - или существенная временная сложность динамической проблемы кратчайшего пути по всем точкам - если вы хотите сохранить информацию о том, сколько прыжков вы выполняете. должны путешествовать, чтобы добраться до ближайшего узла, удовлетворяющего следующему предикату в цепочке (первый подход был бы легким, если бы вы знали, что пути всегда были очень частыми или очень редкими, но из-за отсутствия такой информации мы застряли в худшем случае для в настоящее время). Некоторые подходы, которые мы изучаем, - это более разумное кэширование подпути или использование диаграмм двоичных решений с нулевым подавлением, которые ранее использовались для подсчета путей в графах. Но пока рано.

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

Спасибо, что посмотрели еще один захватывающий выпуск блога Lab41. Увидимся в следующий раз!

Первоначально опубликовано на www.lab41.org Кабиром С. 3 марта 2015 г.