Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования

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

При постановке задачи для расположения вершин кластеризованных графов добавляется еще одно требование:

Вершины, находящиеся в одном кластере должны находится близко друг у другу и vice versa.

В качестве примера алгоритма, расставляющего вершины иерархически-кластеризованного графа, рассмотрим алгоритм Eades and Huan (2000) [15]. Этот алгоритм является силовым, также, как и вышеописанные, однако в нем присутствуют адаптации к иерархически-кластеризованным графам. Прежде всего кластеризованный граф С Делится на уровне абстракции на два обычных графа G И T. Граф G Представляет собой граф С, если бы последний не был кластеризован, то есть он состоит из тех же вершин и ребер между ними. Граф T - это дерево кластеров. Каждая вершина (не лист) графа представляет собой кластер, и она связана со всеми кластерами и вершинами, входящими в нее, а также с кластером в который она сама входит, если такие имеются. Листом графа является вершина из G. Так как классификация является иерархической - то T Является деревом.

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

    1. Внутренние пружины. Они связывают пару связанных вершин из G Если у них общий непосредственный предок в T. 2. Внешние пружины. Они связывают пару связанных вершин из G Если у них не общий непосредственный предок в T. 3. Виртуальные пружины. Для каждого кластера U создается виртуальная вершина. С ней связываются все вершины из G, Если их предком в T Является U.

Тем самым все вершины внутри кластера связаны внутренними и внешними пружинами, а между кластерами - внешними.

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

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




Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования

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