Диссертация (Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов), страница 11

В случаеодинаковых значений начала отрезков располагаются раньше концов отрезков.Зафиксируем множество = ∅ . Данное множество будет хранить в себеприписанные ребрам номера, соответствующие порядку добавления ребер врезультирующем размещении.Начнем последовательно обрабатывать значения . Если текущее значениесоответствует началу отрезка, то соответствующему ребру в качестве значенияфункции () ставим минимальный порядковый номер, который не присутствуетво множестве X и, затем, добавляем его в это множество. В случае, когда является концом отрезка, то значение () соответствующего ребра удаляется измножества X.В результате обработки отсортированной последовательности концовотрезков для каждого ребра будет подсчитано значение функции () и, всоответствии с ней, выполнена сортировка этих значений.

Следовательно,сформируется порядок оптимального (минимизирующего ширину размещения)добавления ребер в размещение. Аналогичным образом строится порядокдобавления вторичных вершин и их инцидентных связей (Алгоритм 2.10 шаг 3-4).Для каждой вторичной вершины строится множество пересекаемых ею полос (),78которое состоит из полосы, в которой располагается вершина, и из полос, которыепересекают все инцидентные ей ребра.Отдельного пояснения требует процедура оптимального определениярасположения подписей к связям. Для каждой горизонтальной полосы , ,описанной выше, стоится так называемый вертикальный профиль, которыйпредставляетсобойломануюлинию,состоящуюизвертикальныхигоризонтальных отрезков и задающую границу между занятым и свободнымпространством: слева от профиля занятое пространство, справа от профиля –свободное.

При добавлении вторичной вершины и ее инцидентных связейучитываются текущие профили полос размещения в соответствии со следующималгоритмом (Алгоритм 2.11).Алгоритм 2.11. Добавление вторичной вершины и ее инцидентных ребер с учетомпрофилей полос размещения.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||. ⊇ 0 - множество базовых вершин, – вершина для размещения.Последовательность шагов:1. Вычисляются ограничения на размещение вершины и ограничениякаждого из ее инцидентных ребер. Переход к шагу 2.2.

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

Финальное расположение вершины корректируется в соответствии сустановленным порядком добавления ее инцидентных ребер. Переход кшагу 5.5. Конец алгоритма.Результат: размещение вершины и ее инцидентных ребер.Данный алгоритм автоматического размещения реализован в рамкахразрабатываемой системы [75] по анализу и визуализации больших сетейвзаимосвязанных объектов. Реализованный алгоритм был протестирован наданных социальной сети ВКонтакте, полученных с помощью открытого API.

Вкачестве объекта размещения использовалась сеть, в которойвершиныопределялись профилями социальной сети, а связи – отношением дружбырассматриваемых профилей. Объем рассматриваемых сетей по количеству вершинварьировался в диапазоне от 300 до 150000, по количеству связей – от 1300 до500000. В качестве атрибутов вершин использовались открытые данные профиля(имя, фамилия, дата рождения, политические взгляды и т. д.), в роли атрибутовсвязей выступали веса, определяющие значимость связи между профилями,открытые публикации между парой пользователей (стена, новостная лента) и др.Анализ подобного рода сетей активно используется [11,], например, для выявленияпреступных групп лиц в ходе криминальных расследований [7, 13, 72].Помимо этого, данный алгоритм был протестирован на небольших графахсоциальных сетей (Рис. 2.11).80Рис. 2.11.

Пример многополосного размещения с двумя линиями тем.Скорость работы алгоритма может сильно варьироваться в зависимости отнеобходимых условий, накладываемых как на порядок добавления базовыхвершин, так и на последовательность размещения вторичных вершин иопределение их полосы расположения. В базовой реализации Алгоритм 2.10работает за ( ()), где – количество вершин исследуемой сети. Алгоритмреализован на языке C++.Далее на примере алгоритма одна и две линии темы (частный случаймногополосногоразмещения)опишемалгоритмпостроенияфинальногоразмещения объектов.2.3.3. Геометрическая модель автоматического размещения «одна линиятемы»Введем несколько вспомогательных классов, которые используются вреализацииалгоритма.СтруктураConnectionFigure:определяетспособвизуального отображения связей между парой вершин.

Если между парой вершиннесколько связей, то данный класс отвечает за способ размещения связейотносительно друг друга: отступ между параллельными связями, определениеположения точек изгиба связей. В случае, если обе вершины представлены в виде81линии тем, то поддерживается координата соединения связей с линиями тем погоризонтали.Структура Connection: представляет собой множество связей между паройвершин, множество изломов, ассоциированных с соответствующими связями, иобъект ConnectionFigure, определяющий результирующее отображение. В качествеструктуры данных для множества используется сбалансированное бинарное деревопоиска [10], в котором в качестве ключей используются указатели на объекты, чтопозволяет эффективно использовать оперативную память и быстро выполнятьбазовые операции (поиск, удаление, добавление).Алгоритм 2.12. Автоматического размещение «одна линия темы».Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.

B – множество изломов ребер.Последовательность шагов:1. Из структуры сети удаляются все существующие изломы ребер. Переходк шагу 2.2. Выделяется вершина, которая отображается как линия темы. Переход кшагу 3.3. Выделяются все вторичные объекты, связи между ними и линией темы,для всех пар вторичных объектов и линии темы формируются структурыConnection. Отдельно сохраняется параметры (координаты и размеры)обрамляющих прямоугольников подписей вторичных вершин и всехсвязей.

Переход к шагу 4.4. Отдельныммножествомсохраняютсявсегруппы связей междувторичными объектами и параметры обрамляющих прямоугольников ихатрибутов. Переход к шагу 5.5. Формируется список всех вторичных вершин. Переход к шагу 6.826. Определяется порядок отображения вторичных вершин. Переход к шагу7.7.

С помощью алгоритма поиска в ширину выполняется обход всехвторичных вершин с целью формирования компонент связностиисходного графа (Алгоритм 2.3). В результате обхода будет построенсписок множеств вершин, в котором каждое множество состоит из всехвершин, принадлежащих одной компоненте связности. Переход к шагу 8.8. Если вторичные объекты размещаются по разные стороны от линии темы,то формируется списки вершин, расположенных сверху и снизу.Найденные компоненты связности разбиваются на две группы: те, чтобудут расположены сверху и те, что будут расположены снизу. Если вграфе всего одна компонента связности, то вершины, сохраняя порядок,будут равномерно распределены по группам.

Переход к шагу 9.9. Выполняется размещение верхней группы вершин (Алгоритм 2.13).Переход к шагу 10.10. Аналогичным образом (п.8) расставляются вершины нижней группы.Переход к шагу 11.11. Конец алгоритма.Результат: размещение графа на плоскости при помощи геометрической модели«одна линия темы».Опишем более подробно некоторые шаги автоматического размещения«одна линия темы» (Алгоритм 2.12). Алгоритм размещения работает только с темиобъектами, которые напрямую связаны с линией темы (вторичные вершины).

Длятого, чтобы остальные объекты присутствовали, в сеть добавляются временныесвязи, соединяющие линию темы с несмежными с ней вершинами.Возможны разнообразные варианты сортировки вторичных вершин дляопределения порядка их отображения (Алгоритм 2.12 шаг 6): по количеству связей83с линией темы, по количеству атрибутов, по значениям одного из атрибутов, поразмеру обрамляющего прямоугольника.Алгоритм 2.13.

Размещение каждой вершины из верхней группы вершин.Вход: Вход: (, ) -граф, где -множество вершин, - множество ребер, =||, = ||. A – верхнее множество вершин, диапазон возможных Y координатгоризонтальной полосы.Последовательность шагов:1. Текущая координата Y устанавливается минимальным значениемзаданного диапазона координаты Y при размещении вторичных объектовв горизонтальную полосу. Текущая координата X (точка соединениясвязейслиниейтемыих-координатавторичнойвершины)устанавливается значением X координаты левого конца линии темы,увеличенного на ширину иконки линии темы и небольшого заранеезаданного отступа.