Визуализация графа цитирования

Размещено на http://www.allbest.ru/

Визуализация графа цитирования

Грязнов Н.В.



Оглавление

• Введение
• Глава 1. Обзор предметной области
• 1.1 Графы цитирования
• 1.2 Постановка задачи
• 1.3 Существующие решения
• 1.4 Автоматическое расположение вершин на плоскости
• 1.5 Силовые алгоритмы расположения вершин на плоскости
• 1.6 Улучшения классических силовых алгоритмов
• 1.7 Силовые алгоритмы для иерархически-кластеризованных графов
• 1.8 Визуализация кластерной структуры
• Глава 2. Визуализация графов цитирования
• 2.1 Автоматическая расстановка вершин на плоскости
• 2.2 Визуализация кластерной структуры. Bubble Sets
• Глава 3
• 3.1 Клиентская программа
• 3.1.1 Инструменты разработки
• 3.1.2 Canvas
• 3.1.3 Геометрические примитивы
• 3.1.4 Реализация алгоритма расположения вершин графа
• 3.1.5 Реализация визуализации анимации алгоритма
• 3.2 Серверная программа
• 3.2.1 Инструменты разработки
• 3.2.2 Получение графов цитирования из IEEE Xplore Digital Library
• 3.2.3 Общение с клиентской программой
• Заключение
• Список используемых источников
• Основные определения, термины и понятия

Введение

В данной работе рассматриваются методы автоматической и полуавтоматической визуализации графов цитирования на плоскости.

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

Можно выделить несколько основных проблем, которые возникают во время управления используемыми статьями:

· Каждый из исследователей хранит у себя набор статей, который он использует. Этот набор, как правило не доступен и не понятен другим соавторам. В связи с этим не формируется единое поле используемого материала, которое может помочь каждому из участников.

· Статьи хранятся в плоском или строго иерархическом виде. То есть либо статьи где-то сваливаются в одну большую кучу, навигация по которой ухудшается с каждой добавленной туда новой статьей. Либо публикации хранятся в дереве категорий (например, в файловой системе), где нет возможности увидеть все статьи сразу и выделить какие-либо связи между статьями в различных категориях.

· Нет возможности посмотреть отношения между статьями через цитирование. Визуализация этих отношений позволяет выделить основные и вторичные статьи в научных сферах.

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

1. Исследовать текущие подходы к визуализации графов цитирования

2. Изучить алгоритмы расположения графа на плоскости

3. Выбрать алгоритмы визуализации кластерной структуры графа

4. Разработать программу визуализации графов цитирования

5. Разработать техническую документацию.

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



Глава 1. Обзор предметной области

1.1 Графы цитирования

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

Альтернативой дереву и списку является более общая структура - ориентированный граф. Граф - это совокупность набора вершин и набора ребер между ними. В самом деле, каждая серьезная научная статья, прошедшая рецензирование и публикацию, содержит в себе ссылки (references) на используемы работы. Эти ссылки вмести со статьями можно рассматривать как граф, где каждая вершина - это статья, а ссылка из одной статьи на другую - это ребро между ними.

Также дополнительно каждая статья может относиться к различным категориям. Ими могут быть научные области, с которыми связана работа (биология, физика, компьютерная лингвистика и т.д.) или дата публикации. Здесь стоит отметить, что существует большое количество работ находящихся на периферии разных областей, и поэтому каждая публикация может находится в нескольких категориях одновременно. Далее мы будем называть множество публикаций, находящихся в одной категории, кластером, а категории, к которыми отнесена статья, - метками. Это связано с тем, что в дальнейшем разделение публикаций на кластеры может быть установлено исследователями не по каким-то известным категориям, а по произвольным, подходящим самим исследователям. Сам же граф цитирования будет называться мягко кластеризованным (англ. "softly clustered"): слово "мягко" - здесь означает, что каждый объект-вершина может относиться к нулю, одной или нескольким категориям, в противовес понятию жестко кластеризованный, где все объекты могут относиться только к одной категории.

1.2 Постановка задачи

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

Следующие задачи должны быть решены для успешной визуализации графа:

1. Отрисовать граф на плоскости. Это самая базовая задача, в которой надо отрисовать на плоскости граф, для которого уже даны все данные. Граф должен быть отрисован в максимально понятном человеку виде. Эта глобальная задача включает в себя нижеописанные задачи.

2. Расположить автоматически вершины на плоскости, в удобном и эстетическом виде. Вершины должны располагаться с учетом, как связей в графе, так и его кластерной структуры. То есть связанные вершины и вершины, находящиеся в одном кластере, должны находится рядом и vice versa.

3. Выделить кластерную структуру графа. Необходимо показать в понятном виде какие вершины к какому кластеру относятся. Помимо этого, также должны быть видны сами кластеры, то есть вершины должны быть выделены как группа, а не по отдельности.

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

Далее, сперва мы расскажем об уже существующих средствах для решения поставленных задач, а после этого описать подходы, которые позволяют их достигнуть. Естественно эти подходы так или иначе использованы в существующих решениях.

1.3 Существующие решения

На данный момент не было найдено решений, которые полностью бы удовлетворяли всем требованиям, однако существуют те, которые реализуют их не все и/или не в полной мере.

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

Другой хорошей альтернативой является СiteSpace [2]. СiteSpace разработан экспертом по визуализации данных и профессором Dexel University в Америке Chaomei Chen. CiteSpace также, как и VOSviewer не поддерживает визуализацию мягко кластеризованного графа цитирования, однако имеет множество различных видов и стилей представления жестко кластеризованных графов. В связи с этим его можно использовать как пример качественной визуализации.

Все остальные инструменты, как для отрисовки графов цитирования (Papercube [3], SciMAT [4]), так и для отрисовки произвольных графов (Gephi [5], graph-tool [6]), также не удовлетворяют всем требованиям, в особенности о мягкой кластеризации.

В связи с этим далее мы рассмотрим классические подходы к решению поставленных и похожих задач, которые в частности использовались в описанных выше инструментах.

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

Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она была поставлена в первых работах по этой теме.

Пускай нам дан граф, и мы хотим расположить его на двумерной плоскости; пока мы будем рассматривать графы без кластеризации. Основным препятствием к достижению цели является то, что как правило граф не содержит какой-либо пространственной информации и содержит только объекты и связи между ними. Для нас важно не просто расположить граф в случайном порядке, а сделать его максимально информативным и эстетически приятным для человеческого восприятия. Введем требования для алгоритма, которые позволят этого достичь [7]:

1. Между вершинами графа должно быть достаточно расстояния.

2. Связанные вершины должны находится рядом с друг другом, не связанные - в отдалении.

3. Ребра не должны пересекаться.

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

1.5 Силовые алгоритмы расположения вершин на плоскости

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

История силовых начинается с алгоритма Tutte в 1963 для планарных графов [8]. Однако современные подходы больше похожи на алгоритм, предложенный Peter Eades [9] в 1984. Основная идея была в том, чтобы представить вершины как стальные кольца, а ребра как пружины между ними. В начале работы алгоритма всем вершинам присваивалось случайное положение на плоскости. После этого запускалась симуляция физической системы, в которой силы упругости приводят систему в состояние с минимальной энергией. На рис. 1 схематично проиллюстрирована работа алгоритма такого типа.

Рисунок 1. Работа силового алгоритма [7]

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

,

где - это длина пружины а и - константы. Обычно понимается, как идеальная длина пружины (ее длина, когда на нее не действуют никакие силы), так как при сила будет равна 0. Вторым улучшением было добавление отталкивающей силы между несвязанными вершинами. Для этой силы использовалась следующая формула:

,

где - это константа, а - это расстояние между вершинами.

На каждом шаге алгоритма высчитывалась суммарная сила , действующая на каждую вершину, и потом вершина перемещалась на расстояние , где - маленькая константа (размер шага). Количество шагов также было константным.

В 1991 году Thomas Fruchterman и Edward Reingold улучшили этот алгоритм и в честь них он получил название Fruchterman-Reingold [10]. Этот алгоритм получил большую популярность и используется сейчас в таких больших системах и библиотеках как Gephi, graph-tool, d3, Boost Graph и другие.

Этот алгоритм имеет дополнительные наработки по сравнению с алгоритмом Eades. Во-первых, силы притягивания (силы упругости) и силы отталкивания считались немного по другому:

,

,

где - это расстояние между вершинами, а - это оптимальное расстояние между ними, определяемая следующим образом:

,

где - это константа, - это площадь рабочей области в которой должны находится все вершины, а - это количество вершин.

Во-вторых, этот алгоритм вводит понятие температуры, которой устанавливается вначале какое-то начальное значение, а потом она линейно уменьшается линейно до 0. Когда температура достигла 0, алгоритм завершает свою работу. Температура контролирует максимальное расстояние, на которое может передвинуться вершина на каждом шаге.

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

1.6 Улучшения классических силовых алгоритмов

Первым улучшением является добавление псевдо-гравитационной силы [11]. Эта сила притягивает все вершины к центру рабочей области. Обычно она линейна относительно расстояния, в отличие от обыкновенной гравитационной силы которая является обратно-квадратичной. Эта сила позволяет решить сразу две проблемы; первая - это то, что она стягивает граф в видимую область и не позволяет ему "уехать" за ее грани во время симуляции, вторая - это то, что она не дает несвязанным подграфам удалиться слишком далеко от центра.

Вторым улучшением является добавление силы трения [11]. Эта сила также является псевдо-силой в том понимании, что она не соответствует силе трения в реальном мире. Обычно она действует линейно на скорость уменьшая ее в определенное количество раз на каждом шаге алгоритма. Тем самым она позволяет не разгоняться вершинам слишком быстро, что часто бывает проблемой при работе подобных алгоритмов.

Также стоит упомянуть два метода, один из которых позволяет улучшить точность симуляции, а второй уменьшить ее вычислительную сложность.

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

Самый простой способ решения - это воспользоваться методом Эйлера [12]. Он не сильно отличается от того, что мы делали раньше. Теперь для каждой вершины вводится понятие скорости, равной изначально 0. На каждом шаге мы вначале находим скорость как:

,

и только после этого вычисляем новые координаты:

.

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

Поэтому чаще всего используют более сложный способ интегрирования - интегрирование Верле [13]. На каждом шаге, вначале высчитывается положение для следующего момента времени:

,

далее считается скорость:

.

Если есть информация о массе вершины , то сила заменяется на ускорение:

.

Этот метод более стабильный, чем метод Эйлера и позволяет использовать больший шаг.

Теперь необходимо сказать о сложности алгоритма расположения вершин. На каждом шаге алгоритма для каждой из N вершин необходимо посчитать силы, действующие на нее со стороны остальных N-1 вершин. Соответственно вычислительная сложность на каждом шаге . Такой алгоритм будет медленно работать даже на сравнительно небольших графах, что неприемлемо для real-time задач и ухудшает user experience.

Для решение данной проблемы используется алгоритм аппроксимации симуляции динамической системы Барнса-Хата [14]. Он позволяет выполнить симуляцию за вместо Этот алгоритм используется полностью на каждом шаге симуляции.

Первый шаг алгоритма Барнса-Хата - это построение квадродерева. Квадродерево рекурсивно делит рабочую область на 4 квадрата, называемых "квадрантами", пока внутри не будет нуля или одной вершины. Тес самым мы получаем дерево, в котором каждый узел - это квадрант и имеет 4 потомка (пример дерева на рис. 2). Сложность построения такого квадродерева . Во время построения дерева считается центр масс и масса каждого узла из всех объектов в его поддереве.

Рисунок 2. Квадродерево из 4 точек. Слева - разбиение плоскости на квадранты, справа - представление точек и квадрантов в виде дерева

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

Узким местом этого алгоритма является понятие "достаточно далеко". Для его определения вводится эмпирический параметр . Если он больше отношения ширины узла к расстоянию от тела до центра масс узла, то узел считается "достаточно далеким". Фактически параметр позволяет управлять балансом между точностью и скоростью аппроксимации. Если имеет большое значение, то алгоритм будет работать быстро но с плохой точностью, а если близка к 0, то наоборот.

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

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

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

Вершины, находящиеся в одном кластере должны находится близко друг у другу и 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).

1.8 Визуализация кластерной структуры

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

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

1. Визуализация кластера должна содержать только его вершины

2. Должно быть легко определить, находятся ли вершины в одном кластере

3. Кластеры должны быть легко различимы

4. Кластер должно быть просто найти

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

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

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

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

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

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

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

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

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

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

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



Глава 2. Визуализация графов цитирования

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

Для автоматической расстановки вершин использовался алгоритм основанный на работах 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

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

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

2.2 Визуализация кластерной структуры. Bubble Sets

Для визуализации кластерной структуры был выбран алгоритм Bubble Sets [18]. Это гибкий алгоритм, относящийся к оверлеям, основанным на областях пространства (см. Главу 1). Этот алгоритм в большей степени удовлетворяет требованиям к кластерной визуализации. Он способен, как учитывать графовую структуру множеств, на которых он работает, так и не учитывать.

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

Контур, иначе называемый "пузырь", описывается, как функция от двух переменных.

.

Здесь функция E понимается, как энергия пикселя с координатами x, y. А с как потенциальная энергия. Если функция E непрерывна, то и контур будет непрерывным.

Абстрактно шаги алгоритма для каждого кластера можно описать следующим образом:

1. Для каждого объекта из кластера ищем оптимально соседа (также объекта из кластера), и строим между ними ломанное виртуальное ребро, по возможности, избегающее элементов не из кластера.

2. Считаем потенциальную энергию каждого пикселя. Под "пикселем" понимается группа реальных пикселей, размер которой дает баланс между производительностью и точностью: чем больше группа - тем меньше точность, но выше скорость выполнения.

3. С помощью алгоритма Marching squares выделяем контур, уменьшая пороговое значение (параметр алгоритма) пока все элементы кластера не будут внутри, или пороговое значение не достигнет 0.

4. Рисуем полученный пузырь с помощью сплайнов.

Теперь подробно рассмотрим эти шаги. Значения и являются параметрами алгоритма, их значение будет объяснено нижу..

Для начала нужно создать виртуальные ребра (virtual edges), которые будут учитываться при подсчете энергии. Ребра должны проложить путь, избегая препятствий. Препятствием считается объект, не входящий в кластер.

Предварительно устанавливаем прямоугольную рабочую область в которую входят все элементы кластера + дополнительное место во все стороны равное . Далее мы работаем только с объектами, находящимися внутри найденной области или пересекающих ее. Также необходимо найти центроиду кластера.

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

.

где distance - минимальное расстояние между границами объектов, а obstacles - количество объектов-препятствий, не входящих в кластер, на пути ребра.

Далее мы проверяем полученное ребро на пересечение с объектами, не входящими в кластер. Если оно найдено мы ломаем ребро в контрольной точке так, чтобы избежать пересечения, если это возможно. Эта точка выбирается на расстоянии длинной от до 0 от угла препятствия. Углы и расстояния перебираются, пока контрольная точка находится в каком-либо препятствии. Если какая-либо часть сломанного ребра имеет пересечения с препятствиями, алгоритм применяется к ней рекурсивно. Этот процесс проиллюстрирован на рис. 7.

Рисунок 7. Процесс создание виртуального ребра [19]

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

Следующим шагом алгоритма является вычисление энергии. Для вычисления энергии вначале пространство разбивается на группы пикселей (обычно 9х 9 или 3х 3).

Потенциальная энергия группы пикселей (далее просто "пиксель) считается следующим образом:

.

,

где - расстояние, где энергия равна 1, - расстояние, где энергия достигает 0 (эти параметры эвристические, их надо подбирать). - все элементы, влияющие на энергию пикселя. - веса, присвоенные элементам. - расстояние между границами объекта.

Веса элементам присваиваются следующим образом:

· Ребрам (как виртуальным, так и структурным) и объектам из кластера присваивается вес 1

· Объектам, не входящим в кластер -0.8

· Ребрам не из кластера присваивается вес 0.

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

После вычисления энергии необходимо получить контур. Для этого используется алгоритм Marching squares. Вначале алгоритм бинаризует все значения пикселей. Если значение энергии меньше порогового значения, то значение пикселя приравнивается 0, иначе 1. Далее строится сетка в узлах которой находятся бинаризованные пиксели. Каждой ячейке сетки выдается номер, получаемый из значений в ее узлах. Далее полученный номер сравнивается со значением в специальной таблице, в которой каждому номеру сопоставляется, что надо отрисовать в ячейке сетки. Таким образом выстраивается пузырь. Если контур содержит все не объекты из кластера, то алгоритм повторяется с другим пороговым значением.

Последним этапом алгоритма является отрисовка самих пузырей. Для этого выбирается каждая 10-ая (возможны другие значения) точка из контура и между ними строится кубический сплайн.

Глава 3

В данной главе будут рассмотрены основные аспекты имплементации программы и алгоритмов, которые она использует. Сама программа состоит из двух частей - клиентской (основной) и серверной. О каждой из них будет написано отдельно.

3.1 Клиентская программа

Клиентская программа - является основной частью программы, так как она реализует все алгоритмы, описанные в главе 2 данного документа. Несмотря на то, что клиентская часть программы зависит от серверной, реализуемые алгоритмы были спроектированы максимально независимо.

3.1.1 Инструменты разработки

Основная часть работы написана, как веб-приложение, на языках программирования HTML, CSS и JavaScript. Эти языки являются стандартным набором при создании веб страниц, так как их умеют интерпретировать все современные браузеры. Во время разработки использовались их последние стандарты, поскольку они описываю функции, позволяющие удобно работать с графикой и данными.

Во время работы использовались библиотеки Require.js [21], jQuery [22], cardinal-spline-js [23], Bootstrap [24].

Require.js реализует спецификацию AMD [25] (Asynchronous module definition), позволяющую организовывать JavaScript проект в виде асинхронных модулей. Модуль - это JavaScript код, имеющий другие модули в качестве зависимостей и имеющий возможность подключения в качестве зависимости. Модули асинхронно подключаются с помощью библиотеки по мере их надобности, поэтому нет необходимости в том, чтобы прописывать ссылки на все файлы в HTML коде вручную. Такая практика позволяет легко менять, добавлять, удалять модули и масштабировать приложение. В данной программе почти все модули написаны по принципу "Один модуль - один класс", так как это позволяет поддерживать объектно-ориентированный стиль программирования.

jQuery - мультифункциональная библиотека, упрощающая взаимодействие HTML и JavaScript, облегчающая работу с AJAX и т.д. В данной работе jQuery использовался для создания, управления DOM элементами страницы и написания обработчиков событий. Здесь стоит отметить, что jQuery позволяет работать со слабо-стандартизированными функциями во всех основных браузерах одинаково. Также jQuery использовался для общения с сервером посредством AJAX.

Cardinal-spline-js - маленькая библиотека, строящая кардинальный сплайны по точкам. В частности, она может расширять функционал элемента Canvas, отрисовывая сплайны сразу на нем. Ее функционал используется в конечном этапе алгоритма Bubble Sets.

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

Так как программа писалась на последних версиях языка JavaScript встал вопрос поддержки браузеров, еще не реализовавших новый функционал. Для решения данной проблемы использовался инструмент Babel состоящий из JavaScript компилятора и библиотеки полифила. Компилятор преобразовывал код написанный на ES6 таким образом, чтобы он полностью соответствовал предыдущему стандарту - ES5, но выполнял те же функции. Компилятор может преобразовывать синтаксис кода, однако не переменные и классы. Поэтому компилятор используется в связке с библиотекой полифилом, подключающейся на странице. Эта библиотека добавляет недостающие классы, функции и т.д. на страницу.

3.1.2 Canvas

Визуализация в браузере производилась с помощью элемента <canvas> представленного в HTML5 и соответствующего JavaScript Canvas API. Элемент canvas позволяет отрисовывать на нем произвольную графику на ходу с помощью JavaScript. В нем уже есть встроенная поддержка таких графических элементов, как отрезок, прямоугольник, многоугольник и т.д. Также canvas поддерживает трансформации, основанные на матрицах перехода. Такие трансформации, как перемещение начала координат и увеличение/уменьшение позволяют реализовывать удобный пользовательский интерфейс для визуализации.

Альтернативой Canvas является векторный формат SVG. SVG представляет из себя <svg> элемент в HTML, внутри которого каждый графический элемент является отдельной DOM вершиной. Тем самым SVG позволяет удобно оперировать графическими элементами также, как и всеми остальными на странице. Однако узким местом данного подхода является скорость отрисовки, при анимации. В отличие от растрового canvas SVG при обновлении берет на себя дополнительно все накладные расходы по изменению DOM структуры и поэтому является менее предпочтительным в таких ситуациях.

3.1.3 Геометрические примитивы

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

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

3.1.4 Реализация алгоритма расположения вершин графа

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

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

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

3.1.5 Реализация визуализации анимации алгоритма

При работе алгоритма расположения вершин графа необходимо анимировать изменения графа в режиме реального времени. Для этого используется специальная функция JavaScript requestAnimationFrame(callback). В эту функцию передается другая функция, содержащая логику и выполняющая отрисовку одного кадра. Эта функция выполняет несколько операций tick(), количество вызовов которой определяет скорость с которой будут двигаться вершины на экране. Чем больше вызовов tick() за один вызов requestAnimationFrame, тем быстрее работает алгоритм, однако при слишком большом количестве могут начаться видимые задержки.

Далее высчитываются и обрисовываются все кластеры с помощью алгоритма Bubble Sets. Здесь стоит отметить, что во время работы алгоритма расположения вершин используется размер группы пикселей равный 9, а не 3 как после завершения, так как это позволяет отрисовывать кластеры с значительно меньшей нагрузкой на процессор, что критично для задачи, работающей в реальном времени

В конце опять вызывается requestAnimationFrame, если алгоритм не достиг точки останова.

3.2 Серверная программа

Серверная программа - это веб-сервер, необходимый для получения и хранения графов. Сервер может создавать графы цитрования из библиотеки IEEE Xplore Digital Library [26], манипулировать ими и общаться с клиенткой программой.

3.2.1 Инструменты разработки

Сервер написан на языке Java версии 1.8 с использованием системы сборки Maven [27], библиотек и фреймворков Spring Boot [28], Spring MVC [29], Spring Data JPA [30], Jsoup [31] и Apache HttpComponents Client [32]. Также использовалась система управления базами данных PostgreSQL [33].

Основой приложения является универсальный фреймворк Spring Famework. Он состоит из множества компонент, работающих в единой экосистеме. Эти модули реализуют такие функции как Dependency Injection, управление транзакциями, систему авторизации и.т.д. Далее будут описаны детально модули, использующиеся в данном веб-сервере.

Обычно приложения, написанные с использованием Spring, являются Java веб-приложениями, работающими в каком-либо контейнере сервлетов, например, в Apache Tomcat. Однако для этого требуется установка и настройка самого контейнера, а также зачастую однотипная начальная настройка приложения, что является, по большому счету, излишними накладными расходами. В связи с этим был разработан Spring Boot, содержащий в себе уже настроенные встроенный контейнер сервлетов и компоненты Spring. По умолчанию контейнером является Apache Tomcat, однако его можно поменять на Jetty или Undertow. В данном проекте используется сервер по умолчанию. Также есть возможность выбора подключаемых модулей, через систему сборки Maven.

Тем самым Spring Boot приложение упаковывается (по умолчанию) не в war файл, который может запустить только контейнер сервлетов, а в jar файл, который запустится одинаково на любом компьютере, где есть Java необходимой версии.

Для работы с HTTP запросами используется компонент Spring MVC. Он позволяет обрабатывать и отвечать на запросы, добавляя такую функциональность, как гибкую систему маршрутизации URL путей, автоматическая сборка объектов из параметров запросов, конвертация ответа из объекта в JSON и т.д. За обработку отвечают классы, называемые "контроллерами". Контроллеры пишутся с максимально меньшим включением в них логики, которая выносится в классы, называемые "сервисами" и вызываемые контроллерами.

Сервисы содержат и инкапсулируют в себе всю бизнес логику приложения. На каждую операцию, которую пользователь захочет произвести пользователь с системой как правило должен быть специальный метод в каком-либо сервисе. Если метод сервиса обращается к базе данных, то весь метод оборачивается в транзакцию. Компонент Spring Data JPA позволяет это сделать просто пометив метод специальной Java аннотацией, в случае если подключение к базе данных происходить через JPA [34] (Java Persistence API).

Spring Data JPA значительно упрощает работу с базой данных через интерфейс JPA. JPA - Java API предоставляющий интерфейсы для сохранения объектов (сущностей) в базе данных (предполагается, что в реляционной) и загрузки данных из базы обратно в объекты. В данном проекте используется одна из самых популярных реализаций JPA - Hibernate. Все обращения к базе (базам) данных как правило реализуются в классах-репозиториях Репозитории - это классы, которые инкапсулируют обращение к базе данных без какой-либо дополнительной логики. Как правило на одну сущность пишется один класс-репозиторий.. Spring JPA позволяет создавать интерфейсы-репозитории не реализуя их. Все, что необходимо сделать - это создать интерфейс, наследующийся от интерфейса Repository и далее подключить его в сервисе с помощью Dependency Injection, которое поставляет ядро Spring Framework.

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

3.2.2 Получение графов цитирования из IEEE Xplore Digital Library

Чтобы построить граф цитирования из библиотеки IEEE Xplore Digital Library используется следующий метод. Выбирается статья из библиотеки, далее собираются все статьи, на которые она ссылалась и которые сами присутствуют в IEEE Xplore Digital Library. Далее для каждой из статей-ссылок собираются их ссылки и по ним добавляются ребра между статьями. Таким образом мы получаем подмножество реальных данных которое могло бы быть создано исследователями, пользующимися программой.

Далее будет описан процесс получения информации о статьях и используемых ими ссылках. Каждая статья в IEEE Xplore Digital Library имеет уникальный номер - arnumber. Для получения информации о статье (без ссылок на другие статьи) используется IEEE Xplore Search Gateway. Он имеет HTTP интерфейс и возвращает XML документ, содержащий информацию о названии статьи, ее абстракт, авторов, теги и т.д. Обращение к этому сервису производится с помощью библиотеки Apache HttpComponents Client и далее с помощью библиотеки Jsoup XML ответ разбирается.

Информация о ссылках берется со страницы на сайте IEEE Xplore Digital Library. Страница также разбирается с помощью Jsoup. На ней в разделе References ищутся статьи, находящиеся также в IEEE Xplore Digital Library. Такие статьи имеют ссылку на их страницу в библиотеке.

3.2.3 Общение с клиентской программой

Сервер общается с клиентской программой посредством HTTP протокола, в частности AJAX. AJAX - это обычные HTTP запросы, которые может выполнять браузер в фоновом режиме, не перезагружая страницу.

Данные передаются на сервер с клиента посредством параметров HTTP запроса, если количество передаваемых данных небольшое и данные представляют из себя простую плоскую структуру, или посредством JSON в теле запроса для более сложных данных. Ответом на запросы как правило также является JSON.



Заключение

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

В рамках выполнения выпускной квалификационной работы была разработана программа, визуализирующая мягко кластеризованный граф цитирования. Для этого был разработан и написан алгоритм расположения вершин на плоскости на основе других известных алгоритмов. А также был реализован алгоритм Bubble Sets (2009) для выделения кластерной структуры. Программа была выполнена в виде веб-приложения, состоящего из клиентской и серверной частей.

Также были рассмотрены различные подходы к визуализации графов и кластерных структур. Были изучены различные силовые алгоритмы расположения вершин и их оптимизации. А также был сделан обзор методов выделения кластерной структуры графов и множеств.

Таким образом, в процессе выполнения дипломной работы были решены следующие задачи:

1. Исследованы текущие подходы к визуализации графов цитирования

2. Изучены алгоритмы расположения графа на плоскости

3. Выбран алгоритм визуализации кластерной структуры графа

4. Разработана программа визуализации графов цитирования

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

Список используемых источников

[1] VOSviewer, "VOSviewer - Visualizing scientific landscapes," 2016. [В Интернете]. Available: http://www.vosviewer.com/. [Дата обращения: 28 04 2015].

[2] Cluster.cis.drexel.edu, "CiteSpace: visualizing patterns and trends in scientific literature," 2016. [В Интернете]. Available: http://cluster.cis.drexel.edu/~cchen/citespace/. [Дата обращения: 28 04 2015].

[3] Papercube.peterbergstrom.com, "Papercube," 2016. [В Интернете]. Available: http://papercube.peterbergstrom.com/. [Дата обращения: 28 04 2016].

[4] Herrera, "SciMAT - Science Mapping Anaylsis Tool," 2016. [В Интернете]. Available: http://sci2s.ugr.es/scimat/. [Дата обращения: 28 04 2016].

[5] Gephi.org, "Gephi - The Open Graph Viz Platform," 2016. [В Интернете]. Available: https://gephi.org/. [Дата обращения: 25 05 2016].

[6] Tiago, "graph-tool: Efficent network analysis with python," 2016. [В Интернете]. Available: https://graph-tool.skewed.de/. [Дата обращения: 28 04 2016].

[7] Kobourov, " [1201.3011] Spring Embedders and Force Directed Graph Drawing Algorithms," 14 01 2012. [В Интернете]. Available: http://arxiv.org/abs/1201.3011. [Дата обращения: 28 04 2016].

[8] Tutte, "How to Draw a Graph," Proceedings of the London Mathematical Society, Т. %1 из %23-13, № 1, pp. 743-767, 1963.

[9] Eades, "A heuristics for graph drawing," Congressus numerantium, т. 42, pp. 146-160, 1984.

[10] Fruchterman и Reingold, "Graph drawing by force-directed placement," Software: Practice and Experience, т. 21, № 11, pp. 1129-1164, 1991.

[11] d3, "Layouts * mbostock/d3 Wiki," 2016. [Online]. Available: https://github.com/mbostock/d3/wiki/Layouts. [Accessed 28 04 2016].

[12] Ascher и Petzold, Computer methods for ordinary differential equations and differential-algebraic equations, Philadelphia: Philadelphia: Society for Industrial and Applied Mathematics, 1998.

[13] Verlet, "Computer "Experiments" on Classical Fluids. I. Thermodynamical Properties of Lennard-Jones Molecules," Phys. Rev., т. 159, № 1, pp. 98-103, 1967.