Копирующая модель сети

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

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

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

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

Где k функция, зависящая от размера графа. Модель Растущей сети. Модель была предложена в 2002г. D.M. Pennock и G.W. Flake. В своей работе они исследовали структуры web-графа, образованные тематическими наборами страниц. Их исследования показали, что распределение значений indegree в этих множествах сильно отличаются от экспоненциального. Распределение числа ссылающихся страниц в подобных группах более всего походит на унимодальное с экспоненциальным хвостом. Авторы выдвинули гипотезу, что экспоненциальный закон распределения является скорее исключением, чем правилом.

Для реализации web-графа на уровне групп страниц с подобным распределением и была разработана модель Растущей сети. Пусть мы имеем некий начальный граф, содержащий m0 вершин. На каждой итерации t к нему будет добавляться по одной вершине и m дуг. В модели развивающейся сети все m дуг соединяют новую вершину со старыми преференциально Вероятность Пki того, что дуга соединит вершину i пропорциональна ki, где ki текущее число дуг, инцидентных i. В этой модели у всех вершин есть некая базовая вероятность быть соединенной с новой вершиной единообразное добавление.

Поэтому, вероятность соединения i-той вершины с новой, можно выразить следующей формулой где m0 t число вершин, а 2mt число дуг графа на t-й итерации. При преференциальном добавлении, страницы на которые указывают множество ссылок имеют большее предпочтение при добавлении дуги. При единообразном все страницы равноценны.

Баланс между этими принципами дает более адекватную модель графа, т.к. web-дизайнеры при создании ссылок руководствуются 2 принципами Ссылки ставятся на наиболее популярные страницы. Ссылки ставятся на наиболее интересные автору страницы, без учета их популярности. При устремлении параметра к 1 или m к 1 закон распределения числа входящих ссылок вновь станет близок к экспоненциальному. Многослойная модель. Как и все вышеописанные модели, многослойная модель является итерационной. В этой модели web-граф рассматривается как объединение нескольких регионов, называемых слоями.

На каждой итерации t к графу добавляется вершина x, и ей присваиваются фиксированное число l регионов и d дуг, соединяющих x с вершинами графа. рис. Многослойная модель графа. Пусть Xit число вершин принадлежащих i-му слою на t-ой итерации. Lx набор слоев, связанных с вершиной x. Для связывания вершины x со слоями, в цикле l раз необходимо выполнить следующую операцию, где i слой, выбираемый из множества LLx с вероятностью, пропорциональной Xit с некоторым нормализующим фактором.

При генерации дуг при преференциальном добавлении рассматриваются только вершины одного слоя. Это позволяет генерировать слои независимо друг от друга. В связи с этим в многослойной модели выделяют 2 процесса поведение вне слоя extra-layer behavior и поведение внутри слоя intra-layer behavior. Подобная независимость позволяет использовать для формирования слоев различные модели Развивающейся сети, Копирующую модель, модель Роста сети и т.д При этом часть слоев может генерироваться одной моделью, а часть другой.

В данной работе мы рассмотрим т.н. гибридную модель формирования слоев. Она была предложена авторами многослойной модели 16 и обладает большой устойчивостью при вариации параметров. Гибридная модель является сочетанием Развивающейся и Линейной копирующей моделей. Между l слоями равномерно распределяются d дуг. Пусть с dx и - параметр копирования. В каждом слое i, с которым связана вершина x, она будет иметь с или с 1 исходящую дугу, к которой необходимо подобрать конечную вершину. Обозначим за множество из Xit вершин слоя i. Т.о. слой i будет состоять из вершин множества и дуг между ними, созданных за t-1 итерацию.

Выберем из прототип p. Соединим x с помощью с дуг с вершинами множества следующим образом Для с вероятностью l-я дуга соединяется с конечной вершиной l-й дуги прототипа p. Иначе, концом l-й дуги выбирается одна из еще не связанных с x вершин множества, с вероятностью, пропорциональной их нормализованному значению indegree 1. Если прототип имеет лишь с исходящих дуг, а необходимо создать c1, то она берется вторым способом.