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

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

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

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

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

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

Отсутствие глобального перекрытия границ (т.е. перекрытие границ, вызванное свойствами межкластера, не совсем нормально)
Локальное перекрытие края внутри кластера прекрасно

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

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

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

Ответ 1

Prefuse имеет хороший графический чертеж текст текста, встроенный в него, и он, по-видимому, обрабатывает довольно большие графики относительно хорошо. Вы можете попробовать Layout Map Layout, который построен поверх Prefuse.

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 6

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