Визуализация кластерной структуры - Визуализация графа цитирования

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

Для начала введем требования к визуализации:

    1. Визуализация кластера должна содержать только его вершины 2. Должно быть легко определить, находятся ли вершины в одном кластере 3. Кластеры должны быть легко различимы 4. Кластер должно быть просто найти

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

B. Alsallakh, L. Micallef, et al [16] ввели разные типы техник визуализаций в своем обзоре. Некоторые техники, такие как диаграммы Венна не могут быть применены для нашего случая, так как они визуализируют метаинформацию об объектах и не могут учитывать их положение в пространстве. Для нашей задачи больше всего подходят методы типа "оверлеи", так как они создают визуализацию поверх уже предварительно отрисованного множества. У нас отрисованное множество объектов будет после того, как сработает алгоритм расположения вершин на плоскости.

Оверлеи в свою очередь поделены авторами статьи еще на 3 категории.

Первая категория использует цветовые глифы - графические символы при отображении информации. Глифы наносятся на каждую вершину, например, круглая вершина может быть разделена на цветные секторы, где цвет обозначает кластер, к которому принадлежит вершина, как показано на рис. 3. Такой тип визуализации удовлетворяет только первому требованию, так как увеличением количества кластеров глифы начнут визуально смешиваться, а с увелечением количества вершин - сложнее будет выделить все множество вершин, входящих в кластер.

визуализация кластерной структуры при помощи глифов [16]

Рисунок 3. Визуализация кластерной структуры при помощи глифов [16]

Вторая категория оверлеев - это использующая линии. Линии связывают все элементы множества, проходя через них. Этот метод позволяет максимально аккуратно включать в визуализацию кластера только его элементы. Однако у этого метода есть проблемы - во-первых линии могут начать смешиваться с уже отображенными ребрами графа, а также линию может быть не так просто найти и отследить ее ход на больших графах. Примером подобной техники являет алгоритм Kelp Diagrams [17]. Пример ее применения показан на рис. 4.

kelp diagrams [18]

Рисунок 4. Kelp Diagrams [18]

Третья категория - основанная на областях пространства. Такие техники используют замкнутые кривые, чтобы обвести все элементы множества. Эти кривые могут расширяться и сужаться до линий тем самым включая в себе преимущество предыдущей категории. Такие регионы легко различимы на плоскости и способны работать с любой геометрией элементов. Среди таких методов можно выделить Bubble Sets [18]. На рис. 5 показан пример результата работы такого метода.

bubble sets [18]

Рисунок 5. Bubble Sets [18]

kelpfusion [18]

Рисунок 6. KelpFusion [18]

К последней категории относятся смешанные техники, использующие приемы из других категорий. Одним из примеров является KelpFusion [19], являющийся смесью Kelp Diagrams и Bubble Sets, как показано на рис. 6.

Похожие статьи




Визуализация кластерной структуры - Визуализация графа цитирования

Предыдущая | Следующая