автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели, алгоритмы и программный комплекс визуализации сложных сетей

004616951

На правах рукописи

Пупырев Сергей Николаевич

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС ВИЗУАЛИЗАЦИИ СЛОЖНЫХ СЕТЕЙ

05.13.18. - математическое моделирование, численные методы и комплексы

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

- 9 ДЕК 2010

Екатеринбург — 2010

004616951

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Уральский государственный университет им. A.M. Горького» на кафедре алгебры и дискретной математики.

Научный руководитель: доктор физико-математических наук,

профессор

Баранский Виталий Анатольевич

Официальные оппоненты: доктор технических наук,

профессор

Гайдамакин Николай Александрович

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

Ведущая организация: Институт математики и механики Уральского

отделения РАН

Защита состоится 3 ^-декабря 2010 в на заседании Диссертацион-

ного совета Д 212.286.10 при ГОУ ВПО «Уральский государственный университет им. A.M. Горького» по адресу: 620000, г. Екатеринбург, пр. Ленина 51, комн. 248.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Уральский государственный университет им. A.M. Горького».

Автореферат разослан

ноября 2010.

Ученый секретарь Диссертационного совета доктор физико-математических наук, профессор

Пименов В.Г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Считается, что 90% информации человек получает посредством зрения и только 10% через остальные органы чувств. Естественно, что проблема визуализации графовой информации приобрела первостепенную важность. Задача визуализации состоит в создании изображения, позволяющего анализировать структуру графа и выявлять его характеристики. В данной диссертации мы концентрируемся на визуализации «сложных сетей». Под сложной сетью понимается система, состоящая из реальных объектов и связей между ними. Другими словами, сложная сеть - это граф, построенный на основе реальных данных. Для сложных сетей характерна безмасштабная топология [1], и они, как правило, наделены дополнительной семантикой, которая, обычно выражается набором атрибутов, приписанных вершинам и ребрам графа. Примерами сложных сетей могут служить сети страниц WWW, социальные сети, графы соавторства ученых, бизнес-отношения, сети взаимодействия протеинов и т.д.

Самые ранние изображения графов, дошедшие до наших дней, относят к XIII веку [9]. Хорошо известны изображения генеалогических деревьев, которые появились, по-видимому, в начале XV века. В переписке Эйлера и Лейбница в XVIII веке обсуждается использование рисунков для решения графовых задач. Позже J.B. Listing, A. Cayley и другие известные математики формулируют и решают задачи рисования деревьев и графов. К началу XX века рисование графов выходит за пределы математики: изображения социальных отношений являются центральной темой в работах Moreno в 1932 [7], который считается родоначальником анализа социальных сетей.

Новейшая история теории рисования графов начинается с 80-х годов и связана с появлением автоматических алгоритмов визуализации. В научном обществе формируется группа ученых целенаправленно занимающаяся визуализацией графов. Теория рисования графов выделяется в отдельную область математики. Ежегодно проводится крупная международная конференция (Symposia on Graph Drawing), на которой обсуждаются новейшие алгоритмы и актуальные задачи в области рисования графов. Большое количество конференций имеют выделенные секции по данной тематике (например, Symposium on Discrete Algorithms, Symposium on Computational Geometry, International Conference on Information Visualization и др.). Существует несколько международных журналов, публикующих результаты исследований по визуализации графов. В настоящее время разработано огромное количество программ, библиотек и специализированных пакетов для рисования графов (крупнейшие - graphviz от AT&T Labs, MSAGL от Microsoft, yFiles от у Works). В нашей стране задачами визуализации информации и рисованием графов занимаются, к примеру, в Новосибирском государственном университете, Уральском государственном университете, Институте математики и механики УрО РАН.

Каковы успехи теории рисования графов на сегодняшний день? Решенными задачами на сегодня можно считать рисование графов с «хорошей» простой структурой - деревьев, сеток, планарных графов, ацикличных (в случае ориентированных графов). Для малых и средних графов с количеством вершин, не превосходящим несколько десятков, существуют

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

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

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

• Разработать математическую модель сложных сетей, адекватно описывающую реальные данные.

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

• Дать теоретические оценки вычислительной сложности разработанных алгоритмов.

• Реализовать алгоритмы в виде программного комплекса.

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

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

программного комплекса основана на методах структурного и объектно-ориентированного программирования с активным использованием шаблонов и моделей.

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

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

Алгоритмы и модели визуализации графов, разработанные и реализованные автором во время двух трехмесячных стажировок в Microsoft Research, вошли в состав библиотеки MSAGL для автоматического рисования графов. Данная библиотека является основным инструментом визуализации графов в нескольких продуктах, в частности, Microsoft Visual Studio 2010 и Microsoft Code Canvas. Работа автора во время стажировок проводилась в непосредственном сотрудничестве с исследователями Microsoft Research, совместно реализованные алгоритмы уже внедрены в Visual Studio, планируется внедрение в ряд других крупных продуктов.

Апробация и публикации. Все основные результаты диссертации отражены в публикациях [11-13],[15-18], список которых приводится в конце автореферата. Публикации [11], [12] и [13] опубликованы в ведущих рецензируемых научных журналах, определенных ВАК. Авторские права на созданные диссертантом совместно с Л. Нахма.нсоном алгоритмы и программные комплексы оформлены в виде патента [14]. В совместных рабо-

тах [13] и [14J диссертанту принадлежат разработка и реализация алгоритма, а также доказательства всех утверждений, Л. Нахмансону - постановка задачи. Из остальных совместных работ [12j и [18j в диссертацию вошли результаты, полученные лично автором.

Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:

1. Всероссийская молодежная школа-конференция «Современные проблемы математики» (Кунгурка). Екатеринбург, 2009 и 2010.

2. Конференция молодых ученых по информационному поиску (RuSSIR). Воронеж, 2010.

3. International Symposium on Graph Drawing (Graph Drawing). Konstanz, Germany, 2010.

4. International Conference on Intelligent Systems Design and Applications (ISDA). Cairo, Egypt, 2010.

5. Научный семинар «Алгебраические системы». УрГУ, Екатеринбург.

Первоначальные результаты работы по укладкам направленных графов и визуализации сложных сетей также представлялись на докладе во время первой трехмесячной научной стажировки автора n Microsoft Research (Рэдмонд, США) в 2009. Работа, описывающая метод связывания ребер для неориентированных графов, была представлена в Microsoft Research в 2010 во время второй трехмесячной научной стажировки. Эта работа была также представлена на международной конференции Symposium on Graph Drawing (Konstanz, Germany) в 2010, которая является крупнейшим ежегодным научным событием для исследователей и разработчиков в области визуализации графов. В рамках конференции между участниками проводится соревнование Graph Drawing Contest, на котором определяются лучшие алгоритмы и методы автоматического рисования графов. В 2010 изображения, построенные автором при помощи метода связывания ребер, были признаны лучшими в номинации «Link Routing».

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Под «сложными сетями» понимаются системы, состоящие из реальных объектов и связей между ними. Сложная сеть моделируется графом, однако этот граф, как правило, имеет определенную структуру и обладает характерными признаками. Такие сети принято называть безмасштабными (scale-free), поскольку средняя степень вершины в них не является характерной, т.е. отсутствует характерный масштаб. Для безмасштабной топологии характерно наличие малого числа хабов - вершин наибольшей степени - и большого числа вершин малой степени. Сложные сети имеют хорошо выраженную структуру естественных сообществ: вершины сети разделены по группам, которые слабо связаны между собой, но имеют большую плотность ребер внутри. При этом сложные сети глобально являются разреженными с количеством ребер, пропорциональным количеству вершин т = 0(п).

В классическом понимании под ¿-мерной укладкой графа G = (V, Е) понимается отображение вершин графа V в множество точек и его ребер на жордановы кривые пространства. R'1. Позицию вершины v будем обозначать через р„. Для построения укладки строится специальная модель, в которой вершины и ребра графа соответствуют «реальным» физическим взаимодействующим объектам. Для этой системы вводится функция энер-

гии таким образом, что конфигурации с меньшим уровнем энергии соответствуют лучшим укладкам. При этом задача поиска лучшей укладки графа сводится к поиску минимума энергии системы. В зависимости от способа построения энергии выделяют силовой (force-directed) и пружинный (spring) алгоритмы рисования графов [2]. В силовой модели вершины графа соответствуют заряженным частицам, между которыми действуют силы притяжения и отталкивания. В общем виде энергия системы выражается следующим образом:

и = Yh fb™-™ IК - Р» 1Г + fr™um* I \pu - pv | |r.

(u,v)6E (u,v):u^v

Первое слагаемое соответствует энергии притяжения, а второе - энергии отталкивания. Параметры системы а, г, /а, /г 6 R и веса вершин и ребер mv,muv 6 R определяют степень влияния каждого компонента на итоговую укладку. В пружинной модели ребра графа заменяются пружинами, при растяжении и сжатии которых возникают силы упругости. Энергия системы пружин записывается следующим образом:

(u,v)eE

Задача построения укладки графа в математической модели, основанной на физических аналогиях, сводится к решению оптимизационной задачи поиска укладки с минимальной энергией:

min U

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

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

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

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

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

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

Во второй главе предлагается алгоритм укладки вершин сложной сети, визуализирующий структуру ее естественных сообществ. Под сообществом графа G мы понимаем подмножество его вершин С С V, в котором вершины тесно связаны друг с другом, и имеют малое количество «внешних» ребер, соединяющих их с остальным графом. Разбиение графа на сообщества - это разбиение множества вершин на непересекающиеся сообщества. Для измерения качества разбиения используется метрика, предложенная в [4], которая называется модульность (modularity):

где сумма берется по всем сообществам ..., Св графа. Через Iк обозначается количество ребер между вершинами сообщества Ск, а через с4 - сумма степеней вершин этого сообщества. Под т, как обычно, понимается количество ребер в (?. Модульность показывает, насколько «плотность» ребер

(1)

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

Эксперименты показывают (например, в [8]), что большое количество реальных сетей обладают хорошо выраженной структурой сообществ. Более того, можно говорить об иерархии, в которой мелкие сообщества оказываются вложенными в более крупные. Каждый уровень иерархии представляет собой набор непересекающихся множеств: верхний уровень содержит единственное сообщество, содержащее все вершины исходного графа, на нижнем уровне количество сообществ совпадает с количеством вершин графа. Сообщества /-ого уровня будем обозначать С1к, где к б [1..количество сообществ уровня /].

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

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

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

(а) Классический силовой алгоритм. (Ь) Ноями алгоритм визуализации сообществ.

Рис. 1. Граф, построенный на основе расписания футбольных игр в американском колледже в 2000 году (115 вершин, 613 ребер). Вершины графа соответствуют командам, ребра - играм между ними. Встречи происходят чаще между командами из одного дивизиона, поэтому можно считать дивизионы естественными сообществами в графе. Наш алгоритм с большой точностью нашел все сообщества графа.

иерархии мы строим фактор-граф G'. Его вершинами являются сообщества второго уровня Cjf, C|i ■ • •, Cji и каждая пара сообществ, имеющая смежные вершины, соединена ребром весом где w(Ci, Cj) - количество ребер между вершинами сообществ Q и Cj. Далее строится укладка графа G' с использованием силовой модели, в которой учитываются веса ребер. В результате мы получаем укладку, в которой «связанные» сообщества будут расположены рядом друг с другом.

Последовательно спускаясь по дереву, мы укладываем каждый узел-сообщество. Рассмотрим обработку узла с / > 2, т.е. сообщество не менее второго уровня. Соответствующий граф G' содержит вершины

W+1 W+l nl+1 ~ „ -_____ Ы г), „,..<„„ _ ^ W-4-i „

, ,..., О; , т.е. осел Детей iv^. оес реира, между вершинами и

W+1 ' й и(с!+1,Й+1) _

Cj пропорционален количеству ребер между ними: . В силовую

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

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

Теорема 2. Вычислительная сложность алгоритма визуализации сообществ составляет 0(n¿).

В отличие от произвольных графов, сложные сети, построенные на основе реальных данных, обладают рядом особенностей, позволяющих создавать более эффективные алгоритмы. В частности, реальные графы являются разреженными, т.е. количество ребер в графе пропорционально количеству вершин: т = 0(п). Другое известное свойство иерархия сообществ реальных сетей, полученная методом оптимизации модульности, имеет высоту порядка log п [3]. Будем называть граф реальным, если он имеет оба этих свойства.

Теорема 3. Алгоритм визуализации сообществ имеет вычислительную сложность 0(n2logn) для реальных графов.

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

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

В поуровневой схеме рисования графов [10] строится разбиение вершин графа G = (V,Е) на подмножества L\,...,Lh так, что для всех дуг графа е = (и, v), где.u € L¡ uve Lj, выполняется i < j. После построения разбиения вершин исходный граф преобразуется к строго поуровневому графу Gp. Для этого каждая дуга е = (ы, v) сие £¡ и v € Lj, проходящая через несколько уровней, заменяется на последовательность вершин

Рис. 2. Диаграмма состояний приложения notepad.exe.

и — di, di+1,... ,d0 =vii ребер (¿¿, di+{), (ck+i, di+2),..., (dj^\,dj). Вершины dk для i < к < j называются фиктивными, а вершины d{ и dj - реальными. Для фиктивных и реальных вершин строится порядок, при котором количество пересечений ребер графа Gp минимально, и для каждой вершины определяется ее горизонтальная координата.

Стандартный способ для рисования ребер в такой схеме - это проведение кусочнолинейных ломаных (или сплайнов) через соответствующие вершины поуровневого графа. Однако если количество ребер в графе велико, то даже в оптимальной укладке ребра пересекаются слишком часто и визуально сложно определить, какие вершины соединены ребром, а какие нет. Мы предлагаем рисовать некоторые ребра вместе друг с другом, тем самым экономя пространство для рисования и делая изображение проще для понимания структуры графа (рис. 2). Такой метод называется связыванием ребер (edge bundling).

На вход алгоритму связывания ребер подается поуровневый граф G31, разбиение на уровни L и укладка, т.е. координаты его вершин. Алгоритм состоит из трех шагов.

1. Сгруппировать ребра графа С в набор связок (bundles), где под связ-

кой понимается множество одноуровневых ребер. Группировка ребер происходит на основе минимизации длины укладки графа (ink). Под длиной укладки мы понимаем суммарную длину ребер нарисованного графа, при этом совпадающие ребра с читаются один раз. Задачу поиска укладки поуровневого графа с минимальной длиной мы решаем с помощью «жадной» эвристики, поскольку общая задача минимизации длины укладки является NP-трудной. Изначально для каждого ребра графа Gp мы создаем связку, содержащую только это ребро. Далее мы находим пару связок, объединение которых максимально уменьшает длину укладки, и производим это объединение. Процедура объединения связок производится до тех пор, пока длина укладки графа уменьшается.

2. Укладка графа с минимальной длиной, полученная после предыдущего этапа связывания, может иметь дуги с большим количеством изломов и поворотов. Для разрешения этой проблемы мы корректируем координаты некоторых фиктивных вершин, «выпрямляя» дуги и делая их более вертикальными и плавными.

3. После объединения ребер в связки изображение графа заметно упрощается, но при этом появляется элемент «двусмысленности», т.е. не всегда возможно отследить путь дуги от начальной вершины к конечной. На этом этапе алгоритма мы «расширяем» каждую связку таким образом, что входящие в ее состав ребра рисуются индивидуальными параллельными отрезками. При расширении связок возникает вопрос об относительном порядке ребер в пределах каждой связки. Естественно использовать тот порядок, при котором количество пересечений дуг исходного графа G минимально. Соответствующая задача называется минимизацией пересечений линий в схемах метро (metroline crossing minimization problem, [6]). Все пары дуг графа G можно разделить на два класса: те, которые можно нарисовать (т.е. указать порядок в пределах связки) без пересечений, и «неизбежные» те, которые пересекаются при любом указанном порядке.

Теорема 6. Оптимальный порядок дуг графа G в пределах каясдой

связки содержит, только неизбежные пересечения.

Теорема 7. Сложность алгоритма вычисления порядка с минимальным количеством пересечений дуг графа G составляет 0(\ЕР\ + |Z?| log |£( + Lp), где \ЕР\ - количество ребер соответствующего поуровневого графа Gp, |£| - количество дуг графа G и Lp -суммарная длина дуг графа G.

Теорема 8. Общая сложность алгоритма связывания ребер для поуров-невых графов составляет 0(т4 + ппг), где п - количество вершин, am -количество ребер графа Gp.

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

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

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

• Для каждого построенного графа строится укладка на плоскости.

• Результирующая визуализация получается объединением всех укладок с соединением вершин, соответствующим одинаковым объектам в соседних графах (рис. 3(c)).

я Е О С

/ 4

с \/в

■С

(а)

(Ь)

Рис. 3. Граф, состоящий из трех слоев, (а) Укладки без учета ментальной карты. (Ь) Сохранение метальной карты, (с) Послойная визуализация.

В задаче динамической визуализации требуется нарисовать последовательность графов ■ • •: От, описывающих некоторые данные за последовательные промежутки времени. С каждой вершиной и £ ассоциирована метка Будем считать, что 1Ь — 1и тогда и только тогда, когда вершины у а и соответствуют одному и тому же объекту исходных данных. При построении послойной визуализации требуется учитывать два конкурирующих критерия. С одной стороны, каждый слой должен быть нарисован с учетом общепринятых критериев эстетичности графа: малое количество пересечений ребер, симметрия, постоянная длина ребер и т.д. С другой, последовательность укладок должна сохранять ментальную карту [5]. Это означает, что графы нужно рисовать в унифицированном стиле: вершины с одинаковыми метками должны иметь близкие позиции.

Для решения поставленной задачи добавим в силовую и пружинную модели дополнительные силы:

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

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

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

Итоговое выражение для энергии системы выглядит следующим образом:

U = Uattr + Urepu "Ь Ügrav + Umental- (2)

Остается открытым вопрос, как минимизировать U. Заметим, что на последовательность GuG2,...,Gt графов можно смотреть, как на один большой граф, объединяющий в себе все вершины и ребра каждого графа последовательности. Граф-объединение Gs = (VS,ES) состоит из множества вершин К = U^jV U Vgrav и ребер Es — U?LгЕ1 U {(u, v) С V, x К, : I, = U {{u,vgrav),u 6 liJ=lVi}. В этом смысле компоненты Ugrav и Umental ~ эт0 части энергии притяжения. Поэтому для минимизации выражения 2 можно применять классические итеративные методы минимизации энергии для статических графов. В диссертации установлено (теоремы 9 и 10), что сложность алгоритма визуализации последовательности графов Gi, G2,..., Gt равна суммарной сложности визуализаций каждого из графов Gb G2,. ■ ■, Gr-

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

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

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

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

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

• Расширяемая архитектура позволяет легко добавлять новую функциональность в систему. От программиста, создающего свое собственное расширение, не требуется знания деталей внутреннего представления графов и логики работы с ними.

• Богатый набор графических возможностей и пользовательского интерфейса (поддержка стилей, операции Undo/Redo и т.д.).

• Встроенная возможность автоматического анализа сетей (фильтрация, статистика, аннотация данных) и укладок графов (автоматическое вычисление метрик эстетичности).

Система доступна для свободного скачивания и использования на ресурсе http://code.google.eom/p/graphvis. Там же доступна подробная инструкция пользователю и документация.

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

СПИСОК ЛИТЕРАТУРЫ

[1] Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Reviews of Modern Physics. - 2002. - Vol. 74. - Pp. 47-97.

[2] Eades P. A heuristic for graph drawing // Congressus Numerantium.— 1984. Vol. 42. Pp. 149 160.

[3] Fortunato S., Castellan C. Community structure in graphs / Ed. by B. Meyers. — Encyclopedia of Complexity and System Science. 2008.

[4] Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. of the National Academy of Sciences of the USA. — 1999. - Pp. 7821-7826.

[5] Layout adjustment and the mental map / K. Misue, P. Eades, W. Lai, K. Sugiyama // Journal of Visual Languages and Computing. — 1995. — Vol. 6, no. 2. - Pp. 183-210.

[6] Line crossing minimization on metro maps / M. A. Bekos, M. Kaufmann, K. Potika, A. Symvonis // Proc. 15th Int. Symposium on Graph Drawing. - 2008. - Pp. 231-242.

[7] Moreno J. L. Application of the group method to classification // New York: National Committee on Prisons and Prison Labor. — 1932.

[8] Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Physical Review E. - 2004. - Vol. 69. - P. 026113.

[9] A short note on the history of graph drawing / E. Kruja, J. Marks, A. Blair, R. Waters // Proc. 9th Int. Symposium on Graph Drawing. — 2001. — Pp. 602-606.

[10] Sugiyama K., Tagawa S., Toda M. Methods for visual understanding of hierarchical system structures // IEEE Transactions on Systems, Man, and Cybernetics. 1981. Vol. 11, no. 2. Pp. 109 125.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в ведущих рецензируемых научных журналах, определенных ВАК:

[11] Пупырев С.Н. Визуализация структуры сообществ в графах // Системы управления и информационные технологии. - Воронеж, 2009. № 2(36). С. 21-27.

[12] Пупырев С.Н., Тихонов А.В. Визуализация динамических графов для анализа сложных сетей // Моделирование и анализ информационных систем. - Ярославль, 2010. № 17(1). С. 117-135.

[13] Pupyrev S., Nachmanson L., Kaufmann M. Improving layered graph layouts with edge bundling // Proceedings of 18th International Symposium on Graph Drawing, Konstanz, Germany. - Springer-Verlag, 2010. № 6502. C. 147-158.

Другие публикации:

[14] Nachmanson L., Pupyrev S. Visualizing a layered graph using edge bundling // U.S. patent application MS#328544.01, 2010.

[15] Пупырев С.Н. Визуализация безмасштабных графов // Труды 40-й всероссийской молодежной школы-конференции. Екатеринбург, 2009. № 40. С. 374-378.

[16] Пупырев С.Н. Эффективное вычисление метрик эстетичности // Известия Уральского государственного университета, серия Компьютерные науки и информационные технологии. - Екатеринбург, 2010. № 74. С. 171-179.

[17] Пупырев С.Н. Система визуализации графов GraphVisSD // Труды 41-й всероссийской молодежной школы-конференции. Екатеринбург, 2010. № 41. С. 501-507.

[18] Пупырев С.Н., Пронченков А.Г. Прогнозирование загруженности автомобильных дорог // Труды конференции молодых ученых по информационному поиску. - Воронеж, 2010. № 4. С. 64-78.

Бумага офсетная. Гарнитура Times New Roman. Усл. печ. л. 1,5. Тираж 100 экз. Заказ № \

Отпечатано в ИПЦ «Издательство УрГУ». 620083, г. Екатеринбург, ул. Тургенева, 4.

Глава 0. Введение

0.1. Мотивация

0.2. Историческая справка.

0.3. Цели работы

0.4. Основные результаты

0.5. Структура диссертации . !.

0.6. Апробация.

Глава 1. Базовые определения и модели визуализации графов

1.1. Определения

1.2. Сложные сети.

1.3. Модели визуализации графов.

1.3.1. Силовая модель.

1.3.2. Многомерное шкалирование.

1.3.3. Сравнение моделей.

1.4. Недостатки существующих алгоритмов.

Глава 2. Визуализация структуры сообществ

2.1. Описание алгоритма.

2.2. Вычислительная сложность.

2.3. Экспериментальная часть.

5.2. Архитектура .112

5.3. Основные возможности .115

5.4. Заключение.118

Результаты и выводы 120

Литература 122

Глава 0. Введение

Рисунок наглядно представит мне то, что в книге изложено на целых десяти страницах.

И.С. Тургенев, Отцы и дети, 1862

0.1. Мотивация

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

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

Считается, что 90% информации человек получает посредством зрения и только 10% через остальные органы чувств. Естественно, что проблема визуализации графовой информации приобрела первостепенную важность. Задача визуализации состоит в создании изображения, позволяющего анализировать структуру графа и выявлять его характеристики. В данной диссертации мы концентрируемся на визуализации сложных сетей. Под «сложной сетью» понимается система, состоящая из реальных объектов и связей между ними. Другими словами, сложная сеть - это граф, построенный на основе реальных данных. Примерами сложных сетей могут служить сети страниц WWW, социальные сети, графы соавторства ученых, бизнес-отношения, сети взаимодействия протеинов и т.д.

В зависимости от применения элементы графа изображаются различными способами. На практике визуализировать граф (нарисовать, построить укладку) чаще всего означает указать координаты вершин и нарисовать их в виде точек на плоскости, а ребра изобразить прямыми или ломанными, соединяющими соответствующие точки. При визуализации сложных сетей на изображение добавляется также дополнительная информация об элементах графа с использованием текстовых меток, цветов и других визуальных элементов. Например, рис. 0.1(a) содержит визуализацию социальной сети одной из американских школ, в которой вершины соответствуют студентам, а ребра - отношению «дружба» между ними. Такие изображения помогают при анализе социальных отношений: например, в данной школе существует четыре обособленных сообщества студентов, причем студенты одной расы предпочитают общаться между собой. Каждое изображение должно удовлетворять набору эстетических критериев, специфицирующих качество и наглядность изображения. Так, например, в визуализациях сети в стиле «схем метро» требуется минимизировать количество пересечений между линиями (рис. 0.1(Ь)). а) (Ъ)

Рис. 0.1. (а) Визуализация социальной сети между студентами американской школы. Цвет вершин соответствует этнической расе студента. (Ь) Изображение схемы метро Мадрида. При рисовании подобных сетей требуется сохранить топологию расположения станций относительно друг друга и минимизировать количество пересечений линий метро.

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

0.2. Историческая справка

Самые ранние изображения графов, дошедшие до наших дней, относят к XIII веку и появлению книги «Book of Games» с описанием настольных игр Morris [89]. Хорошо известны также изображения генеалогических деревьев, которые появились, по-видимому, в начале XV века [63]. Отцом теории графов принято считать Эйлера, опубликовавшего в 1736 работу с решением задачи о кёнигсбсргских мостах [36]. Однако сам Эйлер воздерживался от использования рисунков для описания или решения графовых задач, при том что в переписке с ним Лейбниц про визуализацию графов отмечает «new characteristic, completely different from algebra, which will have great advantage to represent to the mind . everything which depends on the imagination»1. Первые рисунки графов в математических статьях появляются в XVIII и начале XIX века. J.B. Listing в своей работе по топологии [71] рассматривает задачу рисования графа (рис. 0.2(a)) одним росчерком. Задачи, связанные с рисованием и пометкой деревьев, встречаются в статьях A. Cayley [19]. В то же время рисование графов «всплывает» в кристаллографии и химии, в работах R.J. Haüy [55] появляются первые рисунки графов (кристаллов) в трехмерном пространстве.

К началу XX века рисование графов выходит за пределы математики. Исследователи начинают использовать инструмент визуализации для решения своих, нематематических задач. Изображения социальных отношений являются центральной темой в работах Moreno в 1932 (рис. 0.2(b), [73]), который считается родоначальником анализа социальных сетей. Позже он

1 новая характеристика, отличная от алгебры, будет иметь огромное преимущество . для объяснения всего, что зависит от воображения a) (b)

Рис. 0.2. (а) Изображение графа, который можно нарисовать одним росчерком, 1847. (Ь) Одна из первых визуализаций социальной сети, 1934. одним из первых ввел понятие критерия эстетичности изображения, указав «The fewer the number of lines crossings, the better the sociogram»2. По сей день это правило является самым популярным при построении изображения. Рисование графов появляется и неоднократно «переизобретается» в физике при решении задач взаимодействия тел. Фсйнманн рассматривал диаграммы, в которой вершины представляют физические частицы, а ребра - пути частиц после столкновений. Биологи изучают теорию ветвящихся процессов и открывают методы рисования деревьев с разнообразными ограничениями. Даже в психологии возникают планарные графы и их изображения (Левин, 1936).

Новейшая история теории рисования графов начинается с 80-х годов и связана с появлением автоматических алгоритмов визуализации. В научном обществе формируется группа ученых целенаправленно занимающаяся визуализацией графов. Теория рисования графов выделяется в отдельную область математики. Отметим лишь несколько самых заметных достижений. Самыми популярными методами рисования являются алгоритмы, основанные на физических аналогиях, предложенные в работах P. Eades [30],

Чем меньше пересечений линий не. социограмме, тем она. лучше.

Т. Kamada и S. Kawai [61]. Поуровневый подход для рисования ориентированных графов был предложен Сугиямой в 1981 [91]. Значительный вклад в рисование деревьев внесли Reingold и Tilford [87]. Планарными укладками графов (без пересечения ребер) занимались, например, Tutte [96], Chiba [21], Tarjan [93]. Ортогональные изображения графов, в которых ребра изображаются прямыми, параллельными осям координат рассматривали в своих работах Tamassia [92], Di Battista [11]. Стоит отметить, что многие методы в теории рисования графов неоднократно «переизобретались». Например, метод многомерного шкалирования, предложенный для визуализации графов в середине 2000-х [45], успешно применялся для рисования диаграмм Крускалом в начале 80-х [66].

За последнее десятилетие теория рисования графов заметно возмужала. Ежегодно проводится крупная международная конференция (Symposia on Graph Drawing), на которой обсуждаются новейшие алгоритмы и актуальные задачи в области рисования графов. Большое количество конференций имеют выделенные секции по данной тематике (например, Symposium on Discrete Algorithms, Symposium on Computational Geometry, International Conference on Information Visualization и др.). Существует несколько международных журналов, публикующих результаты исследований по визуализации графов. В настоящее время разработано огромное количество программ, библиотек и специализированных пакетов для рисования графов (крупнейшие - graphviz от AT&T Labs, MSAGL от Microsoft, yFiles от у Works).

Каковы успехи теории рисования графов на сегодняшний день? Частично ответ на этот вопрос дает рис. 0.2. Решенными задачами на сегодня можно считать рисование графов с «хорошей» простой структурой - деревьев, сеток, план арных графов, ацикличных (в случае ориентированных графов). Для малых и средних графов с количеством вершин, не превосходящим несколько десятков, существуют эффективные алгоритмы, строящие качественные понятные изображения. На практике графы имеют более сложную структуру (см. главу 1), и существующие методы работают неудовлетворительно. По-прежнему не решена задача масштабирования: сейчас не существует методов, визуализирующих большие реальные графы. С ростом количества информации актуальными становятся вопросы визуализации изменяющихся во времени графов. Нет удобных функциональных систем для интерактивной работы с графовыми данными. размер графа <10 <100 <10000 >105 мы здесь

Рис. 0.3. Эволюция теории рисования графов.

0.3. Цели работы

Цель данной работы - найти или разработать подход к решению вышеозначенных проблем.

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

• Для создания такого комплекса построить модели графов и алгоритмы, сконструированные в соответствие с этими моделями.

• Провести экспериментальное тестирование разработанных методов, убедившись на практике в их применимости и полезности.

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

0.4. Основные результаты

• Разработаны алгоритмы рисования больших графов, построенных на основе реальных данных. Охвачен весь спектр задач, возникающих при визуализации графов: предложен эффективный способ укладки вершин графа, разработан новый способ проведения ребер в графе, рассмотрены вопросы рисования ориентированных графов, решена задача минимизации числа пересечений ребер в методе связывания ребер. Разработанные нами алгоритмы используются на практике в крупных промышленных системах (Microsoft Visual Studio), работа отмечена призами на международной конференции (Symposium оп Graph Drawing).

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

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

0.5. Структура диссертации

Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы.

5.4. Заключение

Изначально GraphVis3D задумывался как учебный проект, предназначенный для рисования графов специального вида. Однако позже система GraphVis3D переросла в полностью самостоятельный комплекс программ с открытым исходным кодом визуализации и анализа сложных сетей. С помощью этого инструмента было выполнено два проекта по анализу социальных сетей: анализ графа друзей в сети LiveJournal [110] и изучение динамики социальных отношений по логам онлайн чатов [107]. Также GraphVis3D выступил в роли «тестового полигона» алгоритмов рисования ребер графа с использованием техники связывания ребер (см. главу 3). Такие алгоритмы изначально реализовывались в рамках библиотеки MSAGL [104], впоследствии тестировались на реальных данных в GraphVis3D, и, наконец, стали частью крупного продукта Microsoft Visual Studio.

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

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

Таким образом можно утверждать, что система СгарКУЪЗО работает на практике для решения конкретных прикладных задач. Сможет ли она стать полноценным универсальным продуктом для анализа сложных сетей - покажет время.

Результаты и выводы

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

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

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

Данная диссертация

Анализ сложных сетей

Визуализация сложных сетей

Визуализац£ информации Рисование графе

Рис. 5.5. Роль и место диссертационной работы в общей картине анализа информации.

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

1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение.— Спб.: БХВ-Петербург, 2003. (Стр. 56 и 58.)

2. А санов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. (Стр. 18.)

3. Abello J., Ham F. van, Krishnan N. Ask-graphview: A large scale graph visualization system // IEEE Transactions on Visualization and Computer Graphics. 2006. — Vol. 12. — Pp. 669-676. (Стр. 53.)

4. Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Reviews of Modern Physics. 2002. — Vol. 74. — Pp. 47-97. (Стр. 100.)

5. An analysis of current trends in cbr research using multi-view clustering: Tech. rep. / D. Greene, J. Freyne, B. Smyth, P. Cunningham: 2009. (Стр. 53.)

6. Analyzing (social media) networks with NodeXL / M. Smith, B. Shneiderman, N. Milic-Frayling et al. // Proc. of the fourth international conference on Communities and technologies. — 2009. — Pp. 255-264. (Стр. 112.)

7. Asquith M., Gudmundsson J., Merrick D. An ilp for the metro-linecrossing problem // Proc. of the 14th Computing: The Australasian Theory Symp. (Cats'08). — 2008. Pp. 49-56. (Стр. 72.)

8. Auber. D. Tulip: A huge graph visualisation framework // Graph Drawing Software. 2003. — Pp. 105-126. (Стр. 112.)

9. Bastian M., Heymann S.; Jacomy M. Gephi: An open source software for exploring and manipulating networks // Proc. of Int. AAAI Conf. on Weblogs and Social Media. 2009. (Стр. 112.)

10. Batagelj V., Mrvar A. Pajek analysis and visualization of large networks // Graph Drawing Software. — 2003. — Pp. 77-103. (Стр. 112.)

11. Battista G. D. Spirality of orthogonal representations and optimal drawings of series-parallel graphs // Proc. WADS. — 1993. — Pp. 150162. (Стр. 9.)

12. Bertault F. A force-directed algorithm that preserves edge crossing properties // Information Processing Letters. — 2000. — Vol. 74. — Pp. 713. (Стр. 35.)

13. Boitmanis K., Brandes U., Pick C. Visualizing internet evolution on the autonomous systems level // Proc. 15th Intl. Symp. Graph Drawing. — 2007. Pp. 365-376. (Стр. 107.)

14. Bourqui R., Auber D., Mary P. How to draw clustered weighted graphs using a multilevel force-directed graph drawing algorithm // Proc. of the 11th Int. Conf. on Information Visualization.— 2007.— Pp. 757-764. (Стр. 53.)

15. Brandenburg F. J., Himsolt M., Rohrer C. An experimental comparison of force-directed and randomized graph drawing algorithms // Proc. 2nd Intl. Symp. Graph Drawing. 1995. - Pp. 76-87. (Стр. 28.)

16. Brandts U. Social network analysis and visualization // IEEE Signal Processing Magazine. 2008. - Vol. 25, no. 6. - Pp. 147-151. (Стр. 53.)

17. Brandes U., Kopf B. Fast and simple horizontal coordinate assignment // Proc. 9th Int. Symposium on Graph Drawing.— 2001.— Pp. 31-44. (Стр. 60.)

18. Branke J. Dynamic graph drawing // Drawing Graphs, Springer Lecture Notes In Computer Science. — 2001. — Pp. 228-246. (Стр. 106.)

19. Cayley A. On the theory of the analytical forms called trees // Philosophical Magazine. — 1857. — Vol. 4, no. 13. — Pp. 172-176. (Стр. 7.)

20. Chen L., Buja A. Local multidimensional scaling for nonlinear dimension reduction, graph layout and proximity analysis // Journal of the American Statistical Association.— 2009.- Vol. 104, no. 485.— Pp. 209-219. (Стр. 106.)

21. Chiba N., Onoguchi K., Nishizeki T. Drawing planar graphs nicely // Acta Informatica.- 1985,-Vol. 22.-Pp. 187-201. (Стр. 9.)

22. Clauset A., Newman M. E. J., Moore C. Finding community structure in very large networks // Physical Review E. — 2004. — Vol. 70. — P. 066111. (Стр. 53.)

23. Coffman E., Graham R. Optimal scheduling for two processor systems // Acta Informatica. 1972. - Vol. 1. - Pp. 200-213. (Стр. 58.)

24. Cohen R., Havlin S. Scale-frec networks are ultrasmall // Phys. Rev. Lett 2003. - Vol. 90. - P. 058701. (Стр. 46.)

25. Davidson R., Harel D. Drawing graphs nicely using simulated annealing // ACM Trans. Graphics.- 1996. Vol. 15.- Pp. 301-331. (Стр. 27.)

26. Diehl S., Gorg C. Graphs, they are changing // Proc. 10th Int. Symp. on Graph Drawing. 2002,- Pp. 23-30. (Стр. 106.)

27. Dunne C., Shneiderman B. Improving graph drawing readability by incorporating readability metrics: A software tool for network analysts: Tech. Rep. 13: University of Maryland, 2009. (Стр. 35.)

28. Dwyer T. Two and a Half Dimensional Visualisation of Relational Networks: Ph.D. thesis / The University of Sydney. — 2005. (Стр. 106.)

29. Dwyer Т., Eckersley P. Wilmascope an interactive 3D graph visualisation system // Lecture Notes in Computer Science. — Vol. 2265. — 2002,- Pp. 442-443. (Стр. 112.)

30. Eades P. A heuristic for graph drawing // Congressus Numerantium. — 1984. Vol. 42. - Pp. 149-160. (Стр. 8.)

31. Eades P., Huang W., hee Hong S. A force-directed method for large crossing angle graph drawing: Tech. Rep. 640: University of Sydney, 2009. (Стр. 35.)

32. Eades P., Sugiyama K. How to draw a directed graph // Journal of Information Processing. — 1990. — Vol. 14, no. 4. — Pp. 424-437. (Стр. 56.)

33. Eades P., Wormald N. Edge crossings in drawings of bipartite graphs // Algorithmica. — 1994. — Vol. 11, no. 4. — Pp. 379-403. (Стр. 59.)

34. Eiglsperger M., Siebenhaller M., Kaufmann M. An efficient implementation of sugiyama's algorithm for layered graph drawing // Journal of Graph Algorithms and Applications. — 2005. — Vol. 9, no. 3. — Pp. 305-325. (Стр. 56.)

35. Eppstein D., Goodrich M. Т., Meng J. Y. Confluent layered drawings // Proc. 12th Int. Symposium on Graph Drawing. — 2004. — Pp. 184-194. (Стр. 81.)

36. Euler L. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Imperialis Petropolitanae. — 1736.-Vol. 8.-Pp. 128-140. (Стр. 7.)

37. An experimental comparison of four graph drawing algorithms / G. D. Battista, A. Garg, G. Liotta et al. // Computational Geometry.— 1997.- Vol. 7, no. 5,- Pp. 303-325. (Стр. 28.)

38. Exploring the computing literature using temporal graph visualization /

39. C. Erten, P. J. Harding, S. G. Kobourov et al. // Proc. of SPIE.— Vol. 5295. 2004. - Pp. 45-56. (Стр. 107.)

40. Extraction and visualization of call dependencies for large C/C++ code bases: A comparative study / A. Telea, H. Hoogendorp, O. Ersoy,

41. D. Reniers // Proc. IEEE VISSOFT. 2009. - Pp. 81-88. (Стр. 53.)

42. Fast unfolding of communities in large networks / V. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre // Journal of Statistical

43. Mechanics: Theory and Experiment. — 2008. — Vol. 2008, no. 10. — P. P10008. (Стр. 45 и 53.)

44. Fortunato S., Castellan C. Community structure in graphs / Ed. by B. Meyers. — Encyclopedia of Complexity and System Science. 2008. (Стр. 29, 46, 52 и 77.)

45. Fruchterman Т., Reingold E. Graph drawing by force-directed placement // Softw. Pract. Exp. — 1991. — Vol. 21, no. 11. — Pp. 11291164. (Стр. 27 и 86.)

46. Gaertler M., Wagner D. Visualizing Large Complex Networks / Ed. by G. Caldarelli. — Large Scale Structure And Dynamics Of Complex Networks. 2007. (Стр. 38.)

47. Gansner E. R., Koren Y. Improved circular layouts // Proc. 14th Int. Symposium on Graph Drawing. — 2006. — Pp. 386-398. (Стр. 64.)

48. Gansner E. R., Koren Y., North S. C. Graph drawing by stress majorization // Proc. 12th Int. Symposium on Graph Drawing. — 2004. — Pp. 239-250. (Стр. 9, 31, 32 и 106.)

49. Geometry-based edge clustering for graph visualization / W. Cui, H. Zhou, H. Qu et al. // IEEE Transactions on Visualization and Computer Graphics (Proc. Info Vis 2008).- Vol. 14.- 2008.- Pp. 1277-1284. (Стр. 81.)

50. Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. of the National Academy of Sciences of the USA. 1999.- Pp. 7821—7826. (Стр. 40 и 53.)

51. A global k-level crossing reduction algorithm / C. Bachmaier, F. J. Brandenburg, W. Brunner, F. Hiibner // Proc. Workshop on Algorithms and Computation. — 2009. — Pp. 70-81. (Стр. 60.)

52. Graph drawing contest report / C. A. Duncan, C. Gutwenger, L. Nachmanson, G. Sander // Proc. of the 18th Int. Symposium on Graph Drawing. Vol. 6502 of LNCS. - Springer-Verlag, 2010. (Стр. 17.)

53. Gusfield D. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. — USA: Cambridge University Press, 1999. (Стр. 75.)

54. Hadany R., Harel D. A multi-scale method for drawing graphs nicely // Proc. 25th International Workshop on Graph-Theoretic Concepts in Computer Science. — 1999. — Pp. 262-277. (Стр. 53.)

55. Ham F. van, Wijk J. J. van Interactive visualization of small world graphs // Proc. of the IEEE Symp. on Information Visualization. — 2004. Pp. 199-206. (Стр. 53.)

56. Hanstein H., Groh G. Interactive visualization of dynamic social networks // GI Jahrestagung (2). — 2008. Pp. 929-936. (Стр. 107.)

57. Harel D., Koren Y. A fast multi-scale method for drawing large graphs // Journal of Graph Algorithms and Applications. — 2000. — Pp. 183-196. (Стр. 53.)

58. Найу R. J. Essai d'une théorie sur la structure des crystaux. — 1784. (Стр. 7.)

59. Holten D. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data // IEEE Transactions on Visualization and Computer Graphics. 2006. - Vol. 12, no. 5. - Pp. 741-748. (Стр. 81.)

60. Holten D., Wijk J. J. van Force-directed edge bundling for graph visualization // 11th Eurographics/IEEE-VGTC Symposium on Visualization (Computer Graphics Forum; Proceedings of Euro Vis 2009).- 2009.-Pp. 983-990. (Стр. 81.)

61. Holten D., Wijk J. J. van A user study on visualizing directed edges in graphs // Proc. of 27th SIGCHI Conf. on Human Factors in Computing Systems. 2009. - Pp. 2299-2308. (Стр. 55.)

62. Introduction to Algorithms / Т. H. Cormen, С. E. Leiserson, R. L. Rivest, C. Stein. MIT Press, 2009. (Стр. 32 и 69.)

63. Jia Y., Garland M., Hart J. C. Hierarchial edge bundles for general graphs: Tech. rep.: 2009. (Стр. 81.)

64. К amada Т., Kawai S. An algorithm for drawing general undirected graphs // Inform. Process. Lett. — 1989. —Vol. 31.— Pp. 7-15. (Стр. 9, 31 и 86.)

65. Karp R. Reducibility among combinatorial problems // Complexity of Computer Computations.— Plenum Press, 1972.— Pp. 85—103. (Стр. 58.)

66. Klapisch-Zuber C. The genesis of the family tree // I Tatti Studies: Essays in the Renaissance. — 1991. — Vol. 4. — Pp. 105-129. (Стр. 7.)

67. Klimt В., Yang Y. Introducing the enron corpus // Proc. of First Conf. on Email and Anti-Spam. — 2004. (Стр. 96.)

68. Koren Y. Two-way visualization method for clustered data // Proc. 9th ACM SIGKDD international conference on Knowledge discovery and data mining.- 2003.-Pp. 589-594. (Стр. 53.)

69. Kruskal J. В., Seery J. B. Designing network diagrams // Proc. of the First General Conference on Social Graphics. — 1980. — Pp. 22-50. (Стр. 9, 30 и 106.)

70. Lambert A., Bourqui R., Auber D. Winding roads: Routing edges into bundles // Computer Graphics Forum. — 2010. Pp. 853-862. (Стр. 81.)

71. Lancichinetti A., Fortunato S., Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks // New Journal of Physics. 2009. — Vol. 11, no. 3.-P. 033015. (Стр. 53.)

72. Layout adjustment and the mental map / K. Misue, P. Eades, W. Lai, K. Sugiyama // Journal of Visual Languages and Computing. — 1995. — Vol. 6, no. 2.- Pp. 183-210. (Стр. 84 и 106.)

73. Line crossing minimization on metro maps / M. A. Bekos, M. Kaufmann, K. Potika, A. Symvonis // Proc. 15th Int. Symposium on Graph Drawing. 2008. - Pp. 231-242. (Стр. 69.)

74. Listing J. B. Vorstudien zur topologie // Vandenhoeck und Ruprecht.— 1847,-Vol. l.-Pp. 811-875. (Стр. 7.)

75. Mithun X. — Linux Package Dependency Visualization. — Master's thesis, Eindhoven University of Technology, 2009. (Стр. 53.)

76. Moreno J. L. Application of the group method to classification // New York: National Committee on Prisons and Prison Labor. — 1932. (Стр. 7.)

77. Multiscale visualization of small world networks / D. Auber, Y. Chiricota, F. Jourdan, G. Melancon // Proc. of Symposium on Information Visualization. — 2003. Pp. 75-81. (Стр. 53.)

78. Nachmanson L., Robertson G., Lee B. Drawing graphs with glee // Proc. 15th Int. Symposium on Graph Drawing. — 2007. — Pp. 389-394. (Стр. 60.)

79. Newbery F. J. Edge concentration: A method for clustering directed graphs // Proc. of 2nd Int. Workshop on Software Configuration Management. — 1989, — Pp. 76-85. (Стр. 81.)

80. Newman M. E. J. Coauthorship networks and patterns of scientific collaboration // Proceedings of the National Academy of Sciences. — 2004, — Pp. 5200-5205. (Стр. 53.)

81. Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Physical Review E. — 2004. — Vol. 69. — P. 026113. (Стр. 41.)

82. Noack A. An energy model for visual graph clustering // Proc. 11th Int. Symp. on Graph Drawing. — 2003. — Pp. 425-436. (Стр. 27 и 94.)

83. Noack A. An energy model for visual graph clustering // Journal of Graph Algorithms and Applications. — 2007.— Vol. 11, no. 2,— Pp. 453-480. (Стр. 53.)

84. Noack A. An energy model for visual graph clustering // Physical Review E.- 2009.- Vol. 79, no. 2.- P. 026102. (Стр. 53.)

85. Nöllenburg M. An improved algorithm for the metro-line crossing minimization problem // Proc. of the 17th Int. Symposium on Graph Drawing. 2009. - Pp. 381-392. (Стр. 69 и 72.)

86. On modularity clustering / U. Brandes, D. Delling, M. Gaertler et al. // IEEE Transactions on Knowledge and Data Engineering. — 2008. — Vol. 20.-Pp. 172-188. (Стр. 43.)

87. Pich С. Applications of Multidimensional Scaling to Graph Drawing: Ph.D. thesis / Universität Konstanz. 2009. (Стр. 31, 32, 33, 100 и 106.)

88. Pollner P., Palla G.} Vicsek T. Preferential attachment of communities: The same principle, but a higher level // Europhysics Letters. — 2005. — Vol. 73, no. 3.- P. 478. (Стр. 41.)

89. Purchase H. Which aesthetic has the greatest effect on human understanding? // Proc. 5th Int. Symp. on Graph Drawing. — 1998. — Pp. 248-261. (Стр. 84.)

90. Reingold E., Tilford J. Tidier drawing of trees // IEEE Trans, on Software Engineering.- 1981,-Vol. SE-7, no. 2.-Pp. 223-228. (Стр. 9.)

91. Sander G. Graph layout for applications in compiler construction // Theor. Comput. Sei. 1999. - Vol. 217, no. 2. - Pp. 175-214. (Стр. 60.)

92. A short note on the history of graph drawing / E. Kruja, J. Marks, A. Blair, R. Waters // Proc. 9th Int. Symp. on Graph Drawing. — 2001. — Pp. 602-606. (Стр. 7.)

93. Sugiyama К. Graph drawing and applications for software and knowledge engineers. — World Scientific, 2002. (Стр. 56 и 58.)

94. Sugiyama К., Tagawa S., Toda M. Methods for visual understanding of hierarchical system structures // IEEE Transactions on Systems, Man, and Cybernetics. 1981. - Vol. 11, no. 2. — Pp. 109-125. (Стр. 9 и 56.)

95. Tamassia R. On embedding a graph in the grid with the minimum number of bends // SI AM J. Computing. — 1987. — Vol. 16, no. 3. — Pp. 421-444. (Стр. 9.)

96. Tarjan R. E. Algorithm design // Communications ACM.— 1987.— Vol. 30, no. 3,- Pp. 205-212. (Стр. 9.)

97. A technique for drawing directed graphs / E. R. Gansner, E. Koutsofios, S. C. North, K.-P. Vo // IEEE Transactions on Software Engineering.— 1993. — Vol. 19, no. 3,- Pp. 214-230. (Стр. 56, 58 и 60.)

98. Tufte E. R. The Visual Display of Quantitative Information. — Graphics Press, Cheshire, CT, 1983. (Стр. 64.)

99. Tutte W. T. How to draw a graph // Proc. London Math. Society. — 1963, —Vol. 13, no. 52.-Pp. 743-768. (Стр. 9.)

100. Two polynomial time algorithms for the metro-line crossing minimization problem / E. Argyriou, M. A. Bekos, M. Kaufmann, A. Symvonis // Proc. 16th Int. Symposium on Graph Drawing. — 2009. — Pp. 336-347. (Стр. 69.)

101. Visualization and analysis of email networks / X. Fu, S.-H. Hong,

102. N. S. Nikolov et al. // Proc. of Asia-Pacific Symp. on Visualisation. — 2007,- Pp. 1-8. (Стр. 107.)

103. Zakharov P. Thermodynamic approach for community discovering within the complex networks: LiveJournal study // Physica A. — 2007. — Vol. 378,- Pp. 550—560. (Стр. 53.)

104. The AT&T graph collection.— http://www.graphdrawing.org. (Стр. 77.)

105. Система визуализации графов GraphVis3D.— http://code.google, com/p/graphvis. (Стр. 110.)

106. Graph visualization software.— http://www.graphviz.org. (Стр. 61 и 112.)

107. Many Eyes. — http: //manyeyes. alphaworks . ibm. com. (Стр. 112.)

108. Microsoft Automatic Graph Layout.— http://research.microsoft, com/en-us/projects/msagl. (Стр. 17, 61 и 118.)105. yEd graph editor. — http://www.yworks. com. (Стр. 112.)

109. Пупырев С. H., Пронченков А. . Прогнозирование загруженности автомобильных дорог // Труды конференции молодых ученых по информационному поиску. — Vol. 4. — 2010. — Pp. 64-78. (Стр. 16.)

110. Пупырев С. Н., Тихонов А. В. Визуализация динамических графов для анализа сложных сетей // Моделирование и анализ информационных систем.-— 2010. — Vol. 17, no. 1.—Pp. 117-135. (Стр. 118.)

111. Пупырев С. Н. — Система визуализации графов на плоскости и в пространстве. — Master's thesis, Уральский государственный университет, 2007. (Стр. 110.)

112. Пупырев С. Н. Визуализация безмасштабных графов // 40-я Всероссийская молодежная школа-конференция. — Vol. 40. — 2009. — Pp. 374-378. (Стр. 16.)

113. Пупырев С. Н. Визуализация структуры сообществ в графах // Системы управления и информационные технологии. — 2009. — Vol. 2, по. 36.-Pp. 21-27. (Стр. 118.)

114. Пупырев С. Н. Эффективное вычисление метрик эстетичности // Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. — 2010. — Vol. 74. — Pp. 171-179. (Стр. 117.)

115. Пупырев С. Н. Система визуализации графов GraphVis3D // 41-я Всероссийская молодежная школа-конференция. — Vol. 41,— 2010. — Pp. 501-507. (Стр. 16, 95 и 110.)

116. Nachmanson L., Pupyrev S. Visualizing a layered graph using edge bundling. U.S. patent application MS#328544.01. — 2010. (Стр. 16.)

117. Pupyrev S., Nachmanson L., Kaufmann M. Improving layered graph layouts with edge bundling // Proc. of 18th Int. Symp. on Graph Drawing.-Vol. 6502 of LNCS. — Springer-Verlag, 2010. (Стр. 16.)

118. Pupyrev S., Tikhonov A. Analyzing conversations with dynamic graphvisualization // Proc. of 10th Int. Conf. on Intelligent Systems Design and Applications. — 2010. (Стр. 16 и 116.)