Содержание к диссертации
Введение
ГЛАВА 1. Средства визуального анализа графа 11
1.1. Программное обеспечение для анализа графов 11
1.2. Многополосное размещение 35
1.3. Визуальный анализ структуры графа взаимодействующих объектов на основе выделения «сообществ» 39
1.4. Выводы по 1 главе 51
ГЛАВА 2. Геометрические модели автоматических размещений объектов графа на плоскости 52
2.1. Базовые геометрические модели автоматического размещений 52
2.2. Геометрическая модель автоматического размещений на основе метода физических аналогий 60
2.3. Многополосное размещение 69
2.4. Выводы по 2 главе 89
ГЛАВА 3. Визуальный анализ графа социальной сети, допускающего выделение подграфов 90
3.1. Методика выделения сообществ 90
3.2. Вычислительные эксперименты 98
3.3. Построение геометрической модели автоматического размещения объектов графа с выделенными сообществами 101
3.4. Выводы по 3 главе 120
ГЛАВА 4. Программный комплекс визуального анализа графов 121
4.1. Общая архитектура программного комплекса 121
4.2. Хранение данных 128
4.3. Используемые структуры данных 132
4.4. Инструменты анализа 139
4.5. Выводы по 4 главе 144
Основные результаты работы 145
Список литературы 147
- Визуальный анализ структуры графа взаимодействующих объектов на основе выделения «сообществ»
- Геометрическая модель автоматического размещений на основе метода физических аналогий
- Построение геометрической модели автоматического размещения объектов графа с выделенными сообществами
- Используемые структуры данных
Визуальный анализ структуры графа взаимодействующих объектов на основе выделения «сообществ»
i2 Analyst s Notebook [37] – визуальная аналитическая среда, позволяющая анализировать, сопоставлять и визуализировать данные из различных источников, там самым уменьшая время на выделение важной информации из данных. Направление анализа связано с выявлением преступной, террористической и мошеннической деятельностей. Основные характеристики: исходный код: недоступен; операционная система: Windows; форматы импорта: csv, txt, xml, xls, doc; интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления; ограничения на визуализацию: официальная информация отсутствует, экспериментальным путем установлено, что для схем с количеством вершин и связей более 10 000, отклик программного продукта при навигации существенно замедляется; алгоритмы авторазмещений: круговое авторазмещение, групповое, иерархическое, временное (упорядоченное и пропорциональное), на основе метода физических аналогий, и размещение, минимизирующее количество пересекающихся связей; дополнительные инструменты анализа: присутствуют.
С точки зрения инструментов визуализации данных, этот продукт предоставляет довольно богатую функциональность: ручное добавление вершин и связей, настройка отображения объектов (цвета, шрифты, иконки, стили), имеет удобные инструменты перемещения и масштабирования по схеме, присутствует возможность добавления атрибутов к объектам на схеме. Имеется возможность отображения множественных связей между вершинами графа. В i2 Analyst s Notebook реализован импорт из различных форматов (csv, txt, xml, xls, doc) данных в виде пошагового мастера, с возможностью визуального пред-просмотра финального результата. В качестве инструментов визуального анализа данное программное обеспечение выделяется большим количеством встроенных алгоритмов автоматического размещение вершин и связей на схеме: круговое авторазмещение, групповое, иерархическое, временное (упорядоченное и пропорциональное), на основе метода физических аналогий, и размещение, минимизирующее количество пересекающихся связей.
Функциональность программы не ограничивается лишь графическим предствлением данных, предоставляя широкой набор инструментов анализа: поиск различных кратчайших путей между вершинами, в том числе и с учетом атрибутов времени, кластеризация для поиска наиболее тесно связанных объектов, поиск объектов, похожих друг на друга по набору заданных условий, поиск объектов не только по значениям атрибутов, но и с помощью генерации графических запросов, построение базовых метрик центральности для вершин и связей. Официальные источники не раскрывают точные цифры по ограничениям на количество объектов для одновременной визуализации в режими реального времени.
Visual Graph [9, 69] – отечественная программа, распространяемая по лицензии BSD, в первую очередь для визуализации атрибутированных иерархических графов. Создаётся в рамках ведущегося в лаборатории конструирования и оптимизации программ ИСИ СО РАН проекта по разработке методов и средств для визуализации сложно структурированной информации большого объема на основе графовых моделей. Программное обеспечение (Рис. 1.5) адаптировано под использование разработчиками систем конструирования программ (компиляторы) для визуализации структур данных, возникающих при работе этих систем. Основные характеристики: исходный код: доступен, лицензия BSD; форматы импорта: graphml; интерактивное взаимодействие с графом: инструменты визуализации и навигации, инструменты редактирования графа и его визуального представления; ограничения на визуализацию: до 100 000 вершин и связей; алгоритмы авторазмещений: круговое, иерархические; дополнительные инструменты анализа: подсветка кратчайшего пути, циклов, а также поиск максимального общего подграфа двух графов; дополнительно: в качестве базы данных для хранения графов используется SQLite, присутствует возможность добавления новой функциональности в виде плагинов. Visual Graph – пример пользовательского интерфейса. i2 Analyst s Notebook, CrimeLink, Sentinel Visualizer и Xanalys Link Explorer являются программными продуктами, предназначенными для анализа систем взаимосвязанных объектов, а также изучения динамики последовательных событий. Tom Sawyer Software и igraph представляет собой набор библиотек для создания инструментов визуализации и анализа сетей из различных предметных областей. Несмотря на некоторые различия в деталях, по предоставляемой функциональности и назначению эти системы визуализации во многом схожи.
Программные средства анализа графов обязательно содержат модули автоматического размещения, предназначенные для автоматического размещение объектов [37, 67] и реализуют графические схемы размещения объектов, типа "павлиний хвост", круговое размещение, покомпонентное круговое размещение.
У большинства современных промышленных систем присутствует ряд недостатков: отсутствие платформенно-независимых решений, отсутствие собственных специализированных хранилищ, системы не ориентированы на работу с большими графами, некоторые системы устарели или перестали поддерживаться.
Отдельно стоит отметить, исходя из проведенного анализа, что у некоторых систем, таких как VisuaLyzer [65], CoSBiLab [23], Графоанализатор [4], GraphViz [34], yEd [73], aiSee [16], отсутствует информация об ограничении на размеры визуализируемых графов. У таких продуктов, как Visual Graph [9, 69], i2 Analyst s Notebook [37], Cytoscape [25], Gephi [32], нет поддержки визуализации больших графов, они лимитированы объемами вплоть до 100 000 вершин. У нескольких продуктов (Tulip [68], NetMiner [49]) не удалось подтвердить заявленные цифры по визуализации в размере 10 000 000 вершин. Также понятно, что объемы обрабатываемых графов на практике не ограничиваются этими цифрами, что делает непригодным использование этих систем при решении прикладных промышленных задач.
Геометрическая модель автоматического размещений на основе метода физических аналогий
Предложенный в [20] метод разбивается на два этапа, которые повторяются итерационно. Предположим, что мы начали с взвешенного графа из вершин. В первую очередь каждой вершине сети назначается свое сообщество, то есть каждая вершина является отдельным сообществом. Затем, для каждой вершины рассматриваются соседние вершины и вычисляется прирост модулярности, который может иметь место при удалении вершины из своего сообщества и добавления ее в сообщество вершины . Вершина переносится в то сообщество, где достигается максимальный положительный прирост значения модулярности. Если положительного прироста не существует, то вершина остается на исходном месте. Данный процесс повторяется итерационно и последовательно для всех вершин графа до тех пор, пока не может быть достигнуто улучшение показателя модулярности (1.1), после этого первая фаза алгоритма заканчивается.
Вторая фаза алгоритма заключается в построении нового графа, чьи вершины являются сообществами, найденными на первом этапе алгоритма. Для того, чтобы этого добиться, веса связей между новыми вершинами представляют сумму весов связей между вершинами, которые соответствуют двум сообществам. Связи между вершинами одного сообщества становятся петлями в новом графе. Как только вторая фаза алгоритма завершится, станет возможным применить снова первую фазу алгоритма к полученной новой взвешенной сети и так далее.
Этапы алгоритма повторяются до тех пор, пока не будет достигнут локальный максимум модулярности. Данный алгоритм по существу напоминает внутреннюю природу сложных сетей и естественным образом включает в себя понятие иерархии, так как в процессе работы алгоритма строятся сообщества сообществ. Глубина полученной иерархии сообществ определяется числом итераций и обычно является небольшим числом, как было установлено из экспериментов с графами социальных сетей различных размеров.
Различные модификации алгоритмов Ньюмана [31, 33, 50-54] и алгоритм Радичи [58] основаны на похожих идеях. Это методы иерархического разбиения, где связи итеративно удаляются на основе информации о дугах, которые определяются значениями некоторых коэффициентов, введенных для описания частоты встречаемости этих дуг. Рассматриваются обычно либо коэффициент промежуточности, который является мерой того, насколько часто связь входит в кратчайшие пути между различными парами узлов, либо коэффициент группировки дуг, который определяет количество циклов, в которых состоит данная дуга. При этом вычисление коэффициента группировки дуг, как в алгоритме Радичи [58], не настолько трудоемко, как, например, коэффициента промежуточности. За счет использования данного показателя асимптотическая сложность алгоритма составляет 0(п2) на разреженных графах, где п - количество вершин в графе.
Помимо указанных выше алгоритмов, существует еще несколько распространенных подходов для выделения сообществ в сетевых структурах [35, 47]. Однако, приведенные в [41] результаты тестирования показывают, что большинство разработанных алгоритмов не применимы для реальных сетей больших размеров либо по причине низких скоростных характеристик, либо из-за низкого качества выделения сообществ.
Топология сети взаимодействующих объектов может быть описана строгими математическими методами. Структура графа сети может быть представлена симметричной матрицей Лапласа, диагональные элементы которой определяются степенью соответствующей вершины (количество связей, исходящих из данных вершин), а не диагональные элементы определяются как -1, если существуют связь между парой вершин и 0 в противном случае. Заметим, что сумма элементов любой строки или столбца такой матрицы равна нулю. Собственные значения матрицы Лапласа являются неотрицательными вещественными числами, а кратность нулевого собственного значения равна количеству компонент связности. Наименьшее положительное собственное значение определяет алгебраическую связность рассматриваемого графа. Соответствующий этому собственному значению собственный вектор содержит всю информацию об интересующей нас структуре графа. По значениям (величинам) компонент данного собственного вектора можно сгруппировать вершины графа по отдельным группам, которые мы называем сообществами.
На спектральных свойствах графа основан алгоритм Донетти-Муньоза (Donetti and Munoz) [27]. Метод предусматривает получение некоторых характеристик для каждой вершины графа из решения задачи на собственное значение матрицы Лапласа. Естественно, что получаются достаточно объемные данные для графов. Затем вершины группируются классическими иерархическими методами кластерного анализа. Из результирующих разбиений выбирают то, которое максимизирует модулярность Ньюмана-Гирвана. Метод работает за (3), где - количество вершин в графе, за счет вычисления только нескольких собственных векторов c помощью итеративного алгоритма Ланчоса (Lanczos algorithm).
Структурный алгоритм Росваля-Бергстрома (Rosvall and Bergstrom) [61] сводит задачу нахождения наилучшего структурного разбиения графа на сообщества к задаче оптимального сжатия информации о структуре графа, при котором после декодирования результат будет максимально близок к исходной структуре графа. Это достигается путем вычисления минимума функции, которая выражает наилучший компромисс между минимумом разницы исходной и сжатой информацией (максимальной точностью к исходной информации) и максимальным сжатием.
Динамический алгоритм Росваля-Бергстрома (Rosvall and Bergstrom) [62, 63] основан на тех же принципах, что и структурный алгоритм Росваля-Бергстрома. Разница заключается в том, что предыдущий алгоритм сжимал информацию о структуре графа, в то время как данный метод сжимает информацию о динамическом процессе, проходящем в графе (случайное блуждание). Оптимальное сжатие снова достигается оптимизацией показателя качества, называемой минимальной длиной описания случайного блуждания.
Для вычисления показателя качества заданного разбиения используется энтропия, описывающая среднюю длину кодового слова, взятого для кодирования вершины. Применение понятия энтропии для описания соответствующей оценки в методе случайного блуждания обеспечивает оптимизацию разбиения сети при случайном движении по вершинам в каждом из сообществ. Показатель качества полученного разбиения, выраженный через энтропию, может быть легко подсчитан для любого разбиения, обновление и пересчет этого показателя является быстрой операцией.
Построение геометрической модели автоматического размещения объектов графа с выделенными сообществами
Если инцидентные вершины находятся в вертикальной полосе, ограниченной концами линии темы, то все связи между такими вершинами и линией темы будут вертикальными и перпендикулярно соединяться с линией темы. Остальные инцидентные вершины будут соединяться с ближайшими концами линии темы и не будут вертикальными. Положение концов линии темы и их длина может меняться. Использование данного способа представления позволяет эффективно решать задачу автоматического размещения графа.
Исходными данными алгоритма многополосного размещения [3, 11] будет сеть Net = (G, pt, V t) и множество базовых вершин V Q V. Введем функции w(y) и h(v) для v Є V, и w(e) и /i(e) для є Є Е, где w - ширина минимального прямоугольника, который ограничивает визуальное представление атрибутов вершины или связи, и, соответственно, h - высота минимального ограничивающего прямоугольника.
В качестве объекта визуализации будет выступать сеть Net = (С, рг,-фг), где С = (V , Е ) , Vі = {v\vEV,v V0, Зи Є V0: (и, v) Є Е] - множество вторичных вершин, V = V U Vі , Е = {е\е = {v1,v2),e EE,v1E V0 или v2 Є V0}. Таким образом сеть Net содержит множество базовых вершин, все остальные вершины исходного графа, которые с ними связаны, и все связи исходного графа, в которых минимум один конец должен быть базовой вершиной. Стоить отдельно отметить, что в визуализируемую подсеть не включаются связи, соединяющие вторичные вершины.
Пусть множество базовых вершин будет состоять из одного элемента. Тогда, алгоритм многополосного размещения представит базовую вершину в виде линии темы, все остальные смежные с ней вершины будут разбиты на два непересекающихся множества, при этом все вершины одного из них будут расположены над линией темы, вершины другого - под линией темы (Рис. 2.9). На Рис. 2.9 заштрихованными прямоугольными областями являются информационные характеристики объектов (атрибуты и их значения). Здесь и далее они будут недоступны для просмотра.
Принципы разбиения множества смежных вершин могут быть довольно разнообразны и часто зависят напрямую от специфики решаемой задачи: например, для задачи анализа связей участника социальной сети в качестве базовой вершины может быть выбран профиль человека, а множество связанных с ним вершин по отношению дружбы может быть разбито по следующему принципу: в первое множество попадут все вершины, у которых значение атрибута «место работы» будет совпадать со значение этого же атрибута базовой вершины, во второе множество – остальные. Рассмотрим принцип расположения первого множества смежных вершин над линией темы. Сначала вершины упорядочиваются по одному из выбранных критериев. В качестве критерия выступают: случайное расположение вершин, сортировка вершин по значению одного из атрибутов вершин, сортировка вершин по значению одного из атрибутов связей между этими вершинами и линией темы. Затем область над линией темы делится на две горизонтальные полосы. Дальняя от линии темы полоса необходима для размещения внутри нее вершин с визуальным представлением их атрибутов, другая полоса – для размещения в ней визуального представления атрибутов связей. Оставшееся множество вершин размещается под линией темы аналогичным образом.
Рассмотрим другой пример многополосного размещения, в котором используется две базовые вершины. Представим базовые вершины в виде линий темы. Разделим множество смежных с ними вершин на три непересекающихся: первое множество – вершины, которые связаны только с первой линией темы, второе – вершины, которые связаны с обеими линиями темы, третье – вершины, связанные только со второй линией темы. Разместим их следующим образом: первое множество над первой линией темы, второе множество между линиями темы, третье множество под второй линией темы. Принцип размещения элементов аналогичен первому примеру, приведенному выше. Сначала будут последовательно добавлен все связи между линиями темы. Затем стоить отметить, что горизонтальная полоса, образующаяся между линиями темы будет разделена на три: в среднюю полосу будут размещаться вершины со своим полным визуальным представлением (отображение самой вершины и ее атрибутов), в боковых полосах будут размещаться визуальные представления атрибутов связей, причем выбор полосы будет определен именно тем, к какой линии темы относится рассматриваемая связь.
Используемые структуры данных
Операция объединения и пересечения схожи по своей реализации. В качестве входных параметров для данных операций должны быть зафиксированы наборы атрибутов графа, с помощью которых будет проходить отождествление вершин и связей соответственно. По умолчанию учитываются все атрибуты.
При выполнении операции пересечения, строится новый граф, в котором множество вершин состоит из отождествленных вершин обоих графов по заранее заданному набору атрибутов. Множество связей нового графа состоит из всех связей обоих графов, участвующих в операции.
Затем для всех связей в новом графе между всеми парами вершин происходит операция фильтрации повторяющихся связей по заданному набору атрибутов. Такой подход позволяет пересекать графы с количеством вершин порядка нескольких миллионов и количеством связей порядка нескольких миллиардов в каждом.
Алгоритм способен обрабатывать объемы данных, не помещающиеся в оперативную память, за счет последовательного считывания данных с жесткого диска при выполнении фильтрации дублированных связей.
Операция объединения двух графов аналогична пересечению всего лишь с одним отличием: множества вершин исходных графов объединяются, при этом отождествление вершин по набору атрибутов гарантирует отсутствие повторяющихся вершин в новом графе.
При работе с небольшими графами (несколько десятков вершин) еще возможно выполнить размещение элементов сети вручную. При увеличении размеров исследуемого графа начиная с нескольких сотен вершин задача ручного размещения становится невыполнимой.
В связи с большим разнообразием видов графов, существует множество различных способов автоматического отображения графов. Модуль автоматического размещения предназначен для автоматического размещения объектов и реализует графические схемы [18, 38] типа павлиний хвост, линия темы, круговое размещение, покомпонентное круговое размещение, а также размещение, основанное на алгоритме выделения сообществ в сети.
Все разработанные алгоритмы автоматического размещения направленны на работу с большими графами, достигающими сотен тысяч вершин. Визуальное представление сетей может выступать в качестве мощного метода отображения скрытой информации, хранящейся в данных о системе взаимосвязанных объектов.
Модуль визуализации отвечает за способы отображения объектов сети и за скорость их отображения. В программном комплексе предусмотрено несколько изобразительных соглашений для вершин: иконки, линии темы, таблицы. Отдельно стоит отметить способ представления вершин в виде линии темы.
Линия темы – это вершина, которая представляется в виде горизонтального отрезка с иконкой, причем все смежные вершины соединены с линией темы перпендикулярно (если они находятся над или под ней) или с ближайшим ее концом. Положение концов линии темы и ее длина может меняться. Использование данного способа представления позволяет эффективно решать задачу визуализации для некоторых графов. Доступна визуализация множественных связей с изломами между вершинами, с возможностью задания ширины, цвета и типа линии. Для атрибутов также предусмотрено множество способов и настроек отображения.
Для эффективного отображения графов используются специально разработанные структуры данных, позволяющие получать быстрый доступ к данным, и алгоритмы машинной графики, заточенные под одновременное отображение большого количества объектов.
Все вершины и связи графа хранятся в соответствующих сбалансированных бинарных деревьях поиска, где ключами выступают указатели на объекты.
Структура связей графа хранится в сбалансированном бинарном дереве поиска, где в качестве ключей выступают указатели на вершины, а в качестве значений хранятся множества инцидентных ребер соответствующей вершины, которые в свою очередь также реализованы на сбалансированных бинарных деревьях поиска. Выбор данной структуры обусловлен тем, что доступ к случайной вершине или связи, доступ к инцидентным связям вершины и удаление или добавление объектов будет осуществляться за логарифмическое время.
При визуализации используются координаты вершин, хранящихся в структуре вершины. В то время как координаты связей вычисляются в процессе визуализации. Для этого предусмотрена отдельная структура данных, отвечающая за хранение направляющей линии между парой вершин. Все связи между заданной парой вершин будут строго параллельны направляющей линии и содержать такое же количество изломов. Тем самым достигается эффективное расходование оперативной памяти без ущерба производительности.