Поиск сообществ пользователей

Естественным свойством человеческого общества является тенденция к объединению в различные сообщества. Аналогичная картина наблюдается в социальных сетях, где пользователи объединяются явно (используя средства сети для создания групп и взаимодействия внутри них) либо неявно (устанавливая связи на основе общей или похожей деятельности, роли, социального круга, интереса или других свойств).

К примеру, знания о структуре сообществ незаменимы для предсказания связей и атрибутов пользователей, расчёта близости пользователей в социальном графе, оптимизации потоков данных в социальной сети, некоторых аналитических приложений и т.д.

Информация о сообществах (модульной структуре) социальной сети на глобальном уровне находит применение в системах рекомендаций, фильтрации спама и многих других приложениях. Автоматически определённые сообщества ближайших контактов пользователя в социальной сети могут применяться для оптимизации потоков входящей и исходящей информации (отправить сообщение только сообществу “Коллеги”, прочитать новости только от сообщества “Близкие друзья”).

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

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

Для оценки производительности разработанного метода было проведено тестирование распределённой реализации на основе фреймворка Apache Spark с помощью сервиса облачных вычислений Amazon ЕС2. По результатам тестирования метод показал линейную масштабируемость от числа вершин в исходном графе, а также от количества параллельно функционирующих вычислительных узлов.

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