Диссертация (1090614), страница 8
Текст из файла (страница 8)
Формирование линейного размещения вершин. Пусть () = { ∈ ∶{, } ∈ } – множество смежных вершин для вершины . Выбор первойдобавляемойвершиныопределяетсяследующимобразом:0 =∈ (| ( )|) – вершина с максимальной степенью. Переход к шагу2.Последовательное добавление остальных вершин в конец линейного размещения.Порядок добавления определяется последовательностью обхода всех вершинначиная с вершины 0 алгоритмом обхода в ширину (2. ). Переход к шагу 3.3. Трансформируем линейное размещение в круговое путем соединенияконцов после добавления всех вершин в линейное размещение.
Переход кшагу 4.4. Выполняется минимизация пересечения связей. Для каждой вершины ∈ просматриваются все смежные с ней вершины ∈ ()- множествосмежных вершин с вершиной , и выбирается та, при перестановке скоторой количество пересечений максимально уменьшится. Переход кшагу 55.
Выполняется перестановка пары вершин, выбранной на 4 шаге. Еслинельзя найти соседнюю вершину, перестановка с которой минимизируетколичество пересечений, то переход к шагу 6, иначе переход к шагу 4.6. Конец алгоритма.54Результат:Всевершинырасположеныпокругу,полученныйпорядокрасположения вершин определяет локальный минимум количества пересеченийсвязей.Алгоритм 2.2. Обход графа в ширину.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1.
Выбирается вершина, с которой начинается обход, и добавляется визначально пустую очередь. Переход к шагу 2.2. Изначалаочередиизвлекаетсявершина ипомечаетсякакпросмотренная. Переход к шагу 3.3. Формируется набор смежных с вершин, которые еще не были помечены(может быть пустым множеством). Переход к шагу 4.4. Все вершины из сформированного набора на шаге 4 добавляются вочередь. Переход к шагу 5.5. Если очередь пуста, то переход к шагу 6, иначе переход к шагу 2.6.
Конец алгоритма.Результат: Сформирована последовательность обхода всех вершин графа.имеет асимптотическую сложность ( + ).На Рис. 2.1 представлен пример графа до и после автоматическогоразмещения.Асимптотическаясложностьшагов1-3равна( + ) .Асимптотическая сложность шагов 4-6 равна () . Экспериментальныерезультаты [19] показывают, что данную операцию достаточно сделать несколькораз для случайного набора вершин для достижения локального минимума функцииколичества пересечений (Рис. 2.1).55Рис.
2.1. а) Объекты сети до автоматического размещения, б) объекты сетипосле применения кругового автоматического размещения.2.1.3.Геометрическая модель кругового покомпонентногоразмещения объектовАлгоритм 2.3. Поиск компонент связности в графе на основе поиска в ширину.Вход: (, )-граф, где - множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1. Формируются 2 множества вершин – множество посещенных и непосещенных вершин. Множество посещенных вершин инициализируетсякак пустое, множество не посещенных вершин изначально состоит из всехвершин графа. Переход к шагу 2.2. Случайным образом выбирается вершина из множества не посещенныхвершин. Переход к шагу 3.56От нее запускается алгоритм обхода графа поиском в ширину (3.
). Таким образом полностью выделяется компонента связности. Вершиныэтой компоненты связности сохраняются и переходят из множества непосещенных вершин во множество посещенных. Переход к шагу 4.4. Если множество не посещенных вершин пусто, то значит все вершиныграфа разбиты по компонентам связности, переход к шагу 5. Иначе,переход к шагу 2.5. Конец алгоритма.Результат: получено разбиение множества вершин графа на непересекающиесямножества.Алгоритм 2.3 имеет асимптотическую сложность ( + ).В результате применения этого алгоритма множество вершин графа будетразбито на множество С непересекающихся подмножеств вершин (2.1), каждое изкоторых будет являться компонентой связности, при этом будет гарантироваться,что не существует никакой связанной пары вершин из разных компонент.
= {1, … , | ⋃=1 = , ∄, : 1 ≤ , ≤ , ≠ , ∩ ≠ ∅} ,(2.1)где С – множество непересекающихся подмножеств вершин, – количествокомпонент связности, – множество вершин (-ая компонента связности).Алгоритм 2.4. Круговое покомпонентное размещение объектов.Вход: (, )-граф, где -множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1. Выполняется поиск всех компонент связности в графе (Алгоритм 2.3). Врезультате получено разбиение С графа на непересекающиесямножества (2.1). Переход к шагу 2.2.
Для каждого множества вершин из выполняется построение круговогоразмещения (Алгоритм 2.1). Переход к шагу 3.573. Центры полученных окружностей размещаются на одной горизонтальнойпрямой. Переход к шагу 4.4. Конец алгоритма.Результат: построено размещение вершин графа на плоскости.На Рис. 2.2 и Рис. 2.3 представлены результаты работы круговогопокомпонентного размещения (Алгоритм 2.4. ). Центры окружностей каждойкомпоненты связности размещаются на одной горизонтальной прямой. Из данныхпримеров видно, что при небольшом количестве связей между вершинами однойкомпоненты связности, структура связей видна отчетливо, и отсутствуютпересечения выбранных изобразительных соглашений вершин (иконки) и ихатрибутов.Рис.
2.2. Результат применения кругового покомпонентного автоматическогоразмещения.Рис. 2.3. Круговое покомпонентное размещение объектов.582.1.4.Геометрическая модель размещения, основанного на оценкесвязностиДанное размещение отличается от кругового покомпонентного размещенияобъектов тем, что между выделенными компонентами могут быть связи.Размещение, основывающееся на оценке связности, использует информацию околичестве связей между парами вершин. Условно, перед размещением строитсяновый граф с тем же количеством вершин и с меньшим количеством связей.Алгоритм 2.5. Размещение, основанное на оценке связности.Вход: (, )-граф, где - множество вершин, - множество ребер, = ||, =||, параметр - порог на количество связей между парой вершинам.Последовательность шагов:1.
Для каждой связанной пары вершин исходного графа выполняетсяфильтрация связей: если количество связей между парой вершин меньшепорога , то все связи между этой парой удаляются. Таким образом будетсформирован новый граф ′ = (, ′ ) , у которого множество вершиносталось таким же, как и в исходном графе, множество ребер ′ ⊆ .Переход к шагу 2.2.
Далее применяется алгоритм выделения компонент связности (Алгоритм2.3) на графе ′ . В результате будет получено разбиение С (2.1) вершин графа ′ на непересекающиеся множества. Переход к шагу 3.3. Далее выполняются шаги 2-3 кругового покомпонентного размещения(Алгоритм 2.4) исходного графа на основе найденного разбиения С длявершин. Переход к шагу 4.4. Конец алгоритма.Результат: построено размещение вершин графа на плоскости.591.1.5. Размещение «вершина в центре»Данное размещение предназначено для анализа локального окружениязаданной вершины. Вокруг выбранной вершины будут расположены все смежныеей вершины с помощью кругового размещения.
Все остальные вершины сети,попадающие в заданную область будут смещены таким образом, чтобы непересекаться с выбранной вершиной и смежными с ней.На Рис. 2.4 представлен пример работы алгоритма. Для заданной вершинывсесмежныесней расположилисьотносительнонеепоГарантируется, что внутри этой окружности не будет других вершин.Рис. 2.4. Размещение вершина в центре.окружности.602.2.Геометрическая модель автоматического размещений на основеметода физических аналогийВ данном разделе описан алгоритм автоматического размещения «павлинийхвост», базирующийся на методе физических аналогий. Данный подход являетсяэффективным при размещении графов социальных сетей.2.2.1.Геометрическая модель автоматического размещения на основебазового метода физических аналогийАлгоритм вычисляет размещение вершин и связей графа, основываясь лишьна информации, хранящейся в структуре, при этом не принимая во вниманиезнания предметной области, содержащиеся в вершинах и связях графа.В качестве вершин рассматриваются одноименно заряженные частицы,взаимодействующие между собой на основе отталкивающей силы взаимодействиямежду точечными электрическими зарядами по закону Кулона.В качестве связей рассматриваются пружины, таким образом силапритяжения между связанными вершинами описывается законом Гука.Физическая модель строится следующим образом: в качестве вершинвыступают одноименно заряженные частицы, а в качестве связей – пружины.Отталкивающая сила вершин основывается на законе Кулона (2.2), описывающимсилы взаимодействия между точечными электрическими зарядами:12 = 1̅̅̅̅1 2 122 1212,(2.2)где 12 - сила, с которой заряд 1 действует на заряд 2, 1, 2 - величины зарядов, ̅̅̅̅12- радиус-вектор (вектор, направленный от заряда 1 к заряду 2, и равный, по модулю,расстоянию между зарядами - 12 ), 1 - коэффициент пропорциональности.Сила притяжения между связанными вершинами описывается законом Гука: = 2 ∆ ,(2.3)61где - сила, которой растягивают (сжимаеют) пружину, ∆ - абсолютноеудлинение (сжатие) пружины, 2 - коэффициент упругости.Алгоритм автоматического размещения (Алгоритм 2.6) является итерационным.Алгоритм 2.6.
Размещение, основанное на базовом методе физических аналогий.Вход: (, )-граф, где V -множество вершин, - множество ребер, = ||, =||, параметр – ограничение на максимальное количество итераций алгоритма,порог – минимально допустимая длина вектора смещения вершины.Последовательность шагов:1. Все вершины графа располагаются случайным образом на плоскости.Переход к шагу 2.2. Для каждой вершины определяется вектор смещения на основе заданнойфизической модели. Переход к шагу 3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
