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

• Автор: Пупырев, Сергей Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Екатеринбург
• Количество страниц: 136 с. : ил.

Оглавление

Глава 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. Экспериментальная часть.
2.4. Заключение
Глава 3. Визуализация ориентированных графов
3.1. Метод Сугиямы.
3.2. Метод связывания ребер
3.2.1. Группировка ребер.
3.2.2. Рисование ребер.
3.2.3. Определение координат.
3.2.4. Рисование линий метро.
3.3. Экспериментальная часть
3.4. Заключение.
Глава 4. Визуализация динамических графов
4.1. Алгоритм визуализации динамических графов
4.1.1. Силовая модель
4.1.2. Пружинная модель
4.2. Экспериментальная часть
4.3. Обзор существующих подходов
4.4. Заключение
Глава 5. Программный комплекс визуализации графов 1X
5.1. Введение
5.2. Архитектура.
5.3. Основные возможности.
5.4. Заключение
Результаты и выводы
Литература


Биологи изучают теорию ветвящихся процессов и открывают методы рисования деревьев с разнообразными ограничениями. Даже в психологии возникают планарные графы и их изображения (Левин, ). Новейшая история теории рисования графов начинается с -х годов и связана с появлением автоматических алгоритмов визуализации. В научном обществе формируется группа ученых целенаправленно занимающаяся визуализацией графов. Теория рисования графов выделяется в отдельную область математики. Отметим лишь несколько самых заметных достижений. Самыми популярными методами рисования являются алгоритмы, основанные на физических аналогиях, предложенные в работах P. Чем меньше пересечений линий на социограмме, тем она лучше. T. Kamada и S. Kawai |). ПоуровневыЙ подход для рисования ориентированных графов был предложен Сугиямой в []. Значительный вклад в рисование деревьев внесли Reingold и Г1 ilford []. Планарными укладками графов (без пересечения ребер) занимались, например, Tutte [], Chiba [], Tarjan []. Ортогональные изображения графов, в которых ребра изображаются прямыми, параллельными осям координат рассматривали в своих работах Tamassia [], Di Battista []. Стоит отмстить, что многие методы в теории рисования графов неоднократно «переизобрета-лись». Например, метод многомерного шкалирования, предложенный для визуализации графов в середине -х [], успешно применялся для рисования диаграмм Крускалом в начале -х [бб]. За последнее десятилетие теория рисования графов заметно возмужал ла. Ежегодно проводится крупная международная конференция (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 Visual Studio), работа отмечена призами на международной конференции (Symposium on Graph Drawing). Разработан метод анализа изменяющихся во времени сетей с использованием послойной (2. D) визуализации графов.