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

3.1. Время выполнения в зависимости от средней степени вершины.Синяя кривая отражает выполненные замеры, красная кривая –аппроксимация замеров линейной функцией (линейная регрессия)Из рисунка 3.1 видно, что представленную зависимость можноаппроксимировать линейной функцией (построена линейная регрессия,отображена на рисунке штриховой линией), но при анализе асимптотикиалгоритма необходимо учитывать структурные особенности конкретной сети.1013.3.Построение геометрической модели автоматическогоразмещения объектов графа с выделенными сообществамиРеализованы два алгоритма построения геометрической модели на основеграфа с выделенными сообществами. Первый алгоритм (Алгоритм 3.3)основан на круговом покомпонентном размещении, второй алгоритм(Алгоритм 3.4) – на методе физических аналогий.Ниже представлен базовый алгоритм автоматического размещения сиспользованием выделенных сообществ (Алгоритм 3.2).Алгоритм 3.2.

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

Далее алгоритм (Алгоритм 3.3 или Алгоритм 3.4) будет применятьсяк каждой сгруппированной группе сообществ (соответствующейодной компоненте связности). После применения одного изалгоритмов все полученные размещения вершин для каждойкомпоненты связности выстраиваются вдоль горизонтальной прямой102другзадругом,гарантируяотсутствиепересечениймеждуобрамляющими прямоугольниками различных сообществ. Переход кпункту 4.4. Конец алгоритма.Результат: размещение графа на основе алгоритма выделения сообществ.Алгоритм 3.3. Размещение сообществ одной компоненты связности на основегеометрической модели кругового покомпонентного размещения.Вход: (, ) - граф, где - множество вершин, - множество ребер, = ||, = || .

– сгруппированное множество сообществ одной компонентысвязности.Последовательность шагов:1. Каждое выделенное сообщество размещается с помощью алгоритмакругового автоматического размещения (Алгоритм 2.1). Переход кшагу 2.2. После размещения сообществ в отдельности для каждого сообществаподсчитываютсяразмеры(ширинаивысота)обрамляющихпрямоугольников. Переход к шагу 3.3. Выбирается максимальный размер обрамляющего прямоугольника,назовем его параметром . Переход к шагу 4.4.

Пусть в компоненте связности найдено = || сообществ. Тогдаможно найти окружность, которая может описать правильныймногоугольник, состоящий из вершин и c длиной одной стороны,равной параметру . Радиус такой окружности будет вычисляться поформуле=Переход к шагу 5.180)2sin(,(3.22)1035. На найденную окружность (шаг 4) выполняется размещение всехсообществ, при этом взаимное расположение элементов внутриодного сообщества, выполненное на шаге 1, сохраняется. Переход кшагу 6.6.

Конец алгоритма.Результат: размещение группы сообществ одной компоненты связности.Алгоритм 3.4. Размещение сообществ одной компоненты связности на основегеометрической модели метода физических аналогий.Вход: (, ) -граф, где - множество вершин, - множество ребер, =||, = ||. G – сгруппированное множество сообществ одной компонентысвязности.Последовательность шагов:1. Каждое выделенное сообщество размещается с помощью алгоритма«быстрый павлиний хвост» (Алгоритм 2.7).

Переход к шагу 2.2. После размещения сообществ в отдельности для каждого сообществаподсчитываютсяразмеры(ширинаивысота)обрамляющихпрямоугольников. Переход к шагу 3.3. Далее строится новый граф, в котором вершины являютсясгруппированными сообществами (Алгоритм 3.5).

Переход к шагу 4.4. К новому графу применяется автоматическое размещение «быстрыйпавлиний хвост» (Алгоритм 2.7), в результате которого получаетсянаглядное размещение сгруппированных сообществ, центрированноеотносительно начала координат. Переход к шагу 5.5. С помощью бинарного поиска [10] определяется коэффициент, накоторый будут умножены координаты вершин графа сообществ, таккак при размещении графа сообществ никак не учитывались размерывершин сгруппированных сообществ. Коэффициент будет равен104такому минимальному масштабу размещения вершин, при которомпосле разгруппировки обрамляющие прямоугольники каждогосообщества не будут пересекаться между собой. Переход к шагу 6.6.

Сжатие размещения, полученного на шаге 5. Переход к шагу 7.7. Конец алгоритма.Результат: размещение группы сообществ одной компоненты связности.Размещения, полученного на шаге 5 (Алгоритм 3.4), не достаточно длятого, чтобы получить финальное представление. Минус этого размещениязаключается в том, что некоторые сообщества сильно отдалены от центра, в товремя как они не пересекались с остальными сообществами.

Это происходитза счет того, что масштаб на шаге 5 применяется ко всем вершинам.Поэтому шаг 6 производит сжатие размещения. Оно происходитследующим образом. Все вершины графа сообществ сортируются в порядкевозрастания расстояния до центра координат. Затем последовательно длякаждой такой вершины с помощью бинарного поиска [10] выполняется поисккоэффициента, который показывает, во сколько раз можно максимальноуменьшить расстояние до центра, при этом гарантируя отсутствиепересечений между сообществами.

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

Построениеновогографаосуществляетсяспомощьюсбалансированного бинарного дерева поиска [10], у которогоключами будут указатели на вершины, а значениями – индексысообществ, к которым они принадлежат. Переход к шагу 2.2. Проход по всем связям исходного графа, с помощью построенного нашаге 1 дерева определяются индексы сообществ обоих вершинконцов связей. Переход к шагу 3.3. Если индексы не совпадают, то значит, что данная связь соединяетвершины из разных сообществ, таким образом, в новый графдобавляется новая связь между вершинами, соответствующиминайденным индексам сообществ.

По сути, порядковые номерасообщества определяет номер вершины в новом графе. Переход кшагу 4.4. Конец алгоритма.Результат: новый граф вершины которого соответствуют сгруппированнымсообществам.Описание процедуры Алгоритм 3.5. Пусть = (, ) – исходный граф, = { | ⋃ = , ∀ ≠ ∩ = ∅}–разбиениевершинграфанасообщества. Тогда новый граф сгруппированных вершин будет ′ = ( ′ , ′ ) граф сообществ, где ′ = {′ }, где | ′ | = ||, ′ -вершина, соответствующаясообществу . Тогда ′ = {′ | ′ = (′ , ′ ) }, где ′ , ′ ∈ ′ , ∀ ∃ ∈ ,∃ ∈ , ≠ , такие что ( , ) ∈ .

То есть в новом графе все связи междувершинами соответствуют связям между вершинами из разных сообществисходного графа.Описанные алгоритмы (Алгоритм 3.2-Алгоритм 3.4) формируютгеометрическуюмодель,позволяющуюреализоватьавтоматическое106размещение вершин с учетом выделенных сообществ в виде компактногорасположения и наглядного представления исходного графа на плоскости. Подкомпактным расположением графа на плоскости понимается площадьзанимаемой поверхности.Далее приведены различные примеры анализа реальных подграфовсоциальных сетей, где вершины – это профили социальной сети, а связи –отношения дружбы между ними. Данные взяты из социальной сети"ВКонтакте" (vk.com) с использованием реализованного модуля выгрузкисоциальной сети [81].Кроме того, для наглядности, при автоматическом размещении вершинна плоскости с учетом выделенных сообществ иконки вершин окрашивалисьразличными цветами, обозначающими принадлежность вершин к одному изсообществ.Далее будут рассмотрены примеры графов G1-G6, для каждого изкоторых представлены три варианта автоматического размещения: случайное,с использованием выделенных сообществ на базе кругового покомпонентногоразмещения, с использованием выделенных сообществ на базе методафизических аналогий.Рассмотрим граф G1, состоящий из 172 вершин и 3026 связей (Рис.

3.2Рис. 3.4). На данном примере графа видно, что для анализа использованиеслучайного размещения не подходит, так как из Рис. 3.2 структура связейграфа не видна. Это применимо ко всем остальным рассматриваемым далееграфам G2-G6. Для данного графа G1 применение двух алгоритмов (Рис. 3.3,Рис. 3.4) позволяет выявить несколько характерных вершин, отличающихсябольшим количеством инцидентных связей. Однако, для большинствасообществ связи внутри сообщества видны лучше при применении метода наоснове физических аналогий.107Рис.

3.2. Граф G1, случайное автоматическое размещение вершин.Рис. 3.3. Граф G1, применение алгоритма на основе кругового размещения.108Рис. 3.4. Граф G1, применение алгоритма на основе метода физическиханалогийРассмотрим граф G2, состоящий из 500 вершин и 7596 связей (Рис. 3.5 Рис. 3.7). Для данного графа видно, что при применении метода физическиханалогий вершины с большим количеством связей видны гораздо отчетливей,однако связи между вершинами из разных сообществ выглядят болеезапутанно, особенно когда вершины какого-то сообщества располагаются насвязях между другими сообществами.109Рис.