📄Работа №128032
Тема: Методы обработки, прогнозирования и оценки структуры сложных сетей. Анализ существующих и разработка новых на примере веб-графов
Тип работы
Бакалаврская работа
Предмет
Программирование
Объем:
29 листов
Год:
2021
Просмотров:
73
4750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 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
Постановка задачи 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): выбрать подмножество вершин или рёбер исходного графа. Самым большим преимуществом методов выборки является их эффективность выполнения, так что процедура преобразования не займет больше времени, чем простое вычисление на исходном графе.
В данной работе будут рассмотрены основные характеристики и существующие методы для обработки, прогнозирования и оценки структуры сложных сетей. Основной задачей будет являться выявление новых зависимостей и способов для решения проблемы анализа веб- графов в сети.
В настоящее время размеры сетевых структур могут достигать несколько миллионов элементов, и тогда возникает задача об оптимальном анализе свойств сети в условиях ограниченности времени и вычислительных мощностей. Существует множество известных алгоритмов для вычисления мер сети ( кратчайших путей, центральности, плотности, степени узлов, коэффициентов кластеризации и т.д.). Но некоторые из них становятся непрактичными для больших графов. Таким образом, встаёт вопрос возможно ли получить репрезентативный подграф, меньший по размеру, но с сохранением свойств изначального графа? Если это так, то запуск алгоритма на преобразованном графе будет иметь тот же эффект, что и на исходном. Кроме того, мы можем оценить характеристики исходного графа, используя только подграф.
Для того, чтобы уменьшить размер графа, и одновременно сохранить его свойства, существует множество сложных подходов. Например, можно сформулировать задачу математического программирования, чтобы минимизировать расстояние между исходным и выборочным графом. Этот подход, будучи очень точным, может быть чрезвычайно дорогостоящим. Например, решение задачи уменьшения размера графа таким образом, чтобы разрезы сохранялись, является NP-трудной [2]. Другим недостатком этих подходов является то, что они обычно требуют полной информации ( всего графа ). Это делает его бесполезным в некоторых сценариях, например в децентрализованных социальных сетях (DSN), где мы можем получить только часть данных и предположить, что это выборка (по некоторому распределению) из исходного графа.
Простой, но эффективный способ преобразования графа заключается в построении выборки (Graph Sampling): выбрать подмножество вершин или рёбер исходного графа. Самым большим преимуществом методов выборки является их эффективность выполнения, так что процедура преобразования не займет больше времени, чем простое вычисление на исходном графе.
В данной работе будут рассмотрены основные характеристики и существующие методы для обработки, прогнозирования и оценки структуры сложных сетей. Основной задачей будет являться выявление новых зависимостей и способов для решения проблемы анализа веб- графов в сети.
✅ Заключение
В выпускной квалификационной работе изучены и проанализированы существующие методы и алгоритмы для обработки, прогнозирования и оценки структуры сложных веб-графов, а также предложен собственный метод для извлечения эффективных выборок графа. В том числе получены следующие научные результаты:
1. Изучены существующие статьи и описанные в них методы и подходы.
2. Реализовано построение веб-графов, а также методов, предложенных в изученных статьях.
3. Предложен свой метод к извлечению эффективных выборок.
4. Предложен подход к сравнению методов.
5. Получен результат эксперимента сравнения полученных в ходе работы методы на основании предложенного подхода.
Таким образом были выполнены все поставленные задачи и достигнута цель работы. Результаты данной работы могут быть применимы, например, в анализе социальных сетей(ЗМЛ) для моделирования распространения сети, анализа характерных признаков и поведения элементов графа, а также прогнозирования связей в веб-графах.
1. Изучены существующие статьи и описанные в них методы и подходы.
2. Реализовано построение веб-графов, а также методов, предложенных в изученных статьях.
3. Предложен свой метод к извлечению эффективных выборок.
4. Предложен подход к сравнению методов.
5. Получен результат эксперимента сравнения полученных в ходе работы методы на основании предложенного подхода.
Таким образом были выполнены все поставленные задачи и достигнута цель работы. Результаты данной работы могут быть применимы, например, в анализе социальных сетей(ЗМЛ) для моделирования распространения сети, анализа характерных признаков и поведения элементов графа, а также прогнозирования связей в веб-графах.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.