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

Формула (3.5)подсчитывается быстро за счет хранения большей части результатовпромежуточных вычислений, входящих в нее слагаемых.Рассмотрим метод для неориентированных взвешенных сетей. Можнозадать вес вершины : = ∑∈ ,(3.6) -множество инцидентных связей вершины ; – вес связи .Тогда с учетом (3.6) можно задать относительный вес сообщества i: = ∑∈ ,(3.7)Пусть -вес выхода из сообщества i: = ∑∈ ,(3.8)где - множество связей, выходящих из сообщества iВведем общий вес связей, соединяющих сообщества:=∑=1 2,(3.9)При условии использования неориентированных взвешенных сетейформулы (3.6) - (3.8) преобразуют формулу (3.5) так, что показатель качестваразбиения () будет выглядеть следующим образом:() = log( ) − 2 ∑log( ) −=1 ∑=1 log( ) + ∑+ ) log( + ) ,=1((3.10)Теперь рассмотрим случай ориентированного взвешенного графа: дляначала необходимо ввести новый параметр: вероятность телепортации .Телепортация случайного блуждания - это равновероятный переход в94случайную вершину в каждый момент времени во время процесса случайногоблуждания.

=1,(3.11)где - вероятность начать случайное блуждание из вершины .Введем вероятность перехода из вершины в вершину :=∑∈,(3.12)где: – множество вершин, выходящих из вершины , – вес связимежду и . Если не существует выходящей связи из в , то = 0.В процессе случайного блуждания на каждом шаге осуществляетсяпереход в соседнюю вершину с вероятностью 1 − и с вероятностью вслучайную вершину сети. При условии, что сеть является ориентированной ивзвешенной, вероятность выхода из сообщества , используемая в формуле(3.5), будет выглядеть следующим образом: = −∑∈ + (1 − ) ∑∈ ∑∉ ,(3.13)где -количество вершин в сообществе i.В качестве обобщения процесса случайного блуждания можно ввестипараметр -вероятность телепортации [39] в вершину , где ∑=1 = 1.Тогда вероятность выхода из сообщества i (формула (3.13)) примет вид: = (1 − ∑∈ ) ∑∈ + (1 − ) ∑∈ ∑∉ ,(3.14)Любой жадный алгоритм (быстрый, но не точный) или метод МонтеКарло (точный, но медленный) могут быть использованы для минимизации().В [61-63] аналогичный метод использован лишь для структурногоразделения сети на сообщества.

Зачастую в социальных сетях содержится95множество дополнительной информации [2, 43, 48, 55], хранящейся вразличных типах данных. Поэтому, при выделении сообществ необходимоиспользовать информационное содержимое сети для улучшения качестваразбиения и его детальной настройки. Под информационным содержаниемпонимаются атрибуты, хранящиеся в вершинах и связях графа. Например,можноиспользоватьтакиеатрибуты,как:религиозныеубеждения,политические взгляды, место работы или учебы, количество общих друзеймежду парой вершин, количество оставленных постов в ленте новостей и такдалее.Пусть-{, , , }множествовсевозможныхстрок,=-- множество типов = (, ) -- типатрибута, где ∈ , ∈ .

= { } - множество (коллекция) типоватрибутов, . - множество всех допустимых значений типа атрибута ∈, = (, ) − атрибут, где ∈ , ∈ .. = (, )-мультиграф, где = { } - множество вершин, = { } - множество ребер,такое что ∈ ×.: → 2 - отображение, задающее множество вершин, обладающихзаданным атрибутом. : () → . , где ∈ - отображение, задающеезначения атрибута в вершинах, содержащих данный тип атрибута.

: → 2- отображение, задающее множество связей, обладающих заданныматрибутом. : () → . , где ∈ - отображение, задающее значенияатрибута в связях, содержащих данный тип атрибута.Пусть ST - множество типов атрибутов, которые должны приниматьсяво внимание при выделении сообществ. Пусть ( , ) ∈ [0; 1] - функцияблизости двух вершин по заданному набору типов атрибутов. Например, вкачестве близости двух вершин и может рассматриваться функция96считающая долю одинаковых атрибутов ( , ) = 1 −||||, где –множество атрибутов, присутствующих в обеих вершинах, ⊆ –множество атрибутов, которые присутствуют в обеих вершинах и их значениясовпадают.Тогда для случая неориентированного графа вес сообщества (формула(3.7)) примет следующий вид: = (∑,∈1− (,))||2∙ ∑∈ ,(3.15)Для случая ориентированного графа вероятность перехода из вершины в вершину (формула (3.12)) преобразуется к виду:=∑∈ ∙ (1 − (, )) ,(3.16)Методология работы алгоритма c учетом баланса между качествомразбиения сети и скоростью работы алгоритма будет выглядеть следующимобразом: соседние вершины соединяются в сообщества, которые, в своюочередь, соединяются в суперсообщества и так далее.

Затем в случайномпорядке каждая вершина перемещается в соседнее сообщество с цельюмаксимальнойминимизациипоказателякачестваразбиения.Еслиминимизировать показатель качества разбиения нельзя, то вершина остается впервоначальном сообществе. Данная процедура повторяется до тех пор, поканельзя будет переместить ни одну вершину и уменьшить показатель качестваразбиения. На каждом шаге генерируется случайная последовательностьвыбираемых вершин. Данным алгоритмом будет быстро найдено хорошееразбиение сети на сообщества.97Алгоритм 3.1. Общая схема алгоритма выделения сообществ.Вход: (, ) -граф, где -множество вершин, - множество ребер, =||, = ||.Последовательность шагов:1. Изначально каждая вершина считается отдельным сообществом.Считается и запоминается показатель качества разбиения () .Переход к шагу 2.2.

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

Иначе, еслизначение показателя качества разбиения () не уменьшилось,переход к шагу 5.5. Полученное разбиение считать результатом выделения сообществв сети. Переход к шагу 6.6. Конец алгоритма.Результат: множество вершин графа представляется в виде наборанепересекающихся множеств вершин (сообществ).Найденныесообществабудутобладатьследующимсвойством:плотность связей внутри сообществ намного больше плотности связей междусообществами.983.2.ТестированиеВычислительные экспериментыалгоритмавыделениясообществ(Алгоритм3.1)проведено в несколько этапов: тестирование на сгенерированных графах итестирование на подграфах реальных социальных сетей.Первый этап тестирования проводился на сгенерированных графах. Дляоценки и тестирования алгоритма выделения сообществ необходимы графы сзаданной структурой сообществ, которую алгоритм будет выделять.

В статьях[40, 42] предложена LFR-модель, при помощи которой можно протестироватьалгоритм на разных конфигурациях сетей и сообществ в них. Рассмотрим LFRмодель как специальный случай планарной модели разбиения на сообществ,при которой:• Размеры сообществ различны и распределены по степенному закону.Пусть – количество сообществ в сети, – максимальная степень(количество вершин, входящих в сообщество) сообщества, ∈{1,2,3, … , } – степень i-го сообщества.

Тогда ( = ) =1 1,где 1 = , 1 = .• степени вершин распределены по степенному закону. Пусть –количество вершин в сети, – максимальная степень вершины, ∈ {1, 2, 3, … , } – степень -ой вершины. Тогда ( = ) =2 2где 1 = , 2 = .Введем следующие обозначения: – количество соседей -ойвершины, лежащих в том же сообществе, – количество соседей -ойвершины, лежащих в других сообществах, – сообщество вершины , –количество вершин, лежащих в сообществе , ( ) – количестводоступных соединений снаружи (внутри) сообщества равная сумме степеней99вершин снаружи (внутри) данного сообщества, < > – средняя степеньвершины:< >=∑=1 (3.17),Тогда ∼ ( − ) ∙ < > ,(3.18) ∼ ∙ < > ,(3.19)Вероятность наличия связи вершины с вершинами из другихсообществ: =∼ (− )∙<>(3.20),Вероятность наличия связи вершины с вершинами своего сообщества:Тестирование=скорости∼ ∙<>(3.21),работыалгоритмапроводилосьнасгенерированных графах.

Приведем зависимость времени выполненияалгоритма от средней степени узла, которая равна количеству смежных с нейвершин, где количество вершин равно 10 000, максимальная степень узларавна 40, вероятность связи между вершинами из разных сообществ равна 0.1,минимальныйразмерсообществаравен100,максимальныйразмерсообщества равен 1000. У всех сетей из теста отличалась средняя степень узла,что в свою очередь отразилось на количестве связей: у графа со среднейстепенью узла «4» - 53152 связи, у графа со средней степенью узла «35» 350440 связей.100Время выполнения в зависимости от средней степенивершиныt, время (сек)1,210,80,60,40,200510152025303540< k >, средняя степень вершиныРис.