В данной работе исследуется рассматривается применение алгоритмов, основанных на векторных представлениях вершин, в таких задачах анализа графов таких, как классификация вершин и прогнозирование ребра. В первой главе дано описание задачи нахождения векторных представлений вершин графов. Во второй главе рассмотрены некоторые существующие методы решения данной задачи. В третьей главе описана программная реализация выбранных методов. В четвертой главе протестировано применение выбранных методов к задачам классификации вершин и прогнозирования ребра в графе.

This paper describes an application of graph embedding based algorithms in networks analysis tasks such as node classification and link prediction. The first chapter describes a graph embedding problem. The second chapter provides an overview of graph embedding methods. The third chapter describes an implementation of selected methods. The fourth chapter presents experimental studies of using selected graph embedding methods in node classification and link prediction problems.

• ВВЕДЕНИЕ
• ГЛАВА 1. ОБЗОР ЗАДАЧИ НАХОЖДЕНИЯ ВЕКТОРНЫХ ПРЕДСТАВЛЕНИЙ ВЕРШИН ГРАФОВ
  • 1.1. Неформальная постановка задачи
  • 1.2. Формальная постановка задачи
  • 1.3. Сложности, возникающие при решении задачи
• ГЛАВА 2. ОБЗОР И СРАВНИТЕЛЬНЫЙ АНАЛИЗ СУЩЕСТВУЮЩИХ АЛГОРИТМОВ ПОСТРОЕНИЯ ВЕКТОРНЫХ ПРЕДСТАВЛЕНИЙ ВЕРШИН ГРАФОВ
  • 2.1. Методы, основанные на факторизации матриц
    • 2.1.1. Laplacian Eigenmaps
    • 2.1.2. Graph Factorization
    • 2.1.3. GraRep и HOPE
  • 2.2. Методы, основанные на случайных блужданиях
    • 2.2.2. DeepWalk
    • 2.2.3. Node2vec
  • 2.3. Методы, основанные на глубоком обучении
    • 2.3.1. SDNE
  • 2.4. Сравнительный анализ методов
• ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
  • 3.1. Используемые программные средства
  • 3.2. Структура программы
    • 3.2.1. Node2Vec
    • 3.2.2. SDNE
  • 3.3. Входные данные
  • 3.4. Тестирование
• ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РЕАЛИЗОВАННЫХ МЕТОДОВ В ЗАДАЧАХ КЛАССИФИКАЦИИ ВЕРШИН И ПРОГНОЗИРОВАНИЯ ПОЯВЛЕНИЯ РЕБРА В ГРАФЕ
  • 4.1. Задача классификации вершин графа
    • 4.1.1. Постановка задачи
    • 4.1.2. Описание входных данных
    • 4.1.3. Описание алгоритма
    • 4.1.4. Метрики качества
    • 4.1.5. Экспериментальное тестирование
  • 4.2. Задача прогнозирования появления ребра в графе
    • 4.2.1. Постановка задачи
    • 4.2.2. Описание входных данных
    • 4.2.3. Описание алгоритма
    • 4.2.4. Метрики качества
    • 4.2.5. Экспериментальное тестирование
  • 4.3. Исследование зависимости качества моделей от размерности векторного пространства
    • ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• Приложение 1
• Код программы. Основные классы
• Приложение 2
• Классификатор
• Приложение 3
• Код для расчета расстояний
• Приложение 4
• Реализация алгоритмов прогнозирования ребра в графе, основанных на признаках пар вершин
• Приложение 5
• Реализация алгоритмов прогнозирования ребра в графе, основанных на векторных представлениях вершин
• Приложение 6
• Графики зависимости метрик от размерности векторного пространства