Математическое и программное обеспечение для поиска людей по заданным критериям в социальных сетях с использованием теории графов и эвристики шести рукопожатий
Выпускная квалификационная работа изложена на 60 страницах, содержит 17 иллюстраций, 2 формулы, 2 таблицы, список использованных источников из 4 наименований и 1 приложение.
Ключевые слова: ГРАФОВЫЕ БАЗЫ ДАННЫХ, ТЕОРИЯ ШЕСТИ РУКОПОЖАТИЙ, СОЦИАЛЬНЫЕ СЕТИ, ПОИСК В ГЛУБИНУ, ГРАФЫ
Выпускная квалификационная работа посвящена задаче поиска потенциально знакомых людей в социальной сети с помощью графовой аналитики.
Объект исследования: профиль человека в социальной сети Вконтакте.
Цель работы: разработать математическое, алгоритмическое и программное обеспечение для поиска потенциально знакомых людей по заданным критериям в социальной сети ВКонтакте на основе теории шести рукопожатий
Область применения результатов: пользователи социальной сети Вконтакте.
Для решения поставленной задачи используются методы поиска пути на графе.
В ходе работы проанализированы математические методы, виды графовых СУБД и эвристика шести рукопожатий, изложены основные принципы работы разработанного ПО.
Основным результатом данной работы является модель и методы с сопутствующим программным обеспечением для поиска людей в социальной сети Вконтакте. Данная модель протестирована на реальных данных пользователей социальных сетей.
В качестве инструментов для реализации были выбраны следующие технологии: язык программирования Python; язык программирования Сypher; VK API; библиотеки pandas, PyQt5, Graph Data Science Library
ВВЕДЕНИЕ 9
1 АНАЛИТИЧЕСКИЙ ОБЗОР 11
1.1 Базы данных NoSQL 11
1.1.1 Понятие графовой базы данных 12
1.1.2 Модели графовых баз данных 14
1.1.3 Графы свойств 15
1.1.4 Графы RDF 17
1.1.5 Как работают графовые БД 17
1.1.6 Достоинства графовых баз данных 18
1.2 Как работает графовая аналитика 20
1.3 Обзор нескольких СУБД 21
1.3.1 Neo4j 22
1.3.2 Microsoft Azure Cosmos DB 25
1.3.3 ArangoDB 26
1.3.4 Virtuoso 30
1.4 Теория шести рукопожатий 32
1.5 Интеллектуальный анализ с помощью теории графов 33
1.5.1 Поиск в ширину 33
1.5.2 Поиск в глубину 35
1.5.3 Краткий обзор двух алгоритмов 36
2 СПЕЦИАЛЬНАЯ ЧАСТЬ 38
2.1 Содержательная постановка задачи 38
2.2 Математическая постановка задачи 42
2.3 Концепт будущего ПО 43
2.4 Программная реализация 44
2.5. Примеры работы ПО 47
3. АНАЛИЗ РЕЗУЛЬТАТОВ 51
ЗАКЛЮЧЕНИЕ 52
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 53
ПРИЛОЖЕНИЕ А 55
1 Базы данных NoSQL // URL: https://db-engines.com/en/article/NoSQL (Дата обращения: 11.09.2021).
2 Что такое графовые базы данных // URL: https://www.oracle.com/ru/big-data/what-is-graph-database/ (Дата обращения: 11.09.2021).
3 Самые популярные графовые база данных // URL: https://www.c-sharpcorner.com/article/most-popular-graph-databases/ (Дата обращения: 20.09.2021).
4 Будущее графовых баз данных // URL: https://www.itworldcanada.com/blog/whats-in-the-future-for-graph-databases-ai-data-storage/438331 (Дата обращения: 01.11.2021).
5 Графовая СУБД Neo4j // URL: https://neo4j.com/ (Дата обращения: 12.11.2021).
6 Графовая СУБД Microsoft Azure DB // URL: https://azure.microsoft.com/ru-ru/services/cosmos-db/ (Дата обращения: 12.11.2021).
7 Графовая СУБД ArangoDB // URL: https://www.arangodb.com/graph-database/ (Дата обращения: 12.11.2021).
8 Графовая СУБД Virtuoso // URL: https://en.wikipedia.org/wiki/Virtuoso_Universal_Server (Дата обращения: 12.11.2021).
9 Графовая СУБД OrientDB // URL: https://en.wikipedia.org/wiki/OrientDB (Дата обращения: 12.11.2021);
10 Графовая СУБД OrientDB // URL: https://orientdb.org/ (Дата обращения: 12.11.2021).
11 Наиболее популярные графовые базы данных // URL: https://www.c-sharpcorner.com/article/most-popular-graph-databases/ (Дата обращения 15.11.2021).
12 Теория шести рукопожатий // URL: https://forallx.ru/posts/six-degrees-of-separation (Дата обращения 13.12.2021).
13 Задача о кратчайшем пути // URL: https://ru.wikipedia.org/wiki/Задача_о_кратчайшем (Дата обращения 13.12.2021).
14 Поиск в ширину// URL: https://ru.wikipedia.org/wiki/поиск_в_ширину (Дата обращения 13.12.2021).
