Введение 3
Актуальность 4
Цель работы 5
Задачи работы 5
Практическая значимость работы 6
Глава 1. Обзор алгоритмов визуализации графов и существующих решений 7
1.1 Представление структуры пользовательской дискуссии 7
1.2 Обзор Force-directed алгоритмов 8
1.3 Обзор существующих инструментов 21
Глава 2. Адаптация методов раскладки графов для анализа
пользовательских дискуссий 23
2.1 Постановка эксперимента 23
2.2 Проведение эксперимента 24
2.3 Результаты 34
Глава 3. Разработка программного комплекса для визуализации
пользовательских дискуссий 36
3.1 Функциональные характеристики приложения 37
Заключение 45
Результаты работы 45
Перспективы развития 46
Список литературы 47
В наши дни веб активно эволюционирует. Люди со всех уголков земли могут принимать активное участие в генерации контента. Им не нужно знать технологии, языки программирования и т.п., чтобы создать свой веб-ресурс. Каждый человек может с легкостью завести сообщество или страницу в социальной сети, так как для всего этого есть интуитивно понятные и доступные инструменты. В связи с этим пользователей социальных сетей становится все больше и больше (на данный момент в Twitter зарегистрировано 1.3 миллиарда аккаунтов, 330 миллионов из них являются активными пользователями), а следовательно, и количество информации, которое они генерируют, непрерывно растет.
Исследования, которые ведутся в настоящий момент [7], [8], [12], направлены на изучение поведения пользователей в дискуссиях в контексте реальных событий. Так как любое событие, происходящее в нашем мире, всегда сопровождается его обсуждением в социальных сетях.
Наука, занимающаяся исследованием социальных сетей в терминах теории графов — это и есть анализ социальных сетей (АСС или “social network analysis / SNA” в англоязычной литературе). Две основные задачи АСС — это сентиментный и структурный анализ сетей. Сентиментный анализ занимается изучением эмоций пользователей в сети, в его основе лежат нейролингвистическое программирование и машинное обучение. Структурный же анализ занимается исследованием сетей, посредством представления их в виде графов, в его основе лежит поиск эффективного метода визуализации графа для моделирования его структуры.
Данная работа посвящена структурному анализу пользовательских дискуссий в сети по реальным событиям.
Актуальность
В связи с активно растущим количеством информации в сети из-за разного контингента, числа пользователей и т.п. перед нами стоим интересная и при этом сложная задача — как лучше усвоить данную информацию.
Проблематика больших данных крайне актуальна из-за их разнообразия, высокой скорости поступления и конечно же большого объёма. Исследования, занимающиеся данной проблемой, решают такие задачи, как нахождение важных пользователей в сети [7], выявление их влияния на других пользователей [8], а также нахождение скрытых сообществ [12]. Поэтому семантический и структурный анализ дискуссий в сети является очень важным.
Проблема визуализации больших данных связана в первую очередь с нахождением и развитием методов, которые помогут компактно и эргономично их представить.
Глобальной же проблемой является именно восприятие большой информации, так как количество узлов в графе может достигать нескольких миллионов. Выбор эффективного метода раскладки графа позволяет отследить образовавшиеся сообщества, оценить важность узла по его расположению и размеру (например концентрация популярных пользователей в центре раскладки или же наоборот на ее периферии; зависимость размера узла от его степени), а так же выявить структуру и основные свойства графа. Всё это необходимо для качественного усвоения большой информации различными специалистами.
Цель работы
Целью данной работы является разработка методов и инструментов для визуализации структуры дискуссий разного объёма в рамках реальных событий в социальных сетях, позволяющих эффективным образом представлять пользователей и их связи для качественного усвоения даже самой большой информации экспертами из смежных предметных областей: социологами, политологами и т.д.
В данной выпускной квалификационной работе были выполнены следующие задачи:
• Проведен обзор научной литературы по теме исследования
• Проведен обзор алгоритмов раскладки графов
• Проведен обзор существующих решений для визуализации графов
• Проведено тестирование и апробация существующих алгоритмов раскладки графов на четырех реальных дискуссиях разного объёма, а также выявлены эффективные методы визуализации графов - Force Atlas 2 и Circle pack layout
• Разработан и реализован программный комплекс на основе клиент- серверного приложения, состоящий из алгоритма Force Atlas 2 и двух интерактивных карт (по сообществам и по степеням вершин), позволяющий эффективно взаимодействовать со структурой дискуссии в виде пользовательского веб-графа, а также имеющий возможность просмотра дискуссии
о Кодовая база приложения доступна по данной ссылке: https://github.com/IrinaS-77/Analysis of the Biryulyovo- Russia discussion
• Созданы интерактивные карты по сообществам для четырех дискуссий. Ознакомиться с ними можно перейдя по следующим ссылкам:
о Бирюлево: https://irinas-77.github.io/Biryulyovo web-
graph/network/
о Кельн: https://irinas-77.github.io/Cologne web-graph/network/
о Фергюсон: https://irinas-77.github.io/Ferguson web-graph/network/
о Шарли Эбдо: https://irinas-77.github.io/Charlie Hebdo web-
graph/network/
Перспективы развития
Данная дипломная работа несет следующие перспективы развития:
• Расширение функционала приложения
о Добавление не менее эффективных методов визуализации графов в программный компонент
о Принятие на вход различных форматов данных: csv, json, xml, gexf и другие
о Добавление возможностей в интерактивные карты: скрытие слабо активных пользователей (число связей меньше 3, например)
• Тестирование работы приложения на большем числе дискуссий разного объёма
