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

2.7 приведен пример небольшого графа, размещенного с помощьюалгоритма «быстрый павлиний хвост». Из данного примера видно, что послеразмещения значительно уменьшилось количество пересекающихся связей,вершины расположились на плоскости таким образом, что общая структура графапредставлена более четко и наглядно.При тестировании алгоритма на графах реальных социальных сетей былидостигнуты следующие скоростные характеристики: граф с 700 000 вершин и 2.5млн. связей обрабатывался за 1.6 секунды.69Рис.

2.7. Пример автоматического размещения «быстрый павлиний хвост»: а)схема до автоматического размещения, б) схема после применения алгоритма.2.3.Многополосное размещениеМногополосное размещение - отдельный класс алгоритмов автоматическогоразмещения, разработанный в [11, 75, 80]. В стандартных поставках многихрассмотренных систем визуализации и анализа графов [9, 25, 32, 68] отсутствуютавтоматические многополосные размещения, особенно, если речь идет обавторазмещении графов социальных сетей, состоящих из миллионов вершин.2.3.1. Постановка задачиВведем следующие обозначения: пусть – множество всевозможных строк, = {, , , } – множество типов, = (, ) – тип70атрибута, где ∈ , ∈ .

= { } - множество (коллекция) типоватрибутов, . - множество всех значений типа атрибута ∈ . =(, ) - атрибут, где ∈ , ∈ . . = (, ) – мультиграф безпетель, где = { } – множество вершин, = { } – множество ребер, такое что ∈ ∗ .: → 2 - отображение, задающее множество вершин, обладающихзаданным атрибутом. : () → . , где ∈ - отображение, задающеезначения атрибута в вершинах, содержащих данный тип атрибута. : → 2отображение, задающее множество связей, обладающих заданным атрибутом. : () → . , где ∈ отображение, задающее значения атрибута в связях,содержащих данный тип атрибута.

Тогда сетью назовем = (, , ).Тогда задача будет формулироваться следующим образом. Необходимопостроить такое размещение элементов на плоскости [11, 38, 79], при котором длянекоторого заранее заданного множества будет гарантироваться отсутствиепересечения связей и атрибутов.2.3.2. Описание алгоритмаНа практике часто используют несколько изобразительных соглашений длявершин: иконки и таблицы. Введем новый способ представления вершин в виделинии темы. Линия темы – это вершина, которая представляется в видегоризонтального отрезка с перемещающейся по всей длине отрезка иконкой (Рис.2.8).71Рис.

2.8.Представление вершины в виде линии темы.Если инцидентные вершины находятся в вертикальной полосе, ограниченнойконцами линии темы, то все связи между такими вершинами и линией темы будутвертикальными и перпендикулярно соединяться с линией темы. Остальныеинцидентные вершины будут соединяться с ближайшими концами линии темы ине будут вертикальными. Положение концов линии темы и их длина можетменяться. Использование данного способа представления позволяет эффективнорешать задачу автоматического размещения графа.Исходными данными алгоритма многополосного размещения [3, 11] будетсеть = (, , ) и множество базовых вершин 0 ⊆ .

Введем функции() и ℎ() для v ∈ V, и () и ℎ() для e ∈ E, где w – ширина минимальногопрямоугольника, который ограничивает визуальное представление атрибутоввершины или связи, и, соответственно, h – высота минимального ограничивающегопрямоугольника.В качестве объекта визуализации будет выступать сеть ′ = ( ′ , , ),где ′ = ( ′ , ′ ) ,вторичных 1 = {| ∈ , ∉ 0 , ∃ ∈ 0 : (, ) ∈ }вершин, ′ = 0 ∪ 1–,множество′ ={| = (1, 2), ∈ , 1 ∈ 0 или 2 ∈ 0 } .

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

Тогда,алгоритм многополосного размещения представит базовую вершину в виде линиитемы, все остальные смежные с ней вершины будут разбиты на дванепересекающихся множества, при этом все вершины одного из них будутрасположены над линией темы, вершины другого - под линией темы (Рис. 2.9). НаРис. 2.9 заштрихованными прямоугольными областями являются информационные72характеристики объектов (атрибуты и их значения). Здесь и далее они будутнедоступны для просмотра.Рис.

2.9. Многополосное размещение с одной линией темы.Принципы разбиения множества смежных вершин могут быть довольноразнообразны и часто зависят напрямую от специфики решаемой задачи: например,для задачи анализа связей участника социальной сети в качестве базовой вершиныможет быть выбран профиль человека, а множество связанных с ним вершин поотношению дружбы может быть разбито по следующему принципу: в первоемножество попадут все вершины, у которых значение атрибута «место работы»будет совпадать со значение этого же атрибута базовой вершины, во второемножество – остальные.73Рассмотрим принцип расположения первого множества смежных вершин надлинией темы.

Сначала вершины упорядочиваются по одному из выбранныхкритериев. В качестве критерия выступают: случайное расположение вершин,сортировка вершин по значению одного из атрибутов вершин, сортировка вершинпо значению одного из атрибутов связей между этими вершинами и линией темы.Затем область над линией темы делится на две горизонтальные полосы. Дальняя отлинии темы полоса необходима для размещения внутри нее вершин с визуальнымпредставлением их атрибутов, другая полоса – для размещения в ней визуальногопредставления атрибутов связей. Оставшееся множество вершин размещается подлинией темы аналогичным образом.Рассмотрим другой пример многополосного размещения, в которомиспользуется две базовые вершины. Представим базовые вершины в виде линийтемы. Разделим множество смежных с ними вершин на три непересекающихся:первое множество – вершины, которые связаны только с первой линией темы,второе – вершины, которые связаны с обеими линиями темы, третье – вершины,связанные только со второй линией темы.

Разместим их следующим образом:первое множество над первой линией темы, второе множество между линиямитемы, третье множество под второй линией темы. Принцип размещения элементованалогиченпервомупримеру,приведенномувыше.Сначалабудутпоследовательно добавлен все связи между линиями темы. Затем стоить отметить,что горизонтальная полоса, образующаяся между линиями темы будет разделенана три: в среднюю полосу будут размещаться вершины со своим полнымвизуальным представлением (отображение самой вершины и ее атрибутов), вбоковых полосах будут размещаться визуальные представления атрибутов связей,причем выбор полосы будет определен именно тем, к какой линии темы относитсярассматриваемая связь.Тем самым, благодаря такому способу размещения подсети на плоскостиможно исключить всяческое пересечение связей, вершин и атрибутов.74Алгоритм 2.10. Многополосное размещение графа в случае, когда размермножества базовых вершин не ограничен.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.

⊇ 0 - множество базовых вершин.Последовательность шагов:1. На заданном множестве базовых вершин фиксируется порядок, всоответствии с которым сверху вниз будут отображаться базовыевершины в виде линий темы. Переход к шагу 2.2. Определяется порядок и добавляются связи между заданными линиямитемы, с отсутствием пересечений между отображением атрибутов.Переход к шагу 3.3.

Определяется порядок добавления вторичных вершин, и затем для каждойвторичной вершины определяется полоса между линиями темы, вкоторую она должна быть добавлена. Переход к шагу 4.4. Добавляются вторичные вершины. При последовательном добавлениивторичных вершин связи добавляются последовательно таким образом,чтобы отсутствовало пересечение отображения атрибутов. Переход кшагу 5.5. Конец алгоритма.Результат: выполнено многополосное размещение графа на плоскости.Рассмотрим некоторые этапы работы алгоритма.

Важным параметромпостроенного таким образом автоматического размещения является его ширина.Ширина размещения сети будет в значительной степени зависеть от шагов 2 и 4(Алгоритм 2.10) при добавлении связей. Для того, чтобы оптимизировать ширинуполученного размещения можно применять следующую процедуру.Если | 0 | = (то есть количество линий темы равно n), то количествогоризонтальных полос между линиями темы будет равно 3 + 1. Пронумеруем всегоризонтальные полосы размещения от 1 до 3 + 1следующим образом:751, 1 , 2 , 2 , 3 , 4 , 3 , 5 , … . Полосы 1 , 1 находятся над первой линией темы,полосы 2 , 2 , 3 расположены между первой и второй линией темы, полосы4 , 3 , 5 - между второй и третьей, и так далее.

Полосы будут использоватьсядля помещения в них визуального представления вершин, полосы - длявизуального представления атрибутов связей (Рис. 2.10).Рассмотрим процедуру оптимального добавления ребер на примере связей10 , … , 0 между вершинами из множества базовых 0 – линий тем (Алгоритм 2.10шаг 2).

Для каждого ребра = ( , ), где , ∈ 0 , построим множество полосразмещения,которыеданноеребробудет пересекать(2.6) (количествопересекаемых полос будет зависеть от порядка расположения базовых вершин вкачестве линий темы): () = { | ∈ [min(, ) + 1, max(, )]} ∪ { | ∈[2 min(, ) , 2 max(, ) − 1]} ,(2.6)76Рис. 2.10. Многополосное размещение с двумя линиями тем, пунктирнымилиниями отображаются границы полос размещения.Последовательно пронумеруем сверху вниз каждую построенную полосуиндексами от 1 до 3 + 1.

Тогда множество () пересекаемых ребром полосможно обозначить некоторым отрезком индексов () = [, ], 1 ≤ ≤ ≤ 3 + 1.Для каждого добавляемого ребра построим функцию (), которая будетзадавать порядковый номер ребра при оптимальном добавлении ребер (т.е. приминимизации ширины получаемого размещения). При найденном порядке77добавления ребер 10 , … , 0 между вершинами из множества базовых 0 ширинаразмещения будет равна: = max((0 )| = 1. . ),где(0 )={(2.7)1, если (0) ∩ С(0 ) = ∅.=1..−1(|С(0 )|) + 1, если (0 ) ∩ С(0) ≠ ∅Итоговый оптимальный порядок добавления ребер восстанавливается путемсортировки значений функции () для каждого ребра в порядке возрастания.Общее количество начал и концов отрезков (), где ∈ {10 , … , 0 }, равно 2.Отсортируем все концы в порядке возрастания значений: {1 , … , 2 }.