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