Кластеризация на графах с качественной информацией на примере социальной сети

Белейченко Татьяна Александровна

Кластеризация на графах с качественной информацией на примере социальной сети

В дипломной работе рассмотрены два алгоритма кластеризации графов с качественной информацией: «осторожный» алгоритм и алгоритм жадной оптимизации. Представленные алгоритмы реализованы в программной среде и применены к кластеризации реальных данных из социальной сети «Вконтакте». На основе результатов программной реализации сделаны выводы об эффективности работы рассмотренных алгоритмов.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36405f1be77c40d58a9b

UUID: b64e6599-8c19-4564-a222-f2b0b82963fc

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 100

Белейченко Татьяна Александровна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 963264 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА МАТЕМАТИЧЕСКОЙ ТЕОРИИ ИГР И СТАТИСТИЧЕСКИХ РЕШЕНИЙ Белейченко Татьяна Александровна Выпускная квалификационная работа бакалавра Кластеризация на графах с качественной информацией на примере социальной сети Направление 01014 Прикладная математика и информатика Научный руководитель, кандидат физ.-мат. наук, старший преподаватель Тур Анна Викторовна Санкт-Петербург 2016

Содержание Введение ........................................................................................................ 3 Обзор литературы ........................................................................................ 6 Постановка задачи ........................................................................................ 8 Глава 1. Алгоритм жадной оптимизации ................................................ 10 1.1. Описание алгоритма ...................................................................... 10 1.2. Реализация алгоритма.................................................................... 13 Глава 2. «Осторожный» алгоритм ............................................................ 17 2.1. Описание алгоритма ...................................................................... 17 2.2. Реализация алгоритма ................................................................... 18 Заключение ................................................................................................. 21 Список литературы .................................................................................... 22 Приложение 1 ............................................................................................. 24 Приложение 2 ............................................................................................. 30 2

Введение В современном, стремительно развивающемся мире во многих производственных, научно-естественных, технических, экономических и др. областях стремительно растет объем данных. Вместе с тем возрастает потребность в упорядочении, выделении связанных групп по принципу схожести из огромного количества объектов. Именно такого рода проблему и помогает решить кластеризация. Информация, полученная вследствие кластеризации данных полезна и многогранна-вот лишь некоторые области практического применения качественных кластеров: 1. В области медицины используется кластеризация заболеваний, их симптомов, лечения. 2. В археологии устанавливаются таксономии каменных сооружений и древних объектов и т.д. 3. В маркетинге задачей кластеризации может являться выделение групп потребителей и конкурентов. 4. В социологии задача кластеризации - разбиение респондентов на однородные группы. Ещё одной областью применения методов кластеризации данных является интернет-пространство. С его развитием продолжают активно набирать популярность «Одноклассники», такие «Facebook», социальные и др. сети как Количество «Вконтакте», пользователей, зарегистрированных в этих сетях, огромно и с каждым днем оно только увеличивается. Эти сети представляют собой богатый источник данных. Особый интерес вызывает структура графа, индуцированного по ссылкам дружбы. В представленной работе будут проанализированы некоторые методы кластеризации и применены к данным социальной сети «Вконтакте» с целью определения неявных сообществ среди друзей. 3

Социальная сеть представима в виде графа, в котором узлами являются пользователи, а наличие связи между узлами означает то, что пользователи находятся в «друзьях» друг у друга. При этом отсутствует какая-либо количественная мера, характеризующая эти связи. Такие структуры называют графами с качественной информацией. Под качественной информацией обычно понимаются некоторые данные о схожести узлов. Любая пара узлов либо наделена свойством схожести, либо нет. Кластеризация графов с качественной информацией подразумевает разбиение множества узлов графов на сообщества таким образом, чтобы в каждом кластере оказалось как можно больше схожих узлов, а между кластерами количество схожих узлов минимизируется. Существует множество методов кластеризации графов с качественной информацией. Каждый их них предлагает некоторую количественную меру, характеризующую качество разбиения, и предлагает алгоритм оптимизирующий разбиение, согласно этой выбранной мере. Среди известных методов можно выделить: • метод Betweenness: алгоритм на основе коэффициента “центральности по посредничеству”, определяемый как количество кратчайших путей между всеми парами вершин, проходящих через данное ребро [1]; • Multilevel: метод, основанный на многоуровневой оптимизации функции модулярности, c использованием эвристики, предложенной в статье [2]; • LabelPropogation: метод, основанный на присвоении меток к каждой вершине. Пошагово выбирается метка с максимальным повторением среди смежных вершин [3]. В работе рассмотрены два алгоритма с различными подходами к кластеризации: 1) «Алгоритм жадной оптимизации», предложенный в статье Ньюмана и Гирвана «Поиск и оценка структуры сообществ в сетях» в 2004г. (M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks); 2) «Осторожный алгоритм» (Algorithm Cautious) Бансаля и Блума, 4

рассмотренный в статье «Корреляция кластеризации» в 2002 г. (N .Bansal, A .Blum, S .Chawla, Correlation clustering). Целью работы является реализация рассмотренных алгоритмов в программной среде, применение их к реальным данным, полученным из социальной сети «Вконтакте», анализ полученных результатов и сравнение работы двух алгоритмов кластеризации. 5

Обзор литературы Наибольший интерес в последних опубликованных работах, касающихся кластеризации, вызывает такая структура сообществ, при которой плотность связей между объектами внутри каждой группы высокая, а между группами низкая. Проблема выделения таких сообществ внутри сети была достаточно хорошо изучена. Ранние методы, такие как алгоритм Керниган-Лин [4], спектральное разбиение [5,6] или иерархическая кластеризация [7] работают хорошо для специфических типов проблемы (в частности, бисекция графа или проблемы с хорошо определенными мерами сходства вершин), но плохо работают для более общих случаев. Для решения этой проблемы ряд новых алгоритмов был предложен в последние годы. Так, Бансаль и Блум в статье [8] решают задачу MaxAgree (максимизация соглашений) и MinDisagree (минимизация рассогласований) и приводят алгоритм «Cautious», который далее в работе детально рассмотрен и применен на практике. Гирван и Ньюман [9,10] предложили алгоритм, который использует промежуточные рёбра в качестве метрики для определения границ сообществ. Этот алгоритм был успешно применен к различным сетям, в том числе сетям сообщений электронной почты, сетям сотрудничества между учеными и музыкантами, обменным и генным сетям. Однако, как отмечается в [10], алгоритм предъявляет высокие требования к вычислительным ресурсам, работает за O( сети с m рёбрами и n вершинами, или O( ) времени на произвольной ) времени на разреженном графе. Это ограничивает применение алгоритма к сетям с максимум несколько тысячью вершинами. В последнее время был предложен ряд быстрых алгоритмов [11,12,13]. В [12] представлен алгоритм, основанный на жадной оптимизации величины, известной как модулярность [10]. Этот метод работает хорошо, как для тестовых задач, так и на практике в реальных ситуациях, и работает быстрее, чем алгоритм Гирвана и Ньюмана. Простая 6

) ) или O( реализация выполняется за время О(( ) на разреженных графах. В работе [10] применён новый алгоритм, который выполняет те же жадные оптимизации алгоритма [6] и, следовательно, дает одинаковые результаты для найденных сообществ. Однако, используя более сложные структуры данных, он работает гораздо быстрее, за время О( глубина “дендограммы”, описывающая структуру сети сообщества. 7 ) где -

Постановка задачи Дан неориентированный граф =(V,W), где V-множество узлов/вершин, W-множество рёбер, соединяющих пары вершин из множества V. )W, если V и V связаны ребром, ( Будем считать, что ( )W, если узлы и не связаны. Пусть - матрица смежности графа : ( { ) Разбиением графа на сообщества будем называть такое разбиение }, т.е. ⋃ множества его вершин, что P={ =V и ∩ =  ≠ 1,…,k. Одной из возможных мер качества разбиения является значение модулярности, предложенное Ньюманом и Гирваном в 2002 году в ходе разработки алгоритма кластеризации вершин графа [9]. Опишем это понятие. Предположим, что вершины разделены в сообщества таким образом, что вершина V принадлежит сообществу . Тогда количество рёбер, расположенных внутри сообществ равно: ∑ ( ) ∑ ∑ ( ) (1) где δ-функция δ( , ) такова, что δ( , )=1 если i=j и 0 в обратном случае. Здесь через m обозначено общее количество рёбер в графе: ∑ . Величина, заданная в (1) будет принимать большие значения для 8

разбиений сети, имеющих много рёбер, находящихся внутри сообществ. Но эта величина не является хорошей мерой качества разбиения, т.к. принимает своё наибольшее значение равное 1 в тривиальном случае, когда все вершины принадлежат единственному сообществу. В работе [10] предложено от величины, описанной в (1) (доли связей внутри сообществ), отнять ожидаемую долю связей, если бы рёбра были размещены случайно: Q= ∑ ] ( [ ) Полученное значение Q авторы назвали модулярностью. обозначена степень вершины Через , т.е. количество рёбер, исходящих из этой вершины ∑ Если количество рёбер . внутри сообщества не отличается от ожидаемого количества для рандомизированной сети, то тогда эта величина будет равна 0. Алгоритм, предложенный в работе [10] предполагает строить разбиения графа так, чтобы величина Q была максимальной. Нашей задачей является реализация предложенного алгоритма и применение его к реальным данным, полученным из социальной сети «Вконтакте». Будет рассмотрен граф с количеством узлов, равным 533. Также интересно сравнить полученные результаты с результатами работы других известных алгоритмов кластеризации. Поэтому в работе также приведён «Осторожный алгоритм» кластеризации Бансаля и Блума, рассмотренного в статье «Корреляция кластеризации» [8]. 9

Глава 1: Алгоритм жадной оптимизации В данной главе опишем сам алгоритм и предоставим его реализацию в программной среде на реальных данных из социальной сети «Вконтакте». Пусть - доля рёбер, соединяющих вершины сообщества с вершинами сообщества : ∑ Через ( ) ( ). определим часть концов рёбер, принадлежащих вершинам в сообществе , т.е.: ∑ ( Величину ∑ ( ∑ ) ( ) можно ( ) представить в виде ( ) ), тогда: ]∑ [ ∑ [ ( ∑ ∑ 1.1 ) ( ) ( ) ( ( ) ) ∑ ( ∑( )] ). Описание алгоритма Опишем работу алгоритма. На каждой итерации действие алгоритма заключается в поиске пары сообществ, в результате объединения которых величина Q изменится максимально. В качестве начального разбиения выбирается такое разбиение, при котором каждый узел представляет собой сообщество. Один способ предусмотреть (и реализовать) процесс объединения сообществ – подумать о сети как о мультиграфе, в котором целое сообщество представлено вершиной, связки рёбер соединяют одни вершины с другими, а ребра внутренних сообществ как самостоятельные 10

рёбра. Матрица смежности этого мультиграфа имеет элементы соединение двух сообществ и и соответствует замене -ых и -ых строк и столбцов их суммой. В алгоритме [12] эта операция явно выполнена на всей матрице, но, если же матрица смежности является разреженной, операция может быть проведена более эффективно с использованием структур данных для разреженных матриц. К сожалению, вычисление Δ i, j с самым большим значением Δ и нахождение пары , становится затратным по времени. Соединение двух сообществ, между которыми нет рёбер, не может повлиять на увеличение значения значения Δ . Нам необходимо рассматривать только для пар i, j, которые соединены одним или более рёбрами. Кроме того, алгоритм использует эффективную структуру данных для отслеживания наибольших значений Δ . Эти улучшения результата в значительной мере сказываются на экономии памяти и времени. В общей сложности сохраняются три структуры данных: 1. Разреженная матрица, содержащая Δ для каждой пары i, j сообществ с, как минимум, одним ребром между ними. 2. Множество H, содержащее наибольшие элементы каждой строки матрицы Δ вместе с метками i, j соответствующих пар сообществ. 3. Обычный векторный массив с элементами . Как описано выше, мы начинаем с каждой вершины, являющейся единственным членом сообщества, в котором и если i и j связаны ; . Таким образом, мы изначально положили, что { (2) и 11

, (3) для каждого i. Наш алгоритм может быть определён следующим образом: 1. Вычисляем начальные значения ∆ и согласно формулам (2) и (3) и заполняем множество H наибольшими элементами каждой строки матрицы ∆Q. 2. Выбираем наибольший элемент ∆ из H, объединяем соответствующие сообщества, обновляем матрицу ∆Q, множество Н и (как описано ниже) и увеличиваем величину Q на соответствующее максимальное значение ∆ . 3. Повторяем шаг 2 до тех пор, пока максимальная величина ∆ принимает положительное значение. Структура наших данных позволяет нам выполнить обновление в шаге 2 довольно быстро. Первым делом, заметим, что в корректировке нуждаются только несколько элементов матрицы ∆Q. Если объединяем сообщества и , то строка, соответствующая сообществу , удаляется из матрицы ∆Q, а обновить необходимо только строку, соответствующую сообществу . Правила обновления следующие. Если сообщество k связано с i и j, тогда: Если k связано с i, но не связано с j, тогда: Если k связано с j, но не связано с i, тогда: Заметим, что Q имеет только один пик за алгоритм, так как после того, как наибольшее значение ∆Q становится отрицательным, далее все значения ∆ Q могут только уменьшаться. Поэтому работа алгоритма останавливается, как только максимальное значение ∆ становится отрицательным. 12

1.2. Реализация алгоритма Описанный алгоритм был реализован на языке JavaScript. Первая часть программы посвящена выгрузке данных из социальной сети «Вконтакте». Для конкретного пользователя считывается множество его друзей и определяются связи между ними. Строится матрица смежности. Вторая часть посвящена непосредственной реализации алгоритма. В третьей части программы реализуется визуализация полученных результатов. Перейдем к подробному описанию каждого их модулей программы. Структура программы: Для запуска программы необходимо открыть файл index.html в любом из браузеров. В данном файле содержится описание пользовательского интерфейса в виде html-разметки и подключены используемые модули (JavaScript файлы). Основные модули: 1. main.js – содержит логику взаимодействия пользователя с интерфейсом. К примеру, реакция на нажатие кнопок. 2. vkFriends.js – содержит методы для работы с API VK, такие как, авторизация, получения списка друзей и др. 3. algorithms.js – содержит реализацию алгоритма кластеризации. 4. graph.js – содержит методы для отображения данных в виде графа. Описание работы программы: 1. Откройте файл index.html в любом из браузеров. 2. В поле «Client Id» введите Id вашего приложения, зарегистрированного в VK. Узнать его или создать новое можно на странице: https://vk.com/apps?act=manage 3. Нажмите на кнопку «Login» и откроется окно с запросом логина и пароля для входа в VK, если они у вас не закешированны в браузере, и запрос на разрешения получения информации о ваших друзьях. После 13

подтверждения всех запросов, вас переадресует на страницу, в адресной строке которой, будет указан access_token для работы с API VK. 4. Введите access_token в поле «access token» и нажмите на кнопку «Определить друзей». Загрузятся данные о ваших друзьях и построится матрица смежности. 5. Нажмите кнопку «Определить связи» и запуститься алгоритм кластеризации результат которого отобразится на странице в виде графа. Для визуализации данных используется D3 JavaScript-библиотека. В программе так же используются: библиотека underscore.js – для работы с множествами (пересечение, разность) и CSS фреймворк Materialize – для стилей визуальных компонент. Результат выполнения программы для конкретного пользователя (автора диплома) отображен на Рис.1. 14

Рис.1. Результат применения жадного алгоритма 533 друга автора были разбиты на 8 основных (достаточно больших) кластеров и несколько кластеров с малым количеством пользователей. Полученные результаты соответствуют ожидаемому разбиению друзей на группы. Например, в один из кластеров попали все пользователи, которые являются друзьями автора по школе, в другой – попали друзья из детского сада и т.д. Программа также тестировалась на множестве друзей других пользователей «Вконтакте», с порядком данных, начиная от 200, где были получены схожие ожидаемые результаты. 15

Таким образом, можно сделать вывод о том, что рассмотренный алгоритм применим для кластеризации данных с порядком, схожим с указанным в нашем реализованном примере. Программный код реализации алгоритма предоставлен в Приложении1. 16

Глава 2: «Осторожный» алгоритм Рассмотрим качественной ещё один информацией. алгоритм В кластеризации статье на «Корреляция графах с кластеризации» («Correlation Clustering») [8] авторы рассматривают две задачи: MaxAgree (максимизация соглашений внутри кластеров и минимизация рассогласований между ними) и MinDisagree (минимизация рассогласований внутри кластеров и максимизация соглашений между кластерами). Задачи являются эквивалентными с точки зрения оптимальности, но различными с точки зрения аппроксимации. 2.1. Описание Алгоритма В отличие от предыдущего алгоритма, «Осторожный» алгоритм производит кластеризацию на полных графах. Пусть G=(V,E) неориентированный невзвешенный полный граф, состоящий из двух множеств: множества V≠Ø, элементы которого называются вершинами или узлами графа, и множества Е неупорядоченных пар из множества V, элементы которого называются рёбрами или связями. Через e( , ) обозначим метку (+ или ) ребра ( , ): e( , )=+, если вершины обладают свойством схожести, e( , )= , если нет. Через N⁺( )={ }U{ :e( , )=+} и N¯( )={ :e( , )= } обозначают "положительных" и "отрицательных" соседей вершины Определение [8]. Вершина соотвественно. называется δ-хорошей по отношению к С, где С  V, если она удовлетворяет следующим условиям: • N⁺( )∩C≥(1-δ)C • N⁺( )∩(V\C)≤δC Набор С называется δ-чистым, если все C являются δ-хорошими по отношению к С. 17

Перейдем к описанию алгоритма. «Осторожный» алгоритм (Algorithm Cautious): 1)Выбирается произвольная вершина и выполняются следующие операции: (а) Пусть A( )=N⁺( ) (b) (Шаг удаления вершины): Пока Ǝ A( ) такой, что x является «3δbad» по отношению к A( ), то A( )=A( )\{ } (с) (Шаг возвращения вершины): Пусть Y={  V, является «7δ- good» по отношению к A( )}. Тогда A( )=A( )UY 2) Удаляем элементы полученного множества A( ) из множества всех вершин графа и повторяем процедуру до тех пор, пока ни одной вершины не останется или пока все преобразованные A( ) не останутся пустыми. В последнем случае оставшиеся на выходе вершины являются одиночными узлами. Авторы предлагают значение параметра δ заданным и равным по величине 1/44. 2.2. Реализация алгоритма Для рассматриваемой задачи кластеризации данных, полученных из социальной сети «Вконтакте» будем считать, что вершины и обладают свойством «схожести» (e( , )=+), если между ними имеется дружественная связь, в противном случае, считаем, что e( , )= . Структура программы: Структура программы совпадает со структурой программы, описанной в первой главе, с той лишь разницей, что в main.js по нажатию на "Определить связи" вызывается другой метод кластеризации, и в algorithms,js реализован «осторожный» алгоритм. Описание работы программы: 18

1. Откройте файл index.html в любом из браузеров. 2. В поле «Client Id» введите Id вашего приложения, зарегистрированного в VK. Узнать его или создать новое можно на странице: https://vk.com/apps?act=manage 3. Нажмите на кнопку «Login» и откроется окно с запросом логина и пароля для входа в VK, если они у вас не закешированны в браузере, и запрос на разрешения получения информации о ваших друзьях. После подтверждения всех запросов, вас переадресует на страницу, в адресной строке которой, будет указан access_token для работы с API VK. 4. Введите access_token в поле «access token» и нажмите на кнопку «Определить друзей». Загрузятся данные о ваших друзьях и построится матрица смежности. 5. Введите значение δ и нажмите "Определить связи" 6. Можно изменить значение δ и нажать "Определить связи". Полученные результаты: При рекомендуемом значении параметра δ= кластеризации 533 (Рис.2.) в результате друзей размер максимально полученного сообщества оказался равным трём. А, к примеру, при использовании параметра δ= ( ) множество друзей оказалось разбитым на два сообщества. Из полученных результатов можно сделать вывод, что «осторожный» алгоритм плохо работает на графах с количеством вершин равным 200-600. Таким образом, можно сделать вывод о том, что рассмотренный алгоритм не применим для кластеризации данных с порядком, схожим с указанным в нашем реализованном примере. Программный код реализации алгоритма предоставлен в Приложении 2. 19

Рис.2. Результат применения «осторожного» алгоритма при δ= Рис.3. Результат применения «осторожного» алгоритма при δ= 20

Заключение В работе были реализованы два алгоритма кластеризации в программной среде. Полученные программы были применены к реальным данным из социальной сети «Вконтакте». Проведен анализ полученных результатов и сравнение работы двух рассмотренных алгоритмов. В результате работы алгоритма жадной оптимизации было получено разбиение на кластеры, отражающие принадлежность друзей к группам знакомств, сформированных по принадлежности к социальным группам. Их условно можно назвать «университет», «школа», «детский сад», «танцевальная школа» и так далее. Работа программы была протестирована для пользователей с числом друзей от 200 до 600. В каждом из случаев, полученные результаты хорошо отображали ожидаемые. В результате работы «осторожного» алгоритма было получено разбиение на кластеры. Однако взаимосвязь между друзьями, соответствующими вершинам одного кластера данного разбиения, определить не удалось. И результат работы данного алгоритма не нашел практического применения для задач кластеризации с числом узлов 200-600. Таким образом, было установлено, что алгоритм жадной оптимизации может быть успешно применен в практических исследованиях для выявления неявных сообществ среди пользователей социальной сети. 21

Список литературы [1] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks.Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002. [2] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10):P10008, 2008. http://www.arxiv.org/abs/0803.0476 [3] sha Nandini aghavan, eka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in largscale networks.Physical Review E, 76(3):036106, 2007. http://www.arxiv.org/abs/0709.2938 [4] B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs.Bell System Technical Journal 49, 291–307 (1970). [5] ] M. Fiedler, Algebraic connectivity of graphs.Czech.Math. J.23, 298–305 (1973). [6] A. Pothen, H. Simon, and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 430–452 (1990). [7] J. Scott,Social Network Analysis: A Handbook. Sage, London, 2nd edition (2000). [8] N .Bansal, A .Blum, S .Chawla, Correlation clustering, in: Proceedings of 43rd FOCS, 2002, pp .238–247 [9] M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002). [10] M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004). [11] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Deﬁning and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658–2663 (2004). [12] M. E. J. Newman, Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004). 22

[13] ] F. Wu and B. A. Huberman, Finding communities in linear time: A physics approach. Eur. Phys. J. B 38, 331–338 (2004). 23

Приложение 1. index.html <!DOCTYPE html> <meta charset="utf-8"> <script src="js\lib\jquery.js"></script> <script src="js\lib\materialize.js"></script> <script type="text/javascript" src="js\lib\underscore.js"></script> <script type="text/javascript" src="js\lib\d3.v3.js" charset="utf-8"></script> <script type="text/javascript" src="js\vkFriends.js"></script> <script type="text/javascript" src="js\graph.js"></script> <script type="text/javascript" src="js\algorithms.js"></script> <script type="text/javascript" src="js\main.js"></script> <link rel="stylesheet" href="css\materialize.css"> <link rel="stylesheet" href="css\style.css"> <body> <div class="progress"> <div class="indeterminate"></div> </div> <div class="row alert alert-success"><span></span></div> <div class="row alert alert-error"><span></span></div> <div class="row"> <input class="col s2 m1" id="clientId" placeholder="Client Id"></input> <a class="col s2 m1 waves-effect waves-light btn" id="login" href="">Login</a> <input class="col s4 m2" id="token" placeholder="access token"></input> <a id="findFriends" class="col s2 m2 waves-effect waves-light btn">Определить друзей</a> <a id="getRelations" class="col s2 m2 waves-effect waves-light btn marginleft">Определеть связи</a> </div> <div id="graphs"> <div id="circlePacking"></div> <div id="forceLayout" class="hide"></div> </div> </body> main.js $(document).ready(function() { function sleep(milliseconds) { var start = new Date().getTime(); for (var i = 0; i < 1e7; i++) { if ((new Date().getTime() - start) > milliseconds){ break; } } }; var showAlert = function(message, type){ $('.alert').hide(); $('.alert-'+ type + ' span').html(message); $('.alert-'+ type).show(); }; var hideAlerts = function(){ $('.alert').hide(); }; 24

deltaQ[k].nodes); deltaQ[maxJ][k] = isNeighborsWithI && isNeighborsWithJ ? deltaQ[maxI][k] + deltaQ[maxJ][k] : isNeighborsWithI && !isNeighborsWithJ ? deltaQ[maxI][k] - 2 * a[maxJ] * a[k] : isNeighborsWithJ && !isNeighborsWithI ? deltaQ[maxJ][k] - 2 * a[maxI] * a[k] : 0; deltaQ[k][maxJ] = deltaQ[maxJ][k]; var row = deltaQ[k]; delete row[maxI]; } deltaQ[maxJ].nodes deltaQ[maxJ].nodes.concat(deltaQ[maxI].nodes); delete deltaQ[maxJ][maxI]; delete deltaQ[maxI]; a[maxJ] = a[maxJ] + a[maxI]; a[maxI] = 0; } = var communities = []; for(var item in deltaQ) { communities.push(deltaQ[item].nodes); }; return communities; }; var isNeighbors = function(source, targer) { var res = false; $.each(source, function(index, sourceNode) { if (_.intersection(neighbors[sourceNode], targer).length > 0) { res = true; return false; } }); return res; }; return { findCommunity: findCommunity } }()); graph.js var showCirclePacking = function(data) { var diameter = 960, format = d3.format(",d"); var pack = d3.layout.pack() .size([diameter - 4, diameter - 4]) .value(function(d) { return d.size; }); $('#circlePacking').empty(); var svg = d3.select("#circlePacking").append("svg") .attr("width", diameter) .attr("height", diameter) .append("g") 28

.attr("transform", "translate(2,2)"); var node = svg.datum(data).selectAll(".node") .data(pack.nodes) .enter().append("g") .attr("class", function(d) { return d.children ? "node" : "leaf node"; }) .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); node.append("title") .text(function(d) { return d.name; }); node.append("circle") .attr("r", function(d) { return d.r; }) .style("fill", "#eee"); var images = node.filter(function(d) { return }).append("svg:image") .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -16;}) .attr("y", function(d) { return -16;}) .attr("height", 32) .attr("width", 32); !d.children; // make the image grow a little on mouse over and add the text details on click var setEvents = images .on( 'mouseenter', function() { // select element in current context d3.select( this ) .transition() .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -128;}) .attr("y", function(d) { return -128;}) .attr("height", 256) .attr("width", 256) .style("z-index", 10); }) // set back .on( 'mouseleave', function() { d3.select( this ) .transition() .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -16;}) .attr("y", function(d) { return -16;}) .attr("height", 32) .attr("width", 32) .style("z-index", 1); }); d3.select(self.frameElement).style("height", diameter + "px"); }; 29

Приложение 2. index.html <!DOCTYPE html> <meta charset="utf-8"> <script src="js\lib\jquery.js"></script> <script src="js\lib\materialize.js"></script> <script type="text/javascript" src="js\lib\underscore.js"></script> <script type="text/javascript" src="js\lib\d3.v3.js" charset="utf-8"></script> <script type="text/javascript" src="js\vkFriends.js"></script> <script type="text/javascript" src="js\graph.js"></script> <script type="text/javascript" src="js\algorithms.js"></script> <script type="text/javascript" src="js\main.js"></script> <link rel="stylesheet" href="css\materialize.css"> <link rel="stylesheet" href="css\style.css"> <body> <div class="progress"> <div class="indeterminate"></div> </div> <div class="row alert alert-success"><span></span></div> <div class="row alert alert-error"><span></span></div> <div class="row"> <input class="col s2 m1" id="clientId" placeholder="Client Id"></input> <a class="col s2 m1 waves-effect waves-light btn" id="login" href="">Login</a> <input class="col s4 m2" id="token" placeholder="access token"></input> <a id="findFriends" class="col s2 m2 waves-effect waves-light btn">Определить друзей</a> <input id="delta" class="col s2 m1" placeholder="delta" value="0.0227272727272727"></input> <a id="getRelations" class="col s2 m2 waves-effect waves-light btn">Определеть связи</a> </div> <div id="graphs"> <div id="circlePacking"></div> <div id="forceLayout" class="hide"></div> </div> </body> main.js $(document).ready(function() { function sleep(milliseconds) { var start = new Date().getTime(); for (var i = 0; i < 1e7; i++) { if ((new Date().getTime() - start) > milliseconds){ break; } } }; var showAlert = function(message, type){ $('.alert').hide(); $('.alert-'+ type + ' span').html(message); $('.alert-'+ type).show(); }; var hideAlerts = function(){ 30

$('.alert').hide(); }; var showProgress = function(){ $('.progress').show(); }; var hideProgress = function(){ $('.progress').hide(); } $('#login').click(function() { var link = 'https://oauth.vk.com/authorize?client_id=' + $('#clientId').val() + '&scope=friends,offline&redirect_uri=https://oauth.vk.com/blank.html&display=page&v=5.50& response_type=token'; window.open(link); }); var friends; $('#findFriends').click(function() { hideAlerts(); showProgress(); findFriends($('#token').val()) .done(function (data){ friends = $.grep(data.response, function(item, i) { return !item.deactivated; }); var uids = $.map(friends, function(friend) {return friend.uid; }); $.each(friends, function(index, friend) { if(index > 0 && (index % 2 === 0)) sleep(1000); findCommonFriends($('#token').val(),friend.uid) .done(function(data){ if(data.error) { showAlert(data.error.error_msg, 'error'); } friend.friends = $.grep(data.response, function(item, i) { return _.contains(uids, item); }); }) .fail(function (jqXHR, textStatus, errorThrown) { showAlert(jqXHR.responseText, 'error'); }); }); showAlert('Найдено друзей: <strong>' + friends.length 'success'); hideProgress(); }) .fail(function (jqXHR, textStatus, errorThrown) { showAlert(jqXHR.responseText, 'error'); hideProgress(); }); }); $('#getRelations').click(function() { hideAlerts(); if(!friends || friends.length == 0) { showAlert('Не удалось определить друзей.', 'error'); return; } 31 + '</strong>.',

showProgress(); var delta = parseFloat($('#delta').val()); var groups = Algorithms.oldAlgorithm(friends, delta); showCirclePacking(groups); $('.progress').hide(); }); $('#graphTypes li a').click(function(){ $('#graphs div').hide(); var type = $(this).data('type'); var navItem = $('#' + type); navItem.show(); $('#graphTypes li').removeClass('active'); $(this).parent().addClass('active'); }); }); vkFriends.js var findFriends = function (token) { return $.ajax({ type: 'GET', dataType: 'jsonp', data: {}, url: 'https://api.vk.com/method/friends.get?order=name&fields=nickname,photo_200_orig,educatio n&access_token=' + token }); }; var findCommonFriends = function(token, friendUid) { return $.ajax({ type: 'GET', dataType: 'jsonp', data: {}, async: false, url: 'https://api.vk.com/method/friends.getMutual?target_uid=' friendUid + '&access_token=' + token }); }; + algorithms.js Algorithms = (function() { var oldAlgorithm = function(friends, delta) { var isGood = function(users, n, c, delta) { if(_.intersection(n, c).length < (1 - delta) * c.length) return false; return _.intersection(n, _.difference(users, c)).length <= delta * c.length; }; var used = []; var groups = {name: "Пользователь", children: []}; var index = 0; var users = $.map(friends, function(friend) { return friend.uid; }); while(users && users.length > 0 && index < users.length) { 32

else { index++; } } return groups; }; return { oldAlgorithm: oldAlgorithm } }()); graph.js var showCirclePacking = function(data) { var diameter = 960, format = d3.format(",d"); var pack = d3.layout.pack() .size([diameter - 4, diameter - 4]) .value(function(d) { return d.size; }); $('#circlePacking').empty(); var svg = d3.select("#circlePacking").append("svg") .attr("width", diameter) .attr("height", diameter) .append("g") .attr("transform", "translate(2,2)"); var node = svg.datum(data).selectAll(".node") .data(pack.nodes) .enter().append("g") .attr("class", function(d) { return d.children ? "node" : "leaf node"; }) .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); node.append("title") .text(function(d) { return d.name; }); node.append("circle") .attr("r", function(d) { return d.r; }) .style("fill", "#eee"); var images = node.filter(function(d) { return }).append("svg:image") .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -16;}) .attr("y", function(d) { return -16;}) .attr("height", 32) .attr("width", 32); !d.children; // make the image grow a little on mouse over and add the text details on click var setEvents = images .on( 'mouseenter', function() { // select element in current context d3.select( this ) .transition() .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -128;}) .attr("y", function(d) { return -128;}) .attr("height", 256) 34

.attr("width", 256) .style("z-index", 10); }) // set back .on( 'mouseleave', function() { d3.select( this ) .transition() .attr("xlink:href", function(d) { return d.photo_200_orig;}) .attr("x", function(d) { return -16;}) .attr("y", function(d) { return -16;}) .attr("height", 32) .attr("width", 32) .style("z-index", 1); }); d3.select(self.frameElement).style("height", diameter + "px"); }; 35

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв