Цели и задачи этой работы.
В данной работе описаны наиболее актуальные модели 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 их конечных вершин увеличивается.
Фаза завершает работу, когда для всех картежей будут сгенерированны дуги. На практике часто используют многоуровневую систему блоков и специальные структуры, ускоряющие поиск вершины внутри них.