Какой самый быстрый механизм направленного сетевого графа для больших наборов данных?

Question

В настоящее время у нас есть динамически обновляемый сетевой график, содержащий около 1500 узлов и 2000 ребер . Это постоянно растет. Наш текущий механизм компоновки использует Prefuse - в частности, макет с принудительным управлением - и требуется около 10 минут с здоровенным сервером, чтобы получить хороший, стабильный макет.

Я посмотрел немного GraphViz алгоритм sfpd, но еще не проверял его ...

Есть ли более быстрые альтернативы, на которые мне следует обратить внимание?

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

Заранее спасибо, пожалуйста, прокомментируйте, если вам нужна более конкретная информация, чтобы ответить!

РЕДАКТИРОВАТЬ: Я особенно ищу сравнения скорости между параметрами двигателя макета. Достаточно тестов, конкретных примеров или просто личного опыта!

Answer 1

Я написал библиотеку для рисования графиков на основе JavaScript VivaGraph.js .

Он рассчитывает макет и визуализирует график с 2K + вершинами, 8,5K ребрами за ~ 10-15 секунд.Если вам не нужна отрисовка, она должна быть еще быстрее.

Вот видео, демонстрирующее это в действии: Рендеринг графика WebGL с VivaGraphJS .

Демо-версия доступна здесь .WebGL требуется для просмотра демонстрации, но не нужен для расчета макетов графиков.Библиотека также работает в node.js , поэтому ее можно использовать в качестве службы.

Пример использования API (только макет):

var graph = Viva.Graph.graph(),
    layout = Viva.Graph.Layout.forceDirected(graph);

graph.addLink(1, 2);
layout.run(50); // runs 50 iterations of graph layout

// print results:
graph.forEachNode(function(node) { console.log(node.position); })

Надеюсь, это поможет:)

Answer 2

Я бы посмотрел на OGDF, в частности http://www.ogdf.net/doku.php/tech:howto:frcl Я не использовал OGDF, но я знаю, что Fast Multipole Multilevel является хорошим быстродействующим алгоритмом, и когда вы имеете дело с типами сред выполнения, связанных с принудительно-ориентированным макетом, с количеством нужных вам узлов, это очень важно. Почему, помимо прочего, этот алгоритм является удивительным: метод Fast Multipole. Быстрый мультипольный метод - это приближение умножения матриц, которое сокращает время выполнения O () умножения матриц для аппроксимации в небольшой степени. В идеале, у вас должен быть код, например, такой: http://mgarland.org/files/papers/layoutgpu.pdf, но я нигде не могу его найти; может быть, решение CUDA все равно не по твоему пути.

Удачи.

Answer 3

Возможно, вам нужен Gephi Toolkit: некоторые макеты очень быстрые, но с хорошим качеством: http://gephi.org/toolkit/

От 30 секунд до 2 минут достаточно для построения такого графика, в зависимости от вашей машины. Вы можете использовать макет ForAtlas или многоуровневый макет Yifan Hu.

Для очень больших графиков (+ 50К узлов и 500К ссылок) макет OpenOrd будет

Answer 4

В коммерческом сценарии вы также можете обратиться к семейству yFiles библиотек макетов и визуализации графиков.

Даже его версия JavaScript может выполнять макеты для тысяч узлов и ребер, используя различные стили размещения.«Органический» стиль компоновки представляет собой реализацию алгоритма форсированного макета, по своей природе похожего на тот, который используется в браузерном приложении Neo4j.Но есть намного больше доступных алгоритмов компоновки, которые могут дать лучшую визуализацию для определенных типов структур и диаграмм графа.В зависимости от настроек и структуры проблемы, некоторые алгоритмы занимают всего несколько секунд, в то время как более сложные реализации также могут поставить ваш движок JavaScript на колени.Варианты, основанные на Java и .net, на сегодняшний день все еще работают немного лучше, но движки JavaScript догоняют.

Вы можете поиграть с этими алгоритмами и настройками в этой онлайн-демонстрации .

^{Отказ от ответственности: я работаю на yWorks, которая является производителем этих библиотек, но я не представляю своего работодателя на SO.}

Answer 5

Я бы посмотрел на http://neo4j.org/ его открытый исходный код, который полезен в вашем случае, поэтому вы можете настроить его под свои нужды.Аккаунт github можно найти здесь .