Методы визуализации кластерных графов

Question

Мне нужно визуализировать относительно большой граф (6K узлов, 8K ребер), который имеет следующие свойства:

• Отдельные кластеры. Приблизительно 50-100 узлов на кластер и умеренная взаимосвязь на уровне кластера
• Минимальная (5-10 межкластерных ребер на кластер) взаимосвязь между кластерами

Пусть глобальные ребра перекрываются = Ребра перекрываются, вызванные прямой визуализацией графа кластеров = {A, B, C, D, E}, Edges = { Пентаграмма этих кластеров, что не является между прочим, планарная и определенно будет генерировать перекрытие ребер, если вы рисуете его напрямую}

Пусть Local Edge Overlap = выше, но {A, B, C, D, E} - просто узлы.

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

• Нет глобального перекрытия краев (то есть перекрытия краев, вызванные межкластерными свойствами, не в порядке)
• Локальное перекрытие ребер в кластере нормально

У кого-нибудь есть мысли о том, как лучше всего визуализировать график с указанными выше требованиями?

Одним из решений, которое я придумал для борьбы с глобальным перекрытием ребер, является обеспечение того, чтобы кластер A мог иметь максимум 1 прямой ребер к другому кластеру (B) во время визуализации. Любые дополнительные межкластерные ребра между кластером A -> C, A -> D, ... отключаются, а дополнительные узлы / ребра A -> A_C, C -> C_A, A -> A_D, D -> D_A ... созданы.

У кого-нибудь есть мысли?

Answer 1

Хотя в данный момент спрашивать глупо, пробовал ли ты http://www.graphviz.org/?

Answer 2

Существует программа, построенная поверх Prefuse, которая называется SocialAction .Вы должны запросить код у автора, но он выполняет для вас большой статистический анализ, например, определение подграфов.Я использовал его на графике с более чем 18 000 узлов, и хотя он очень медленный в этом масштабе, он все еще работает.

Answer 3

Учитывая ваши цели, я думаю, что алгоритм Fruchterman-Reingold делает довольно приличную работу по предотвращению перекрытия краев. См., Например, этот снимок экрана сети, состоящей из нескольких компонентов, построенных с использованием алгоритма Фрухтермана-Рейнгольда. IGraph имеет встроенную поддержку этого алгоритма (как и Networkx , я полагаю) и действительно быстр.

Answer 4

Prefuse имеет несколько хороших графиков для рисования текст ссылки встроенных алгоритмов, и кажется, что он довольно хорошо обрабатывает довольно большие графы.Вы можете попробовать Схема карты потока , которая построена поверх Prefuse.

Answer 5

Органическая компоновка управляет довольно хорошо кластеризованными графами в среде yFiles. Попробуйте сначала в yEd , чтобы увидеть, делает ли он то, что нужно. Вероятно, разумно использовать группы псевдонимов вложенных графов для каждого кластера. Органическая компоновка имеет функцию, называемую Групповой политикой компоновки, которая может использоваться, если компоновка должна выполняться с использованием различных принципов для межкластерных и внутрикластерных границ с добавочным макетом. С некоторыми усилиями можно перевести график в GraphML, чтобы избежать ручной работы.

Answer 6

Я не видел слишком много инструментов визуализации графа, которые поддерживают визуальное разделение кластеров внутри графа. Один из вариантов - взглянуть на WilmaScope . Похоже, что есть некоторая поддержка макетов на основе кластера.