Введение
Обзор литературы
Постановка задачи
Глава 1. Алгоритм жадной оптимизации
1.1. Описание алгоритма
1.2. Реализация алгоритма
Глава 2. «Осторожный» алгоритм
2.1. Описание алгоритма
2.2. Реализация алгоритма
Заключение
Список литературы
Приложение 1
Приложение 2 .
В современном, стремительно развивающемся мире во многих
производственных, научно-естественных, технических, экономических и др.
областях стремительно растет объем данных. Вместе с тем возрастает
потребность в упорядочении, выделении связанных групп по принципу
схожести из огромного количества объектов. Именно такого рода проблему и
помогает решить кластеризация. Информация, полученная вследствие
кластеризации данных полезна и многогранна-вот лишь некоторые области
практического применения качественных кластеров:
1. В области медицины используется кластеризация заболеваний, их
симптомов, лечения.
2. В археологии устанавливаются таксономии каменных сооружений и
древних объектов и т.д.
3. В маркетинге задачей кластеризации может являться выделение групп
потребителей и конкурентов.
4. В социологии задача кластеризации - разбиение респондентов на однородные группы.
Ещё одной областью применения методов кластеризации данных
является интернет-пространство. С его развитием продолжают активно
набирать популярность такие социальные сети как «Вконтакте»,
«Одноклассники», «Facebook», и др. Количество пользователей,
зарегистрированных в этих сетях, огромно и с каждым днем оно только
увеличивается. Эти сети представляют собой богатый источник данных.
Особый интерес вызывает структура графа, индуцированного по ссылкам
дружбы. В представленной работе будут проанализированы некоторые
методы кластеризации и применены к данным социальной сети «Вконтакте»
с целью определения неявных сообществ среди друзей.4
Социальная сеть представима в виде графа, в котором узлами являются
пользователи, а наличие связи между узлами означает то, что пользователи
находятся в «друзьях» друг у друга. При этом отсутствует какая-либо
количественная мера, характеризующая эти связи. Такие структуры
называют графами с качественной информацией. Под качественной
информацией обычно понимаются некоторые данные о схожести узлов.
Любая пара узлов либо наделена свойством схожести, либо нет.
Кластеризация графов с качественной информацией подразумевает
разбиение множества узлов графов на сообщества таким образом, чтобы в
каждом кластере оказалось как можно больше схожих узлов, а между
кластерами количество схожих узлов минимизируется.
Существует множество методов кластеризации графов с качественной
информацией. Каждый их них предлагает некоторую количественную меру,
характеризующую качество разбиения, и предлагает алгоритм
оптимизирующий разбиение, согласно этой выбранной мере. Среди
известных методов можно выделить:
• метод 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) Бансаля и Блума,5
рассмотренный в статье «Корреляция кластеризации» в 2002 г. (N .Bansal, A
.Blum, S .Chawla, Correlation clustering).
Целью работы является реализация рассмотренных алгоритмов в
программной среде, применение их к реальным данным, полученным из
социальной сети «Вконтакте», анализ полученных результатов и сравнение
работы двух алгоритмов кластеризации
В работе были реализованы два алгоритма кластеризации в
программной среде. Полученные программы были применены к реальным
данным из социальной сети «Вконтакте». Проведен анализ полученных
результатов и сравнение работы двух рассмотренных алгоритмов.
В результате работы алгоритма жадной оптимизации было получено
разбиение на кластеры, отражающие принадлежность друзей к группам
знакомств, сформированных по принадлежности к социальным группам. Их
условно можно назвать «университет», «школа», «детский сад»,
«танцевальная школа» и так далее. Работа программы была протестирована
для пользователей с числом друзей от 200 до 600. В каждом из случаев,
полученные результаты хорошо отображали ожидаемые.
В результате работы «осторожного» алгоритма было получено разбиение
на кластеры. Однако взаимосвязь между друзьями, соответствующими
вершинам одного кластера данного разбиения, определить не удалось. И
результат работы данного алгоритма не нашел практического применения для
задач кластеризации с числом узлов 200-600.
Таким образом, было установлено, что алгоритм жадной
оптимизации может быть успешно применен в практических исследованиях
для выявления неявных сообществ среди пользователей социальной сети
