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

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

Поэтому происходит сравнение с «нулевойгипотезой», заключающейся в том, что дуги распределены случайно, т.е. нетзакономерностей в распределении плотности дуг внутри групп.Q = ∑i,j [Aij2m−ki kj4m2] σ(ci , cj ) ,(1.1)43где m-количество связей, A – матрица смежности графа, Aij – наличие ребра между1, ci = cjвершинами i и j, ki -степерь вершины i, σ(ci , cj ) = {, где ci -номер класса, к0, ci ≠ cjкоторому принадлежит вершина i.В алгоритме иерархического разбиения Гирвина и Ньюмана (Girvan andNewman) [33, 54] связи удаляются итеративно, основываясь на значении одной изчисленныххарактеристикдлясвязейиливершин[2,52].Всамыхраспространенных реализациях используется численная характеристика связи "центральность по посредничеству" (betweenness centrality) [2], определяемая какколичество кратчайших путей между всеми парами вершин, проходящих череззаданную связь (1.2): () = ∑≠,∈,∈ (),(1.2)где - связь, для которой считается численная характеристика связи, множество вершин графа, - количество кратчайших путей между вершинами и , () - количество кратчайших путей между вершинами и , проходящихчерез связь .В самой распространенной реализации процедуразавершается,когдамодулярностьрезультирующегоудаления связейразбиениядостигаетмаксимума.Также существует быстрый жадный алгоритм оптимизации модулярности(Clauset, Newman and Moore) [22].

Этот метод является ускоренной реализациейпредыдущей техники, предложенной Ньюманом [50]. Начиная с множестваизолированных вершин, связи оригинального графа итеративно добавляются так,чтобы максимально возможным образом увеличить численную характеристикумодулярности, описанную выше.44Наиболее эффективным из группы алгоритмов, основанных на активномиспользовании модулярности Ньюмана-Гирвана, является алгоритм Блонделя(Blondel) быстрой оптимизации модулярности [20].

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

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

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

Данный алгоритм по существу напоминает45внутреннюю природу сложных сетей и естественным образом включает в себяпонятие иерархии, так как в процессе работы алгоритма строятся сообществасообществ. Глубина полученной иерархии сообществ определяется числомитераций и обычно является небольшим числом, как было установлено изэкспериментов с графами социальных сетей различных размеров.Различные модификации алгоритмов Ньюмана [31, 33, 50-54] и алгоритмРадичи [58] основаны на похожих идеях.

Это методы иерархического разбиения,где связи итеративно удаляются на основе информации о дугах, которыеопределяются значениями некоторых коэффициентов, введенных для описаниячастоты встречаемости этих дуг. Рассматриваются обычно либо коэффициентпромежуточности, который является мерой того, насколько часто связь входит вкратчайшие пути между различными парами узлов, либо коэффициентгруппировки дуг, который определяет количество циклов, в которых состоитданная дуга. При этом вычисление коэффициента группировки дуг, как в алгоритмеРадичи[58],ненастолькотрудоемко,как,например,коэффициентапромежуточности. За счет использования данного показателя асимптотическаясложность алгоритма составляет (2 ) на разреженных графах, где - количествовершин в графе.Помимоуказанныхвышеалгоритмов,существуетещенесколькораспространенных подходов для выделения сообществ в сетевых структурах [35,47].

Однако, приведенные в [41] результаты тестирования показывают, чтобольшинство разработанных алгоритмов не применимы для реальных сетейбольших размеров либо по причине низких скоростных характеристик, либо из-занизкого качества выделения сообществ.1.3.3.Метод на основе спектральных свойств графаТопология сети взаимодействующих объектов может быть описана строгимиматематическими методами. Структура графа сети может быть представленасимметричной матрицей Лапласа, диагональные элементы которой определяются46степенью соответствующей вершины (количество связей, исходящих из данныхвершин), а недиагональные элементы определяются как −1, если существуют связьмежду парой вершин и 0 в противном случае. Заметим, что сумма элементов любойстроки или столбца такой матрицы равна нулю.

Собственные значения матрицыЛапласа являются неотрицательными вещественными числами, а кратностьнулевого собственного значения равна количеству компонент связности.Наименьшее положительное собственное значение определяет алгебраическуюсвязность рассматриваемого графа. Соответствующий этому собственномузначению собственный вектор содержит всю информацию об интересующей насструктуре графа. По значениям (величинам) компонент данного собственноговектора можно сгруппировать вершины графа по отдельным группам, которые мыназываем сообществами.На спектральных свойствах графа основан алгоритм Донетти-Муньоза(Donetti and Munoz) [27]. Метод предусматривает получение некоторыххарактеристик для каждой вершины графа из решения задачи на собственноезначение матрицы Лапласа.

Естественно, что получаются достаточно объемныеданные для графов. Затем вершины группируются классическими иерархическимиметодами кластерного анализа. Из результирующих разбиений выбирают то,которое максимизирует модулярность Ньюмана-Гирвана. Метод работает за(3 ), где - количество вершин в графе, за счет вычисления только несколькихсобственных векторов c помощью итеративного алгоритма Ланчоса (Lanczosalgorithm).1.3.4.Алгоритмы, основанные на оценке энтропии системыСтруктурный алгоритм Росваля-Бергстрома (Rosvall and Bergstrom) [61]сводит задачу нахождения наилучшего структурного разбиения графа насообщества к задаче оптимального сжатия информации о структуре графа, прикотором после декодирования результат будет максимально близок к исходнойструктуре графа.

Это достигается путем вычисления минимума функции, которая47выражает наилучший компромисс между минимумом разницы исходной и сжатойинформацией (максимальной точностью к исходной информации) и максимальнымсжатием.Динамический алгоритм Росваля-Бергстрома (Rosvall and Bergstrom) [62, 63]основан на тех же принципах, что и структурный алгоритм Росваля-Бергстрома.Разница заключается в том, что предыдущий алгоритм сжимал информацию оструктуре графа, в то время как данный метод сжимает информацию одинамическомпроцессе,проходящемвграфе(случайноеблуждание).Оптимальное сжатие снова достигается оптимизацией показателя качества,называемой минимальной длиной описания случайного блуждания.Для вычисления показателя качества заданного разбиения используетсяэнтропия, описывающая среднюю длину кодового слова, взятого для кодированиявершины.