рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Цели и задачи этой работы

Работа сделанна в 2006 году

Цели и задачи этой работы - Курсовая Работа, раздел Связь, - 2006 год - Моделирование Web-графа. Цели И Задачи Этой Работы. В Данной Работе Описаны Наиболее Актуальные...

Цели и задачи этой работы.

В данной работе описаны наиболее актуальные модели web-графа, позволяющие получить компактные наборы данных, максимально полно отражающие структуру и особенности web. Эти данные делают доступными эксперименты с алгоритмами и симуляциями, использующими в своей работе ссылочную структуру сети от PageRank и выделения кибер-собществ до моделирования распространения вирусов в реальных сетях. В среде Delphi 7 мною была реализована Многослойная модель, использующая для формирования слоев гибридную, копирующую и развивающуюся модели.

Модели Web-графа. Модель ACL. Модель ACL зависит от 2-х параметров и. Для реализации экспоненциального закона распределения степеней, положим, что мы имеем в графе y вершин степени x 0 Вершины степени 0 являются изолированными и обычно не рассматриваются, т.к. на практике они не встречаются где x и y удовлетворяют следующему равенству Таким образом, мы имеем , По сути это логарифм числа вершин степени 1, а - двойная логарифмическая оценка убывания числа вершин заданной степени.

Из формулы видно, что y действительное число. На практике используют. Другим ограничением является то, что сумма степеней вершин должна быть четной. Если это не так, то можно добавить к графу вершину степени 1, но далее будем полагать, что в графе нет изолированных вершин. Для данной модели характерны следующие свойства Максимальная степень равна, учитывая что Число вершин в модели может быть вычислено следующим образом где - функция Реймана-Зетта. Число дуг в модели может быть вычислено следующим образом Для создания графа необходимо поступить следующим образом 1. Выбрать параметры и . рекомендуется брать близким к 1. 2. Вычислить максимальную степень вершины графа 3. По вышеописанным свойствам модели вычислить число вершин и дуг, из которых состоит граф. 4. Сформировать набор L, состоящий из degvi копий вершин vi, i 1 n. 5. Выбрать случайное соответствие элементов в L. 6. Для всех пар вершин u и v графа, число дуг соединяющих эти вершины будет равно числу соответствий всех копий вершины u копиям вершины v набора L. Результатом модели будет мультиграф, который может содержать петли.

Прообразом для модели служил т.н. call-граф граф междугородних телефонных звонков, произведенных за некоторый длительный промежуток времени например, сутки.

Для генерации web-графа эта модель не используется, но оказала большую помощь в его изучении этой проблемы. Модель Развивающейся сети. Модель представляет собой итерационный процесс, в котором на каждой итерации к web-графу добавляется по одной вершине.

Пусть функция indegreev возвращает число входящих в вершину v дуг. Тогда новая вершина w соединяется с вершинами vk графа с вероятностью пропорциональной indegreevk преференциальное добавление. Для реализации модели, используется массив Ik хранящий значения indegreevk 1. Обозначим число уже добавленных к web-графу вершин g. Пусть I сумма значений indegree всех вершин количество вершин. Все добавляемые вершины получают фиктивное значение indegree равное 1, что позволяет им быть выбранным в качестве конечной вершины дуги. Поэтому к I и было добавлено g. Добавим к web-графу вершину w. Выберем случайное число r от 1 до I. Затем найдем вершину vk с наименьшим k, для которого выполняется следующее Вершина vk выбирается конечной вершиной новой дуги, а значение Ik увеличивается на 1. Начальной вершиной дуги является добавленная вершина w. При генерации массивных web-графов возникают две трудности В оперативной памяти должен хранится массив Ij, что затруднительно при большом числе вершин.

Процесс поиска подходящей конечной вершины vk существенно замедляется. Для решения вышеописанных проблем используется следующее усовершенствование алгоритма В оперативной памяти хранится вспомогательный массив S из элементов.

Каждый элемент массива S хранит сумму значений indegree для вершин. Т.о и т.д. Множество из вершин назовем блоком. Алгоритм генерации web-графа принимает следующий вид Фаза 1. В оперативной памяти хранятся картежи tk, описывающие дуги, для которых известна начальная вершина, но не найдена конечная.

Каждый картеж хранит номер блока, в котором находится конечная вершина дуги. Пусть с добавляемая вершина, она и будет являться начальной для новой дуги. Выберем случайное число r от 1 до I, где, а g с 1. Затем необходимо определить блок, в котором находится конечная вершина. Для этого найдем наименьшее k, для которого выполняется следующее В память записывается картеж t номер дуги номер блока относительная позиция внутри блока, где за относительную позицию внутри блока принимается разность числа r и суммы значений indegree всех блоков, предшествующих найденному.

Добавление вершин и генерация картежей продолжается до заполнения заданного объема памяти. Фаза 2. Создание дуг и запись их во внешнюю память. Для каждого блока ищутся все картежи, которые ссылаются на один блок. Затем этот блок загружается в оперативную память и в нем ищется конечные вершины описанных картежами дуг. Полученные дуги пишутся в буфер, выгружаемый во внешнюю память по мере заполнения, а значение indegree их конечных вершин увеличивается.

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

– Конец работы –

Эта тема принадлежит разделу:

Моделирование Web-графа.

Под Web-графом понимается орграф, вершинами которого являются документы в основном статические html страницы сети Интернет, а дугами гипертекстовые… Подавляющее большинство запросов пользователей содержат не более 3-5 слов, и… Естественно, пользователю предоставляются ссылки на первые 10-15 самых лучших страниц.Ранжирование результатов поиска…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Цели и задачи этой работы

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Этапы изучения web-графа и его моделирование
Этапы изучения web-графа и его моделирование. Первой моделью web-графа являлась модель Erdцs-Renyi 3. Конечные вершины для исходящих дуг в этой модели выбираются случайным образом из всех вершин гр

Копирующая модель сети
Копирующая модель сети. На каждой итерации алгоритма к web-графу добавляется по одной вершине. Для каждой новой вершины v выбирается вершина-прототип p. Для всех исходящих из v дуг, с вероятностью

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги