Содержание к диссертации
Введение
Глава 0. Введение 4
0.1. Мотивация 4
0.2. Историческая справка 7
0.3. Цели работы 10
0.4. Основные результаты 11
0.5. Структура диссертации 12
0.6. Апробация 15
Глава 1. Базовые определения и модели визуализации графов 18
1.1. Определения 18
1.2. Сложные сети 23
1.3. Модели визуализации графов 25
1.3.1. Силовая модель 26
1.3.2. Многомерное шкалирование 29
1.3.3. Сравнение моделей 33
1.4. Недостатки существующих алгоритмов 35
Глава 2. Визуализация структуры сообществ 38
2.1. Описание алгоритма 40
2.2. Вычислительная сложность 44
2.3. Экспериментальная часть 47
2.4. Заключение 52
Глава 3. Визуализация ориентированных графов 55
3.1. Метод Сугиямы 56
3.2. Метод связывания ребер 62
3.2.1. Группировка ребер 64
3.2.2. Рисование ребер 67
3.2.3. Определение координат 69
3.2.4. Рисование линий метро 70
3.3. Экспериментальная часть 77
3.4. Заключение 81
Глава 4. Визуализация динамических графов 83
4.1. Алгоритм визуализации динамических графов 86
4.1.1. Силовая модель
4.1.2. Пружинная модель 89
4.2. Экспериментальная часть 95
4.3. Обзор существующих подходов 106
4.4. Заключение 107
Глава 5. Программный комплекс визуализации графов 110
5.1. Введение 110
5.2. Архитектура 112
5.3. Основные возможности 115
5.4. Заключение 118
Результаты и выводы 120
Литература 122
- Многомерное шкалирование
- Недостатки существующих алгоритмов
- Метод связывания ребер
- Алгоритм визуализации динамических графов
Введение к работе
Актуальность темы. Графы - это простая, мощная, элегантная абстракция, применяемая во многих областях науки и техники. Графы позволяют моделировать произвольные системы, иредставимые в виде набора объектов и связей между ними. За последние десятилетия популярность графов значительно возросла. Объясняется это их универсализмом и независимостью от предметной области, что позволяет обрабатывать и анализировать системы произвольной сложности. Информационный взрыв, вызванный развитием Всемирной Паутины, и развитие компьютерных технологий сделали доступным большое количество информации. Сегодня теория графов используется в биологии для анализа взаимодействий между протеинами, в радиоэлектронике - при проектировании печатных схем, в химии - для описания кинетики сложных реакций, в экономике - при оптимизации маршрутов и грузоперевозок, в социологии - для изучения связей и закономерностей в обществе и т.п. Графы являются центральным инструментом при разработке программного обеспечения, структурировании бизнес-процессов, проектировании баз данных и используются во многих областях математики и компьютерных наук.
Считается, что 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] и [14] диссертанту принадлежат разработка и реализация алгоритма, а также доказательства всех утверждений, Л. Нахмансону - постановка задачи. Из остальных совместных работ [12] и [18] в диссертацию вошли результаты, полученные лично автором.
Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:
Всероссийская молодежная школа-конференция «Современные проблемы математики» (Кунгурка). Екатеринбург, 2009 и 2010.
Конференция молодых ученых по информационному поиску (RuSSIR). Воронеж, 2010.
International Symposium on Graph Drawing (Graph Drawing). Konstanz, Germany, 2010.
International Conference on Intelligent Systems Design and Applications (ISDA). Cairo, Egypt, 2010.
Научный семинар «Алгебраические системы». УрГУ, Екатеринбург.
Первоначальные результаты работы по укладкам направленных графов и визуализации сложных сетей также представлялись на докладе во время первой трехмесячной научной стажировки автора в Microsoft Research (Рэдмонд, США) в 2009. Работа, описывающая метод связывания ребер для неориентированных графов, была представлена в Microsoft Research в 2010 во время второй трехмесячной научной стажировки. Эта работа была также представлена на международной конференции Symposium on Graph Drawing (Konstanz, Germany) в 2010, которая является крупнейшим ежегодным научным событием для исследователей и разработчиков в области визуализации графов. В рамках конференции между участниками проводится соревнование Graph Drawing Contest, на котором определяются лучшие алгоритмы и методы автоматического рисования графов. В 2010 изображения, построенные автором при помощи метода связывания ребер, были признаны лучшими в номинации «Link Routing».
Структура работы. Диссертационная работа состоит из 136 страниц машинописного текста, включающего введение, пять глав и заключение, а также рисунки, таблицы и список литературы, содержащий 115 наименований.
Многомерное шкалирование
Понятие качественного способа рисования обычно формализуются с помощью таких концепций, как эстетичность и читабельность изображения. Эстетические критерии специфицируют свойства изображений, которые желательно применять в наибольшей степени, чтобы повысить наглядность изображения. Широко используются следующие эстетические критерии. Минимизация пересечений. Изображение должно содержать как можно меньше попарных пересечений ребер. Минимизация сгибов. Ребра должны рисоваться с малым количеством сгибов. Длина ребер. Ребра должны иметь по возможности одинаковую длину Перекрытие вершин и ребер. Требуется избегать наложения вершин друг на друга и перекрытий ребер с вершинами. Максимизация разрешения. Необходимо, чтобы ребра, инцидентные одной вершине, расходились под максимально возможным углом. Ортогональность. Ребра должны быть нарисованы параллельно осям координат. Минимизация области размещения. Граф более читабелен, если вершины равномерно распределены по всей доступной области рисования. Кластеризация. Вершины из плотной группы вершин требуется изображать рядом друг с другом. Симметрия. Изображение должно наглядно демонстрировать существующие симметрии графа. Большинство из приведенных эстетических критериев, как задачи оптимизации, являются сложными для решения с вычислительной точки зрения. Поэтому обычно при построении изображений используются различные эвристики и стратегии приближенных решений. Под «сложными сетями» мы будем понимать системы, состоящие из реальных объектов и связей между ними. Другими словами, сложная сеть -граф, построенный на основе реальных данных. Примерами сложных сетей являются граф ссылок в сети Интернет, социальные сети, транспортные сети, биологические системы (взаимодействия протеинов), сети цитирования в научных работах и т.д. Сложная сеть моделируется графом, однако этот граф, как правило, имеет определенную структуру и обладает характерными признаками. Размер Количество вершин в графе - величина ни чем не ограниченная и зависит только от предметной области и доступных данных. На сегодняшний момент вычислительные ресурсы позволяют обрабатывать сети, состоящие из более чем миллиарда вершин. При этом все сложные сети являются разрежепными с количеством ребер, пропорциональным количеству вершин т = 0{п). Эффект малого мира Рассмотрим среднее кратчайшее расстояние между всеми парами вершин в графе: где dij - кратчайшее расстояние между вершинами г и j. Для сложных сетей введенная величина I принимает малые значения, обычно из интервала [2..20] (отсюда появилась известная гипотеза «six degree of separation», которая предполагает, что любые два человека на Земле связаны цепочкой знакомств не длиннее шести шагов). Эффект малого мира - очень важное свойство, обеспечивающее, например, быстрое распространение информации в сети. Распределение степеней вершин Определим через рк долю вершин в сети, имеющих степень к. Эквивалентно, pk - вероятность того, что выбранная случайным образом вершина графа имеет степень к. Для сложных сетей степени вершин имеют степенное распределение (power-law), т.е. pk к а для некоторого положительного параметра а. Для большинства реальных сетей а Є [2..3]. Такие сети также названы безмасштабными (scale-free), поскольку средняя степень вершины в них не является характерной, т.е. отсутствует характерный масштаб. Для такой топологии характерно наличие малого числа хабов - вершин наибольшей степени - и большого числа вершин малой степени. Структура сообществ Сложные сети имеют хорошо выраженную структуру естественных сообществ: вершины сети разделены по группам, которые слабо связаны между собой, но имеют большую плотность ребер внутри. Природа такого разделения зависит от предметной области. Например, в социальных сетях сообщества формируются на основе общих интересов, рода деятельности и места жительства участников сети. В программных проектах наблюдается большое количество связей между объектами со схожей функциональностью в пределах одного модуля.
К настоящему моменту для сложных сетей замечено и изучено большое количество общих свойств и признаков. Помимо обозначенных отметим наличие гигантской компоненты, устойчивость к случайному удалению узлов, спектральные свойства матрицы смежности и др. Также важны и часто изучаются вопросы динамики (роста) сетей. Например, отмечено, что с ростом сложной сети ее диаметр не увеличивается, как может показаться, а уменьшается.
Недостатки существующих алгоритмов
Задача визуализации состоит в создании изображения, позволяющего анализировать структуру графа и выявлять его характеристики. Простые свойства, такие как количество вершин или диаметр графа, легко получить, посчитав некоторые статистики. Другие (например, распределение степеней вершин) просматриваются при помощи специально построенных графиков. Однако существуют характеристики графа, которые объяснить и анализировать сложнее. Аналитические укладки (analytic layouts, [43]) представляют граф в виде, подчеркивающим его определенное свойство или характеристику, упрощая визуальный анализ.
Данная глава посвящена описанию разработанного нами метода визуализации графов, который позволяет выделять общее свойство многих реальных сетей - структуру сообществ, т.е. разделение вершин по группам, которые слабо связаны между собой, но имеют большую плотность ребер внутри. Природа такого разделения сети на сообщества зависит от предметной области. Например, в социальных сетях сообщества формируются на основе общих интересов, рода деятельности и места жительства участников сети. В программных проектах наблюдается большое количество связей между объектами со схожей функциональностью в пределах одного модуля. Такая «неоднородность» наблюдается для многих реальных графов со степенным распределением степеней вершин и де-факто является общим свойством всех сложных сетей.
Изображение графа с выделенной структурой сообществ представлено на рис. 2.1(b). Вершины, принадлежащие одному сообществу, расположены рядом друг с другом. Несвязанные вершины визуально разделены. Стоит отметить, что на практике некоторые объекты нельзя строго отнести к одному определенному сообществу. Это объясняет нечеткие границы сообществ на изображении. Важным преимуществом разработанного алгоритма является скорость работы: с его помощью мы построили изображение социальной сети Live Journal (http://www.livejournal.com), содержащей более четырех миллионов вершин. Очень небольшое количество современных алгоритмов способно обрабатывать графы таких размеров.
Приведем необходимые определения. В данной главе будут рассматриваться укладки простых связных неориентированных графов в двумерном пространстве. Ребра будут отображаться в прямые, соединяющие соответствующие точки, поэтому под укладкой графа будем понимать укладку вершин графа. Более того, для повышения наглядности на некоторых изображениях мы иногда не рисуем ребра.
Под сообществом графа G мы понимаем подмножество его вершин С с V. Разбиение графа на сообщества - это разбиение множества вершин на непересекающиеся сообщества. Для измерения качества разбиения мы используем метрику, предложенную в [47], которая называется модульность (modularity):
где сумма берется по всем сообществам Ci,...,Cs графа. Через Ik мы обозначаем количество ребер между вершинами сообщества Ck, а через dk -сумму степеней вершин этого сообщества. Под т, как обычно, понимается количество ребер в G. Интуитивно смысл выражения 2.1 следующий. «Хорошим» сообществом считается то, в котором вершины тесно связаны друг с другом, и имеют небольшое количество «внешних» ребер, соединяющих их с остальным графом (рис. 2.2(a)). Первое слагаемое формулы модульности дает больший вес разбиениям с такими «плотными» сообществами. Однако в таком простом виде метрика качества использоваться не может, т.к. наилучшим будет разбиение, содержащее единственное сообщество со всеми вершинами графа. Поэтому вводится дополнительное нормализующее второе слагаемое, которое равно ожидаемому количеству ребер в сообществе с данными степенями вершин (т.е. количеству ребер в случайном графе с теми же степенями вершин). Таким образом, если количество ребер в сообществах заметно отличается от ожидаемого, то модульность разбиения будет высока. Фактически модульность показывает, насколько плотность ребер внутри сообществ больше по сравнению со случайным графом, имеющим то же распределение степеней вершин. На практике значения модульности Q 0.3 означают, что граф имеет хорошо выраженную структуру сообществ.
Эксперименты показывают, что большое количество реальных сетей обладают хорошо выраженной структурой сообществ [78]. Более того, фактор-граф, вершинами которого являются сообщества, сам является безмасштабным и также может быть разбит на непересекающиеся сообщества [85]. Таким образом, можно говорить об иерархии, в которой мелкие сообщества оказываются вложенными в более крупные. Каждый уровень иерархии представляет собой набор непересекающихся множеств: верхний уровепь содержит единственное сообщество, содержащее вес вершины исходного графа, на нижнем уровне количество сообществ совпадает с количеством вершин графа (это «вырожденные» сообщества, состоящие из одной вершины). Сообщества 1-ого уровня будем обозначать С1к, где к Є [1..количество сообществ уровня I]. Вырожденное множество для удобства будем отождествлять с его единственным элементом. Размером сообщества \С1к\ назовем количество содержащихся в нем вершин графа.
Метод связывания ребер
Задачей данного этапа является присвоение каждой вершине се вертикальной координаты (здесь и далее мы предполагаем, что уровни располагаются и нумеруются сверху вниз). Для этого строится разбиение множества вершин V на подмножества Li,..., Lh так, что для всех дуг графа є = (и, г ), где и Є Li и v є Lj, выполняется і j. Высотой разбиения называют количество уровней h, шириной w - максимальное число вершин на одном уровне. Для искомого разбиения можно сформулировать набор критериев, определяющих качество результирующего изображения. Во-первых, вершины должны быть распределены по уровням равномерно, поскольку эстетически наиболее привлекательно выглядят компактные размещения графов. Во-вторых, короткие дуги на итоговом изображении графа предпочтительнее длинных, что влечет ограничение на суммарную длину дуг в разбиении. Под длиной дуги е = (u,v) с и Є L; и v Є Lj мы здесь понимаем число j — і, также называемое протяоїсенностью. Задача поиска разбиения графа с минимальной суммарной протяженностью дуг уже оказывается NP-трудной (precedence constrained multiprocessor scheduling) [23]. Наиболее известные приближения используют методы минимизации потоков в сети [1]. Также популярны симплекс методы, которые хотя и не полиномиальны, но на практике работают довольно быстро [94]. После построения разбиения вершин исходный граф преобразуется к строго поуровневому виду. Для этого каждая дуга е = (и, v) с и Є Li и v Є Lj, проходящее через несколько уровней, т.е. имеющее протяженность j — i больше единицы, заменяется на последовательность вершин и = di, di+i,..., dj = v и ребер (d,, di+1), (dm, di+2),..., (dj_i, dj) (рис. 3.2(c)). Вершины dk для г к j будем называть фиктивными, а вершины di и dj - реальными. Фиктивные вершины также добавляются в соответствующие элементы разбиения Ь . Если для двух ребер (гіі,г»і) и (ггг, ) поуровневого графа выполняется щ є L{,v\ є Li+i и щ Є L V2 Є Li+i, то будем называть их одноуровневыми. Далее мы будем различать исходный граф G и ассоциированный с ним поуровневый граф. В последующих шагах алгоритма Сугиямы ориентированность ребер не используется, поэтому мы будем считать поуровневый граф неориентированным. Таким образом, можно сформулировать
Целью данного шага алгоритма является определение такого порядка вершин графа Gp на каждом уровне, что количество пересечений ребер минимально. Заметим, что это количество не зависит от фактических координат вершин на уровне, а полностью определяется их относительным порядком. Соответствующая задача поиска оптимального порядка вершин является NP-трудной даже в случае графа с двумя уровнями (2-layer crossing minimization) [33]. Существующие решения условно делятся на две категорий: (1) глобальная оптимизация числа пересечений [48], при которой все уровни графа обрабатываются одновременно, и (2) локальная оптимизация, последовательно минимизирующая пересечения между двумя соседними уровнями.
На этом этапе метода Сугиямы определяются окончательные координаты вершин графа. Вертикальные координаты определяются положением уровней, которые располагают сверху вниз с фиксированным шагом. При нахождении горизонтальных координат учитывают несколько критериев: порядок следования вершин, найденный на предыдущем шаге, должен быть сохранен, исходные ребра должны иметь малое количество изгибов. Также если вершины графа изображаются не точками, а имеют более сложную форму, то они не должны пересекаться с ребрами. В качестве возможных решений отметим подходы на основе линейного программирования [94], модель линейных сегментов [88], эвристику самого длинного пути [17].
Наконец, конечное изображение получается рисованием ребер графа. Если ребра графа представляются в виде ломанных, то требуется просто соединить соответствующие фиктивные вершины. В некоторых системах рисования графа предпочтительней иметь гладкие ребра без изломов. В этом случае задача проведения ребер выделяется в отдельный этап, в ходе которого строятся сплайны, проходящие через заданный набор точек, и не пересекающие вершины графа [75].
Алгоритм визуализации динамических графов
Каждый набор данных - это множество сообщений (событий коммуникаций) между участниками сети. Для каждого сообщения известен его отправитель, получатель и время отправления. В данной работе мы не учитывали текст сообщения для анализа. Основные характеристики использованных наборов данных представлены в таблице 4.2.
Применение предлагаемого подхода к изучению динамики связей внутри сообщества предполагает разбиение изучаемого периода времени на непересекающиеся подпериоды. Каждому из этих подпериодов соответствует отдельный слой визуализации, содержащий укладку графа, сопоставленного этому подпериоду. При выборе разбиения мы учитывали следующие факторы: представляется удобным выбор разбиения, при котором все подпериоды имеют равную продолжительность, т.к. такое разбиение позволяет наглядно визуализировать процессы роста, убывания и стабилизации активности взаимодействий в сообществе в течение всего исследуемого периода; общее число подпериодов не должно быть слишком большим, т.к. это, с одной стороны, существенно замедляет расчеты, а, с другой стороны, уменьшает наглядность результирующей визуализации; длительность подпериода удобно выбирать кратной периоду некоторого внутреннего (присущего рассматриваемому сообществу) колебания интенсивности общения. Таких «сезонных составляющих» интенсивности общения может быть несколько: часто прослеживаются суточная (рис. 4.2(a)), недельная (рис. 4.2(b)), месячная и годовая периодичности. Наличие той или иной периодичности зависит от конкретного сообщества, так, например, суточная периодичность наблюдается в случаях, когда все участники сообщества или основная их масса принадлежит одному часовому поясу, а месячная периодичность обычно зашумлена некратной ей недельной, но может проявляться в общении, связанном, например, с производственным циклом. Исходя из приведенных выше соображений, в наших экспериментах мы использовали разбиения на подпсриоды длительностью в 1, 7, 30, 60 и 365 суток, получая при этом приблизительно от 5 до 25 слоев визуализации. Построение графа общения для каждого подпериода После разбиения периода на непересекающиеся подпсриоды необходимо преобразовать данные истории сообщений в граф общения, соответствующий каждому подпер иоду. Для этого: производится поиск всех пользователей, которые в течение анализируемого подпериода фигурировали как отправители или как получатели сообщений; каждому такому пользователю сопоставляется узел с весом, равным общему числу сообщений, отправленных этим пользователем за под-период; если в течение подпериода пользователь А отправил хотя бы одно сообщение пользователю В, в граф добавляется направленное ребро (А,В), с весом равным общему число сообщений, отправленных от А к В за рассматриваемый подпериод. Полученная последовательность взвешенных ориентированных графов содержит сводную статистику общения между пользователями в течение каждого подпериода. Подготовка графов общения для визуализации Стандартные трудности при анализе и визуализации социальных сообществ связаны с тем, что большинство таких сообществ имеют степенное распределение числа пользователей по объему их общения, а также проявляют свойство ассортативности по числу собеседников, т.е. имеется явная положительная корреляция между числом собеседников у двух общающихся пользователей. Эти особенности приводят к тому, что граф общения, соответствующий каждому слою, оказывается немасштабируемым и содержит гигантскую плохо разделимую компоненту с очень плотным ядром [4].
Визуализация такого графа «в лоб» практически нечитаема (рис. 4.3(a)). Кроме того, большое число ребер в плотном ядре немасштабирусмого графа делает существующие алгоритмы укладки неэффективными [84]. В связи с этим, в наших экспериментах мы использовали специально «прореженные» графы общения, т.е. подграфы, построенные путем удаления ма-линформативных узлов и ребер. Для построения таких подграфов нами использовались два алгоритма:
Похожие диссертации на Модели, алгоритмы и программный комплекс визуализации сложных сетей
