Тип работы:
Предмет:
Язык работы:


Компромиссное решение в конкурентной модели по выявлению скрытых сообществ в социальной сети YouTube

Работа №128058

Тип работы

Магистерская диссертация

Предмет

база данных

Объем работы50
Год сдачи2021
Стоимость5650 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
91
Не подходит работа?

Узнай цену на написание


Введение 4
Глава 1. Обзор литературы 6
Глава 2. Алгоритмы выявления скрытых сообществ 16
2.1. Математические обозначения 16
2.2. Алгоритм поиска ядер графа 17
2.3. Алгоритм поиска клик графа 19
2.4. Алгоритмы поиска кластеров графа 20
2.4.1. MST 20
2.4.2. NAG 21
Глава 3. Компромиссное решение 23
Глава 4. Программная реализация 27
4.1. Архитектура 27
4.2. Обработка данных 28
Глава 5. Апробация 31
5.1. Ядра графа 32
5.2. Клики графа 34
5.3. Кластеры графа (MST) 35
5.4. Кластеры графа (NAG) 37
5.5. Компромиссное решение 38
5.6. Тестирование 39
Заключение 46
Список литературы 47

На сегодняшний день социальная сеть является одним из основных способов организации взаимодействий между людьми. В качестве «взаимодействия» можно понимать как явное обозначение дружбы (например, добавил в список друзей или контактов), обмен сообщениями, так и участие в каких-либо дискуссиях, что образуются благодаря комментариям под записью, видео или фотографией. Можно провести аналогию с СМИ: пользователи доверяют информации, что получают через социальную сеть больше, чем другим источникам новостей, например, телевидению или журналам.
Анализ социальных сетей на сегодняшний день развивается достаточно быстро. Одной из центральных задач анализа социальной сети является задача выявления скрытых сообществ на основе исследования взаимодействий между пользователями. Под скрытыми сообществами понимаются группы людей, которые невозможно определить без применения специальных математических алгоритмов.
Объектом исследования является социальная сеть YouTube. По статистике на 2020 год она охватывает 2 миллиарда пользователей в мире (69.1% населения в России). Это говорит о том, что в YouTube присутствует достаточно большое количество пользователей, из которых формируются крупные сообщества, что интересно исследовать в дальнейшем.
Задача выявления скрытых сообществ относится к классу задач кластеризации. Одним из интересных направлений исследования является определение пересекающихся сообществ (overlapping community), случай, когда один и тот же пользователь может относиться сразу к нескольким скрытым группам.
Актуальность данного направления исследований обусловлена популярностью использования социальной сети YouTube. Если изначально данная социальная сеть была создана с целью распространения видео по Всемирной паутине, то сейчас ее используют для распространения какой-либо информации, начиная с рекламы и спама, заканчивая сообщениями для участников скрытой группы людей. Поэтому считается, что в данном исследовании может быть заинтересовано большое количество физических лиц или организаций, что смогут выбрать конкретный алгоритм для использования его в своих целях в дальнейшем.
Применяя разные алгоритмы по выявлению таких сообществ, мы получаем несколько результатов для дальнейшего исследования со стороны агентов (физическое лицо или организация). Интересно было бы оценивать их эффективность и рассматривать их применение в социологии, политике, экономике. У каждого агента есть собственная оценка алгоритмов, он расставляет эти алгоритмы в порядке приоритета. Таким образом, между множеством агентов возникает противоречие в выборе конкретного алгоритма по поиску скрытых сообществ. В связи с этим в данной работе рассматривается задача поиска компромиссного решения, что основывается на теории игр. Оптимальное решение задачи позволяет найти компромисс для агентов в возникающей конфликтной ситуации.
На сегодняшний день существует большое количество инструментов, направленных на выявление кластеров пользователей в социальной сети с использованием теории графов, однако ни один из них не является универсальным. Обусловлено это тем, что в данных решениях можно подчеркнуть либо высокую стоимость, либо отсутствие открытого доступа к исходному коду и, как следствие, невозможность направления компонентов программы на решение определенных задач.
Целью исследовательской работы является разработка программного продукта, что позволяет:
1. Выявить скрытые сообщества;
2. Визуализировать результаты;
3. Сохранить полученные результаты для дальнейшей оценки со стороны агентов;
4. Найти компромиссное решение по полученным оценкам.
В данной работе использованы идеи из статьи [1]. Отсюда наследуется способ сбора необходимых для исследования данных и математическая модель.
Сформулируем задачи для достижения поставленной цели:
1. Модифицировать алгоритм сбора данных;
2. Реализовать/включить в проект новые алгоритмы по выявлению скрытых сообществ и протестировать их;
3. Реализовать возможность настройки параметров для алгоритмов;
4. Реализовать визуализацию c отображением сообществ;
5. Реализовать пользовательский интерфейс для знакомства и оценки результатов алгоритмов со стороны агентов;
6. Реализовать алгоритм поиска компромиссного решения;
7. Провести апробацию и тестирование на реальных данных социальной сети YouTube.
В результате разработано программное решение, что предоставляет для ознакомления агентам несколько подходов по выявлению скрытых сообществ и помогает выбрать им совместное оптимальное решение, решить конфликтную ситуацию.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!


В ходе научно-исследовательской работы были выполнены все поставленные задачи, а именно:
• реализованы алгоритмы по выявлению скрытых сообществ;
• реализована возможность выбора параметров для конкретного алгоритма;
• модифицирован алгоритм сбора данных;
• реализована визуализация выявленных групп;
• реализован User Interface для знакомства и оценки результатов алгоритмов агентами;
• реализован алгоритм поиска компромиссного решения;
• проведена апробация и тестирование на актуальных данных за 2020 год социальной сети YouTube.
Отметим, что в качестве скрытых сообществ можно считать отдельные ядра, клики, кластеры или же разделять на некоторые классы тех пользователей, которые относятся сразу к нескольким ядрам или кликам. Используя рассмотренные алгоритмы, мы можем разбивать множество вершин на группы, а затем находить среди них узлы, которые входят сразу в несколько сообществ или же относятся к достаточно крупным кластерам.
В перспективе данную работу можно использовать как в поиске террористических группировок в социальной сети YouTube, так и в направлении каких-либо других социальных исследований. Для увеличения спроса на рынке в будущем программный продукт необходимо модифицировать по следующим пунктам:
• производительность;
• параметры алгоритмов выявления скрытых сообществ.
Результаты исследовательской работы частично опубликованы в статье [2].


[1] . Щеникова С.А. Методы анализа AD HOC дискуссий в социальной сети YouTube // Control Processes and Stability (CPS’19). Том 6, раздел 1 (2019). С. 378-382.
[2] . Малафеев О.А., Щеникова С.А., Скворцова О.И. Математическое моделирование задач экономической конкуренции по выявлению скрытых сообществ в социальной сети // Информационные технологии в образовании (2021). С. 167-172.
[3] . Santo F. Community detection in graphs // Physics Reports 486, 75-174 (2010). P.14 - 80.
[4] . Cosciaa M., Giannotti F., Pedreschia D. A Classification for Community Discovery Methods in Complex Networks // Statistical Analysis and Data Mining journal, Special Issue: Networks. Volume 4, Issue 5, pages 512-546 (2011). P.5 - 25.
[5] . Schaeffer S.E. Graph clustering // Computer Science Review 1(1), 27-64 (2007). P.9 - 29.
[6] . Amelio A., Pizzuti C. Overlapping Community Discovery Methods: A Survey. // Social Networks: Analysis and Case Studies. Lecture Notes in Social Networks (2014). P. 3 - 16.
[7] . Nerurkar P., Chandane M., Bhirud S. A Comparative Analysis of Community Detection Algorithms on Social Networks: ICCI-2017. 10.1007/978-981-13-1132-1_23 (2019). P. 4 - 8.
[8] . Reichardt J., Bornholdt S. Statistical mechanics of community detection // Phys. Rev. (2006). P. 113-126.
[9] . Nerurkar, Pranav & Chandane, Madhav & Bhirud, Sunil. Community Detection Using Node Attributes: A Non-negative Matrix Factorization Approach: ICCI-2017. 10.1007/978-981-13- 1132-1_22 (2019). P. 5 - 8.
[10] . Fiscarelli A.M., Brust M.R., Danoy G., Bouvry P. A Memory-Based Label Propagation Algorithm for Community Detection // COMPLEX NETWORKS 2018. Studies in Computational Intelligence, vol 812. Springer, (2019).
[11] . Fiscarelli, Antonio, Brust, Matthias, Danoy, Gregoire, Bouvry, Pascal. A vertex-similarity clustering algorithm for community detection // Journal of Information and Telecommunication. 4. 1-15. 10.1080/24751839.2019.1686683 (2019). P. 4 - 6.
[12] . Ning-Ning W, Zhen J., Xiao-Long P. Community Detection with Self-Adapting Switching Based on Affinity // Complexity, vol. 2019, Article ID 6946189 (2019). URL:https://doi.org/10.1155/2019/6946189
[13] . Jaiswal R., Ramanna S. Detecting Overlapping Communities Using Distributed Neighbourhood Threshold in Social Networks // Bello R., Miao D., Falcon R., Nakata M., Rosete A., Ciucci D. (eds) Rough Sets. IJCRS 2020. Lecture Notes in Computer Science, vol 12179. Springer. URL: https://doi.org/10.1007/978-3-030-52705-1_32
[14] . Ge J., Sun H., Xue C., et al. LPX: Overlapping community detection based on X-means and label propagation algorithm in attributed networks // Computational Intelligence; 37: 484­510 (2021). URL: https://doi.org/10.1111/coin.12420.
[15] . Nyunt Nyunt S. Overlapping Community Detection Using Centrality Measure and Local Seed Information //Journal of Computer Applications and Research, Volume 1, No 1 (2020).
...


Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ