авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Модели, алгоритмы и программный комплекс визуализации сложных сетей

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

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

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС

ВИЗУАЛИЗАЦИИ СЛОЖНЫХ СЕТЕЙ

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

программ

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

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

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

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

Официальные оппоненты: доктор технических наук, профессор Гайдамакин Николай Александрович кандидат физико-математических наук Волканин Леонид Сергеевич

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

Защита состоится декабря 2010 в ч. на заседании Диссертацион ного совета Д 212.286.10 при ГОУ ВПО «Уральский государственный универ ситет им. А.М. Горького» по адресу: 620000, г. Екатеринбург, пр. Ленина 51, комн. 248.

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

Автореферат разослан ноября 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 от yWorks). В нашей стране задачами визуализации ин формации и рисованием графов занимаются, к примеру, в Новосибирском государственном университете, Уральском государственном университете, Институте математики и механики УрО РАН.



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

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

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

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

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

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

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

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

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

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

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

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

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

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





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

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

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. Научный семинар «Алгебраические системы». УрГУ, Екатеринбург.

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

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

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

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

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

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

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

|| || + || ||.

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

|| ||2.

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

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

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

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

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

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

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

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

[ ] ( ) =, (1) = где сумма берется по всем сообществам 1,..., графа. Через обознача ется количество ребер между вершинами сообщества, a через – сумма степеней вершин этого сообщества. Под, как обычно, понимается коли чество ребер в. Модульность показывает, насколько «плотность» ребер внутри сообществ больше по сравнению со случайным графом, имеющим то же распределение степеней вершин.

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

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

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

Изначально строится сообществ, содержащих по одной вершине графа.

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

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

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

иерархии мы строим фактор-граф. Его вершинами являются сообщества 2 2 второго уровня 1, 2,...,, и каждая пара сообществ, имеющая смеж (, ) ные вершины, соединена ребром весом | || |, где (, ) – количество ребер между вершинами сообществ и. Далее строится укладка графа с использованием силовой модели, в которой учитываются веса ребер. В результате мы получаем укладку, в которой «связанные» сообщества будут расположены рядом друг с другом.

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

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

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

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

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

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

В поуровневой схеме рисования графов [10] строится разбиение вер шин графа = (, ) на подмножества 1,..., так, что для всех дуг графа = (, ), где и, выполняется. После построения разбиения вершин исходный граф преобразуется к строго поуровневому графу. Для этого каждая дуга = (, ) с и, проходя щая через несколько уровней, заменяется на последовательность вершин S0 S11 S0 S S S S S S S S8 S S8 S S10 S S10 S S S S S S S S13 S S12 S6 S12 S S14 S19 S14 S S20 S S18 S S21 S17 S21 S S7 S (a) Стандартная укладка (b) Связывание ребер Рис. 2. Диаграмма состояний приложения notepad.exe.

=, +1,..., = и ребер (, +1 ), (+1, +2 ),..., (1, ). Вершины для называются фиктивными, а вершины и – реальными.

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

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

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

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

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

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

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

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

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

Теорема 7. Сложность алгоритма вычисления порядка с ми нимальным количеством пересечений дуг графа составляет (| | + || log || + ), где | | – количество ребер соответству ющего поуровневого графа, || – количество дуг графа и – суммарная длина дуг графа.

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

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

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

Метод послойной визуализации состоит из следующих шагов.

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

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

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

F F E F E E D D A A A D C B C B B C E F F E D D F E B D C C C B B E F F E F D D E C B C C B D B (a) (b) (c) Рис. 3. Граф, состоящий из трех слоев. (a) Укладки без учета ментальной карты. (b) Сохранение ментальной карты. (c) Послойная визуализация.

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

вершины с одинаковыми метками должны иметь близкие позиции.

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

ментальные силы, притягивающие вершины с одинаковыми метками.

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

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

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

= + + +. (2) Остается открытым вопрос, как минимизировать. Заметим, что на по следовательность 1, 2,..., графов можно смотреть, как на один большой граф, объединяющий в себе все вершины и ребра каждого гра фа последовательности. Граф-объединение = (, ) состоит из мно жества вершин = и ребер = {(, ) =1 = : = } {(, ), }. В этом смысле компоненты = и – это части энергии притяжения. Поэтому для минимиза ции выражения 2 можно применять классические итеративные методы ми нимизации энергии для статических графов. В диссертации установлено (теоремы 9 и 10), что сложность алгоритма визуализации последова тельности графов 1, 2,..., равна суммарной сложности визуализа ций каждого из графов 1, 2,...,.

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

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

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

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

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

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

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

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

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

Система доступна для свободного скачивания и использования на ре сурсе http://code.google.com/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 Draw ing. — 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. С. 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] Пупырев С.Н. Система визуализации графов GraphVis3D // Тру ды 41-й всероссийской молодежной школы-конференции. – Екатерин бург, 2010. № 41. С. 501–507.

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



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.