Главная » Просмотр файлов » Диссертация

Диссертация (1090614), страница 8

Файл №1090614 Диссертация (Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов) 8 страницаДиссертация (1090614) страница 82018-01-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.

Характеристики

Список файлов диссертации

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6489
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее