Модели, алгоритмы и программный комплекс визуализации сложных сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Пупырев, Сергей Николаевич

• Пупырев, Сергей Николаевич
• кандидат физико-математических наук
• 2010

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

Глава 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. Роль и место диссертационной работы в общей картине анализа информации.

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

Список литературы диссертационного исследования кандидат физико-математических наук Пупырев, Сергей Николаевич, 2010 год

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.)