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

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

На первом шаге выполняется поиск непересекающихся сообществ спомощью динамического алгоритма Росваля-Бергстрома. Авторы переопределяютфункцию качества разбиения с учетом того, что вершина может входить сразу внесколько сообществ. На втором шаге формируется список всех граничных вершиндля всех найденных на первом шаге сообществ. Далее, каждая такая вершинапримыкает к новому сообществу, и выполняется пересчет нового показателякачества разбиения, в результате выбираются вершины с максимальным48уменьшением показателя качества. Процедура итеративно продолжается до техпор, пока выполняется оптимизация функции.В[64]описываетсяметодулучшенияалгоритманахожденияпересекающихся сообществ с помощью добавления «памяти» в моделированиепроцесса случайного блуждания по графу.

Если раньше при кодировании процессаучитывалось только предыдущее состояние, то теперь учитывается заданноеколичество последних переходов.Отметим, что предложенный в [26] метод,способен выделять пересекающиеся сообщества в многослойных сетях. В основеданного метода также лежит оценка энтропии системы. Многослойные сети можнопредставлять как одну сеть со связями разных типов. Данную методику можноприменять в анализе социальных сетей, так как им присуще наличие связей разныхтипов: отношение дружбы, публикация постов, проставление «лайков» и так далее.1.3.5.

ТестированиеСамый известный тест на выделение сообществ использует определенныйкласс графов, предложенный Гирваном и Ньюманом (тест GN) [53]. Каждый графимеет 128 вершин, которые разбиваются на 4 сообщества по 32 вершины вкаждом. Средняя степень вершины составляет 16 . Вершины имеют примерноодинаковую степень, как в случайном графе. Очевидны недостатки таких тестов:все вершины графа имеют примерно одинаковую степень; все сообществаодинаковые размеры; у тестовых графов очень небольшие размеры.Указанные недостатки частично исправляются при тестировании на частоприменяемых LFR-моделях [39, 44] генерации случайных графов, обладающихструктурой сообществ.

Данный подход является самым популярным длятестирования алгоритмов автоматического выделения сообществ, направленных наработу с большими графами. Для оценки и тестирования алгоритмов выделениясообществ необходимы графы с заданной структурой сообществ, которуюалгоритмы будут выделять. С помощью LFR модели можно протестировать49алгоритм как на разных конфигурациях сетей, так и на различных распределенияхколичества и размеров сообществ в них.В работе [41] приведены результаты для большинства представленных вышеалгоритмов на тестах Гирвана-Ньюмана, LFR, а также на случайных графах. Крометого, в проведенных тестах учитывались такие параметры, как направление связи,веса связей и возможность сообществ пересекаться.

Для остальных алгоритмовавторы в своих работах приводят результаты на нескольких графах и развернутыйанализ полученных результатов. С учетом всех имеющихся тестов средирассматриваемых алгоритмов наилучшим образом себя показали алгоритмыБлонделя [20] и динамический алгоритм Росваля-Бергстрома [61-63]. Этиалгоритмы удовлетворяют требованиям к скорости работы, требуемой памяти и ккачеству полученного разбиения, за счет этого их часто применяют при работе сбольшими графами реальных социальных сетей. У остальных алгоритмовнаблюдались различные недостатки, например, такие как неспособность быстройработы на больших объемах данных и нестабильность качества получаемыхразбиений при тестировании.В целом методы, основанные на оценке модулярности, имеют довольнонебольшую точность. Исключение составляет алгоритм Блонделя [20], чьирезультаты достаточно хорошие. Для большинства представленных алгоритмовточность выделения сообществ сильно подвержена негативному влиянию скорееразмеров сообществ (в случае с большими сообществами это видно хуже, тогда какдля небольших размеров сообществ это видно отчетливо), нежели размеров графа.Динамический алгоритм Росваля-Бергстрома показал наилучшую точность как поотношению к изменению размеров графа, так и по отношению к изменениюразмеров сообществ.Алгоритмы Блонделя [20] и Росваля-Бергстрома [61-63] показали наилучшиерезультаты на LFR тесте для неориентированных невзвешенных графов.

Несмотря50на высокую скорость работы (линейно относительно размеров сети), онипродемонстрировали лучшее качество выделения сообществ на больших графах.Упомянутоевышетестированиеалгоритмоввыделениясообществосуществляется на двух типах тестов: на тесте Гирвана-Ньюмана и на LFR тестах.Отметим, что все эти тесты искусственно генерируются и скорее всего немоделируют реальные социальные сети, для которых применение данныхалгоритмов наиболее интересно. Реальные графы характеризуются неравномернымраспределением степеней вершин и неравномерным распределением самихсообществ, причем законы таких распределений могут быть различны в разныхсетях. Поэтому остается актуальной задача сравнительного тестированияалгоритмов на графах реальных социальных сетей.Всуществующихпрограммныхпродуктахпоанализусетейвзаимодействующих объектов отсутствуют встроенные алгоритмы выделениясообществ, и, как следствие, отсутствуют геометрические модели визуализациисетей, основанные на выделении сообществ.Проведенные оценки позволяют сделать вывод о том, что наиболееэффективным и перспективным для реализации является динамический алгоритмРосваля-Бергстрома [61-63].

Развитие данного подхода [26, 30, 64] позволяетучитывать возможные значения атрибутов вершин и ребер графа, что даетвозможность выявить сообщества, основанные не только на формальномвзаимодействии объектов, но и на иных информационных характеристикахсоциальных сетей. Поэтому его целесообразно применять для решения задачвыделения сообществ в графах больших размеров, характерных для массовыхсоциальных сетей и сетей телекоммуникационного взаимодействия.

Данныеалгоритмы могут оказаться интересны и для задач, возникающих в биологии,экономике, социологии и маркетинге.511.4.Выводы по 1 главеУ большинства современных промышленных систем визуализации и анализаграфоввзаимодействующих объектов,ориентированных наисследованиесоциальных и аналогичных сетей, присутствует ряд недостатков: отсутствиеплатформенно-независимыхрешений,отсутствиесобственныхспециализированных хранилищ, системы не ориентированы на работу с графамибольших размеров. Поэтому стоит проблема разработки специализированныхсредств для аналитической работы с графами больших размеров. При этомотсутствуют отечественные программные продукты для работы с графамибольших размеров.В литературе отсутствуют эффективные алгоритмы многополосногоразмещения графов социальных сетей и их программная реализация в составепрограммных продуктов для анализа сетей больших размеров.Одной из самых актуальных является задача выделения сообществ,возникающая в задачах как криминального расследования, так и социологическогои маркетингового анализов.

В публикациях представление графа в виде сообществне рассматривается как геометрическая модель для визуального представленияструктуры графа. В основных коммерческих программных продуктах отсутствуетреализация геометрической модели визуального представления графа на основеприменения алгоритмов выделения сообществ.52ГЛАВА 2. Геометрические модели автоматических размещенийобъектов графа на плоскостиПри анализе графов различной природы возникает задача визуальногопредставления их структур в программном интерфейсе.

Размещение узлов и связейна сетевой схеме является нетривиальной задачей и в ручном режиме можеттребовать значительных временных затрат уже для схем с количеством узловпорядкадесяти.Вданнойглавеописываютсягеометрическиемодели,реализующие автоматическое размещение узлов, связей, и их атрибутов наплоскости для большого графа.2.1.Базовые геометрические модели автоматического размещений2.1.1.Случайное размещение объектовНа первом шаге для заданного графа подбирается прямоугольная областьнужного размера.

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

Распределение вершин в заданной области является равномерным.2.1.2.Геометрическая модель кругового размещения объектовУзлы равномерно располагаются по одной окружности. Распределение поокружности производится на основе структуры связей. Минимизация пересеченийв круговом размещении является NP-трудной задачей [19]. Используетсядвухфазный алгоритм минимизации пересечений [19].53Алгоритм 2.1. Круговое размещения объектов.Вход: (, )-граф, где - множество вершин, - множество ребер, = ||, =||.Последовательность шагов:1.