Диссертация (1090614), страница 12
Текст из файла (страница 12)
Переход к шагу 2.2. Выбираются все связи между вершиной и линией темы (Connection).Переход к шагу 3.3. Связи сортируются по одному из выбранных принципов: по значениюатрибутов,поколичествуатрибутов,размеруобрамляющегопрямоугольника атрибутов. Переход к шагу 4.4. Инициализация оптимальной ширины W нулем. Далее выполняетсяподсчетоптимальнойшириныWипозицийподписейсвязей,необходимой для размещения вторичной вершины.
Переход к шагу 5.5. К переменной W прибавляется ширина обрамляющего прямоугольникаатрибутов первой связи. Если связь не имеет атрибутов, то прибавляетсяудвоенное значение заданного минимально возможного расстояниямежду связями. Переход к шагу 6.846. Для последующих связей обрамляющий прямоугольник атрибутов будетрасполагаться под предыдущим, тем самым переменная W будетувеличена на часть ширины атрибутов и на величину минимальногорасстояния между подписями и самими связями (чтобы подпись ненакрывала соседние связи). Переход к шагу 7.7.
В случае, если атрибуты вновь добавляемой связи будут выходить занижнюю границу заданной горизонтальной полосы размещения, то ониначинают снова располагаться с верхней части этой полосы. Переход кшагу 8.8. Текущая координата X увеличивается на величину W. Переход к шагу 9.9. Последующиевершиныдобавляютсяаналогичнымобразом.Yкоордината вершины будет установлена как минимум между максимальнодопустимойYкоординатойисуммойвысотобрамляющихпрямоугольников связей. Переход к шагу 10.10.
Конец алгоритма.Результат: вершина из верхней группы вершин расположена относительно линиитемы.Примеры полученных размещений показаны на Рис. 2.11 и Рис. 2.12.Таким образом будет получено размещение, которое гарантирует отсутствиепересечений связей между вторичными вершинами и линией темы.85Рис. 2.12. Результат применения алгоритма автоматического размещения «одналиния темы».2.3.4. Геометрическая модель автоматического размещения «две линиитемы»Размещение «две линии темы» аналогично размещению «одна линия темы».Алгоритм 2.14. Автоматическое размещение «две линии темы».Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.
1, 2 -вершины, выбранные в качестве линий темы.Последовательность шагов:1. Выбранные две линии темы 1 и 2 сортируются либо в случайномпорядке, либо по значению заданного атрибута. Переход к шагу 2.862. Задаются расстояние между линиями темы, высота горизонтальнойполосы размещения вторичных вершин над первой линией темы, высотагоризонтальной полосы для размещения вторичных вершин под второйлинией темы. Переход к шагу 3.3. Выбираются все вершины, смежные с первой линией темы. Онирасполагаются в заданную горизонтальную полосу над линией темы поалгоритму «одна линия темы» (Алгоритм 2.12). Переход к шагу 4.4.
Выбираются все вершины, смежные со второй линией темы. Онирасполагаются в заданную горизонтальную полосу под линией темы поалгоритму «одна линия темы» (Алгоритм 2.12). Переход к шагу 5.5. Затем выбираются все вторичные вершины, которые связаны с двумялиниями темы. Аналогично шагам 4-7 алгоритма «одна линия темы»(Алгоритм 2.12) величина оптимальной ширины будет являтьсямаксимумом из ширины, найденной для связей, соединенных с первойлинией темы, и ширины, найденной для связей, соединенных со второйлинией темы. Переход к шагу 6.6. Вершины, которые не связаны ни с одной из линий темы, будут помещеныпоследовательно между линиями темы, либо под ними с применениемкругового покомпонентного размещения.
Переход к шагу 7.7. Конец алгоритма.Результат: выполнено автоматическое размещение вершин графа на основе двухвыбранных линий тем.87Рис. 2.13. Результат применения алгоритма автоматического размещения «двелинии темы».88Рис. 2.14. Результат применения алгоритма автоматического размещения «двелинии темы».На Рис. 2.13 и Рис. 2.14 представлены примеры результатов размещения «две линиитемы». Из данных примеров видно, что отображения всех вторичных вершин непересекаются между собой. Кроме того, отсутствуют пересечения связей междувторичными объектами и линиями тем.
Параметры отображения атрибутоввыбраны таким образом, что атрибуты вершин и связей вторичных объектов непересекаются между собой. За счет этого обеспечивается наглядное представлениеподграфа, состоящего из вершин – линий тем, смежных с ними вершин и связеймежду линиями тем и вторичными вершинами.89Выводы по 2 главе2.4.1. Разработаны и реализованы геометрические модели базовых алгоритмовавтоматического размещения сети на плоскости, в том числе алгоритм наоснове метода физических аналогий, способные работать с графами большихразмеров.2.
Разработанаиреализованагеометрическаямодельавтоматическогоразмещения «быстрый павлиний хвост», основанная на методе физическиханалогий.Спецификапредложеннойоптимизациискоростныххарактеристик алгоритма достигается за счет анализа только локальнойобласти на плоскости при вычислении взаимодействующих сил междуобъектами графа.3. Разработан и реализован алгоритм многополосного размещения графа наплоскости, включающий в себя формализацию процедуры расположениясмежных с линией темы вершин. Нововведение заключается в использованиизначений атрибутов и их визуальных характеристик (размеры) приразмещении вторичных вершин относительно линии темы.4.
Геометрическаямодельалгоритмамногополосногоавтоматическогоразмещения графа впервые реализована в среде для визуализации и анализаграфов больших размеров.5. Разработаны и реализованы частные случаи алгоритма многополосногоразмещения: автоматического размещения «одна линия темы» и «две линиитемы».90ГЛАВА 3.Визуальный анализ графа социальной сети, допускающеговыделение подграфовВ данной главе предлагается методика геометрического моделированияструктурыграфа,основаннаянаалгоритмевыделениясообществ,предложенного в [75-77].3.1.Методика выделения сообществМетодика выделения сообществ основана на модификации алгоритма,использующего показатель модулярности графа, и предложенного в [61, 62,63].Предлагаемая методика предусматривает проведение предобработкиданных, которая заключается в получении графа и заданного мультиграфапутем замены кратных связей в мультиграфе на одну с весом, равнымколичеству кратных связей между парой вершин.Проведем аналогию между задачей выделения плотно связанных группвершин из графа с задачей сжатия данных.Рассмотрим задачу получения уникальных имен для вершин.
Простойметод получения уникальных имен для вершин - использование кодаХаффмана, который обеспечивает сжатие информации путем назначениясамых коротких кодовых слов самым частым событиям или объектам, идлинных кодовых слов менее частым. Затем для создания общегопредставления сети необходимо отделить важную структурную информациюот несущественных деталей. В основе метода лежит двухуровневое разбиениеинформации. Метод использует уникальные имена для более общих объектов- сообществ, и повторяющиеся имена для более мелких деталей - обозначениявершин в каждом сообществе.91Использование двухуровневого описания позволяет закодироватьслучайное блуждание с использованием меньшего количества информации,чем при одноуровневой схеме кодирования.
Кроме того, данный подходпоможет извлечь структуру сети на основе того предположения [44], что, вобщем случае, случайное блуждание будет статистически больше проводитьвремени внутри групп вершин, чем при перемещении от группы к группе.Таким образом, разбиение на сообщества будет описываться верхнимуровнем двухуровневого кодирования. Основная идея заключается в том, чтонет необходимости непосредственно выполнять двухуровневое кодирование.Достаточно лишь считать верхнюю границу длины кодового слова,необходимую для кодирования вершины. Процесс разбиения сети насообщества подразумевает минимизацию длины кодового слова.Рассмотрим множество всех возможных разбиений множествавершин графа .
Разбиение M ∈ обозначает разбиение вершин на сообществ. Поставим в соответствие разбиению некоторое числовоезначение () – верхнюю границу длины кодового слова, описывающегокачество разбиения . Назовем () показателем качества разбиения .Для вычисления показателя () для заданного разбиения сначалаприменим теорему Шеннона [66] об источнике шифрования, которая гласит,что когда используется кодовых слов для описания состояний случайнойвеличины , которые встречаются с частотами , средняя длина кодовогослова не может быть меньше энтропии случайной переменной ,представимой в виде: () = − ∑=1 ∙ log( ) ,(3.1)Показатель качества разбиения () будем определять на основе (3.1)Для заданной сети зафиксируем разбиение на сообщества.
Введемслучайную величину , которая принимает значения от 1 до (количество92сообществ) с вероятностями () ,где = 1. . . Для каждого сообщества введем случайную величину , которая принимает значения от 1 до (количество вершин в сообществе ) c вероятностями , где = 1 … .Расчет показателя () основывается на вычислении энтропии введенныхслучайных величин и следующим образом:() = ( ) + ∑=1 ( ) ,(3.2)где = ∑=1 - вероятность перехода между сообществами на каждом шагеслучайного блуждания, - вероятность покинуть сообщество , вероятность посетить вершину , = ∑∈ + - вероятность остаться всообществе .
( ) = − ∑=1 ∑=1 log (∑ ) ,(3.3)=1 ( ) - энтропия переходов между сообществами, нижняя границасредней длины кодового слова для именования сообществ.Запишем энтропию ( ) перемещения внутри -того сообщества,определяющую нижнюю границу средней длины кодового слова дляименования вершин в -том сообществе:( ) =log()− + ∑∈ + ∑∈ ∑∈log() +∑∈ +∑∈ ,(3.4)Из заданных формул (3.3) и (3.4) можно получить более детальноеописание показателя () (формула (3.1)):() = (∑=1 ) log(∑=1 ) − 2 ∑=1 log( ) − ∑=1 log( ) +∑=1( + ∑∈ ) log( + ∑∈ ) ,(3.5)Стоит заметить, что ∑=1 log( ) - не зависит от разбиения сети насообщества. Поэтому, в процессе поиска лучшего разбиения сети, необходимобудет хранить все изменения: - вероятность, с которой случайное93блуждание входит и выходит из сообществ, и ∑∈ - доля времени, которуюслучайное блуждание проводит в каждом из сообществ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
