Визуализация графов цитирования, Автоматическая расстановка вершин на плоскости - Визуализация графа цитирования

Автоматическая расстановка вершин на плоскости

Для автоматической расстановки вершин использовался алгоритм основанный на работах Eades [9], Fruchterman-Reingold [10] и Omote and Sugiyama (2007) [20]. Это силовой алгоритм, позволяющий автоматически размещать на плоскости вершины мягко-кластеризованного графа.

Этот алгоритм имеет схожий принцип работы с алгоритмами, описанным во второй главе. Как любой силовой метод, идея заключается в симуляции физической системы, состоящей из объектов и сил между ними.

На первом шаге мы определяем силы, действующие в системе на вершины. В алгоритме используются 3 различные силы для разного типа соединений между вершинами.

Первая сила - это сила упругости абстрактной пружины между вершинами, связанными ребром. Ее формула:

,

Где - расстояние между вершинами, - положительный коэффициент, а - идеальная длина пружины.

Вторая сила - это сила упругости абстрактной пружины между вершинами, находящимися в одном общем и более кластере. Ее формула:

,

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

.

Последняя сила - это сила отталкивания между любыми двумя вершинами. Ее формула:

,

Где - расстояние между вершинами, - положительный коэффициент.

Также на каждую вершину действуют еще две силы.

Первая сила - это сила гравитации, притягивающая вершины к центру заранее заданной рабочей области. Ее формула:

,

Где - расстояние от вершины до центра, - положительный коэффициент.

Вторая сила - это сила трения, не дающая вершинам разгоняться слишком сильно во время симуляции. Ее формула:

,

Где - скорость вершины, - положительный коэффициент меньший единицы.

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

Работа алгоритма продолжается пока средняя арифметическая скорость всех вершин на каком либо шаге не будет меньше. Размер шага устанавливается эмпирически.

Для этого алгоритма была произведена настройка параметров, на графах цитирования, полученных из электронной библиотеки IEEE Xplore Digital Library. Для получения данных бралась статья из библиотеки и далее из ссылок, которые она указывала, и которые содержатся в вышеуказанной библиотеке, строился граф цитирования. Эти данные хорошо приближены к задаче ВКР, описанной детально в первой главе.

Для описания параметров был введен параметр, описанный Fruchterman-Reingold [9].

,

Где - это площадь рабочей области, а - это количество вершин.

Ниже представлена таблица настроенных параметров:

Таблица 1

10

6

0.025

0.3

0.2

0.01
    * - если обе вершины принадлежат кластерам, в которых больше одной вершины ** - если хотя бы одна вершина не находится ни в каком кластере или находится только в кластерах, состоящих из одной этой вершины

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




Визуализация графов цитирования, Автоматическая расстановка вершин на плоскости - Визуализация графа цитирования

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