Введение 2
Постановка задачи 4
Обзор литературы 5
Глава 1. Обнаружение сообществ 8
1.1. Обзор предметной области 8
1.2. Система для распределённых вычислений на графах GraphChi 11
1.3. Алгоритм Гирвана-Ньюмана и его реализация на GraphChi 13
1.3.1. Нахождение кратчайших путей и вычисление промежуточности 15
1.4. Вычисление PageRank 21
1.4.1. Определение и краткий обзор существующих подходов 21
1.4.2. Описание выбранного алгоритма и его реализация на GraphChi 24
1.5. Алгоритм распространения меток (Label Propagation Algorithm) 26
1.5.1. Описание метода и его реализация на GraphChi 27
1.6. Обобщение модулярности на ориентированные графы и LinkRank 28
1.7. Тестирование работы алгоритмов 29
Глава 2. Текстовая классификация и тематическое моделирование 32
2.1. Предварительная обработка текстовой информации 32
2.2. Обзор подходов к классификации документов 36
2.2.1 Байесовский классификатор 37
2.2.2. Практическая реализация разделения сообщений на категории 39
2.5. Тематическое моделирование 43
2.5.1. Латентное размещение Дирихле 43
2.5.2. Критерий качества модели 45
2.6. Практическая реализация тематического моделирования 45
Глава 3. Тестирование работы программы 47
3.1. Сбор информации из социальной сети ВКонтакте 47
3.2. Обнаружение сообществ в полученной социальной сети 49
3.3. Текстовая классификация и тематическое моделирование сообщений пользователей полученной сети 50
Выводы 55
Заключение 57
Приложение 1 58
Список литературы 61
Купить

За последние десятилетия огромное внимание стало уделяться связям, существующим в нашем обществе, что привело к появлению отдельного направления исследований. Ученые рассматривают социальные отношения в рамках теории сетей, в основе которой лежит математическая теория графов, а также эмпирические исследования в области различных общественных наук (антропологии, социологии, биологии и др.)[1]. Основные термины теории сетей включают в себя понятие узла (отвечает за отдельного участника в пределах сети) и связи (отображает различные отношения между участниками сети: дружеские, рабочие, учебные и другие) [1].
Данное направление исследований в последнее время переживает новый подъем благодаря появлению социальных онлайн-ресурсов таких как социальные сети, форумы и др. На сегодняшний день социальные сети (такие как Facebook, Вконтакте, Instagram, Одноклассники, Twitter и др.) являются одними из самых посещаемых сайтов во всем мире [2]. Доступность большого объёма персональной информации пользователей (интересы, мнения, связи с другими пользователями) открывает большие возможности для эффективного решения исследовательских и бизнес-задач, решение которых раннее было очень кропотливым, трудоёмким, а зачастую невозможным, что делает данное направление исследований актуальным. Исследованиями социальных данных активно занимаются университеты Стэнфорд [3, 4], Карнеги-Меллон, Оксфорд, INRIA, а также компании Facebook, Google, Yahoo!, LinkedIn и многие другие [5].
Под анализом социальных данных понимается их обработка, позволяющая определить организацию исходной сети, обобщая их по определенному критерию, и выявить какие-либо признаки, характеризующие эти данные, такие как: интересы участников, их образ жизни, мнения по каким-либо вопросам и т.д.
Анализ социальных данных позволяет произвести моделирование распространения информации в сети, выявить характерные признаки поведения пользователя, помогает в развитии систем рекомендаций, а также прогнозировании связей. В частном секторе фирмы используют анализ социальных сетей для поддержки такой деятельности, как взаимодействие и анализ клиентов, маркетинг и бизнес-аналитика. Использование анализа социальных сетей государственным сектором включает в себя развитие стратегий участия руководства, использование средств массовой информации и основанное на сообществах решение проблем.
Основными сложностями в работе с социальными данными являются: их большой объем, многообразие, неоднозначное качество получаемой информации (недостоверная информация, спам, ложные аккаунты), которые делают процесс анализа вручную почти невозможным. К примеру, в социальной сети ВКонтакте на сегодняшний день зарегистрировано более 350 миллионов пользователей [6], а база данных социальной сети Facebook содержит более 1 миллиарда пользовательских аккаунтов и более 100 миллиардов связей между ними. Каждый день пользователи добавляют более 200 миллионов фотографий и оставляют более 2 миллиардов комментариев [5]. В связи с этим, возникает потребность в новых решениях, позволяющих осуществлять распределённую обработку данных, а также сделать её более доступной для большего количества исследователей.
Купить