Введение 3
Постановка задачи 5
1. Описание предметной области 6
1.1. Актуальность работы 6
1.2. Обзор литературы 7
2. Известные алгоритмы 8
2.1. Методы случайной выборки по вершинам 8
2.2. Методы случайной выборки по рёбрам 10
2.3. Аналитические методы 12
2.3.1. Метод “Снежного кома” 12
2.3.2. Метод случайных блужданий 13
2.3.3. Алгоритм Метрополиса-Хастингса 17
2.3.4. Алгоритм Метрополиса-Хастингса с ограничением 19
2.3.5. Forest Fire 20
3. Эксперимент 22
3.1. Модификация метода случайного обхода 22
3.2. Описание эксперимента 23
3.3. Результаты эксперимента 24
Заключение 27
Список литературы 28
Исследование свойств больших сетей является на данный момент актуальной задачей не только в мире математики, но и в других областях науки.
В настоящее время размеры сетевых структур могут достигать несколько миллионов элементов, и тогда возникает задача об оптимальном анализе свойств сети в условиях ограниченности времени и вычислительных мощностей. Существует множество известных алгоритмов для вычисления мер сети ( кратчайших путей, центральности, плотности, степени узлов, коэффициентов кластеризации и т.д.). Но некоторые из них становятся непрактичными для больших графов. Таким образом, встаёт вопрос возможно ли получить репрезентативный подграф, меньший по размеру, но с сохранением свойств изначального графа? Если это так, то запуск алгоритма на преобразованном графе будет иметь тот же эффект, что и на исходном. Кроме того, мы можем оценить характеристики исходного графа, используя только подграф.
Для того, чтобы уменьшить размер графа, и одновременно сохранить его свойства, существует множество сложных подходов. Например, можно сформулировать задачу математического программирования, чтобы минимизировать расстояние между исходным и выборочным графом. Этот подход, будучи очень точным, может быть чрезвычайно дорогостоящим. Например, решение задачи уменьшения размера графа таким образом, чтобы разрезы сохранялись, является NP-трудной [2]. Другим недостатком этих подходов является то, что они обычно требуют полной информации ( всего графа ). Это делает его бесполезным в некоторых сценариях, например в децентрализованных социальных сетях (DSN), где мы можем получить только часть данных и предположить, что это выборка (по некоторому распределению) из исходного графа.
Простой, но эффективный способ преобразования графа заключается в построении выборки (Graph Sampling): выбрать подмножество вершин или рёбер исходного графа. Самым большим преимуществом методов выборки является их эффективность выполнения, так что процедура преобразования не займет больше времени, чем простое вычисление на исходном графе.
В данной работе будут рассмотрены основные характеристики и существующие методы для обработки, прогнозирования и оценки структуры сложных сетей. Основной задачей будет являться выявление новых зависимостей и способов для решения проблемы анализа веб- графов в сети.
В выпускной квалификационной работе изучены и проанализированы существующие методы и алгоритмы для обработки, прогнозирования и оценки структуры сложных веб-графов, а также предложен собственный метод для извлечения эффективных выборок графа. В том числе получены следующие научные результаты:
1. Изучены существующие статьи и описанные в них методы и подходы.
2. Реализовано построение веб-графов, а также методов, предложенных в изученных статьях.
3. Предложен свой метод к извлечению эффективных выборок.
4. Предложен подход к сравнению методов.
5. Получен результат эксперимента сравнения полученных в ходе работы методы на основании предложенного подхода.
Таким образом были выполнены все поставленные задачи и достигнута цель работы. Результаты данной работы могут быть применимы, например, в анализе социальных сетей(ЗМЛ) для моделирования распространения сети, анализа характерных признаков и поведения элементов графа, а также прогнозирования связей в веб-графах.
