Механизм копирования

При изучении безмасштабных сетей механизм копирования — это процесс, посредством которого такая сеть может формироваться и расти посредством повторяющихся шагов, в которых узлы дублируются с мутациями из существующих узлов. Было изучено несколько вариантов. В общей модели копирования растущая сеть начинается с небольшого начального графа, и на каждом временном шаге добавляется новая вершина с заданным числом k новых исходящих ребер. В результате стохастического отбора соседи новой вершины либо выбираются случайным образом среди существующих вершин, либо случайно выбирается одна существующая вершина и k ее соседей «копируются» как заголовки новых ребер. ^[1]

Мотивация

Механизмы копирования для моделирования роста Всемирной паутины мотивированы следующей интуицией:

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

Это роста и предпочтительного прикрепления свойства сетей .

Описание

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

(I) С вероятностью $p$ , единственный параметр модели,новое ребро указывает на вас.

(II) С вероятностью $1-p$ ,новое ребро указывает на пункт назначения вашего (единственного) исходящего канала;новый узел достигает своего края путем копирования.

Второй процесс увеличивает вероятность получения узлами высокой степени новых входящих ребер. Фактически, поскольку u выбирается случайным образом, вероятность того, что веб-страница со степенью $k$ воляполучить новую гиперссылку пропорциональнос $(1-p)k$ , что указывает на то, что механизм копирования фактически представляет собойлинейная преимущественная привязанность. Кумар и др. докажите, что математическое ожидание входящего распределения степеней является $P(k_{in})=k^{-(2-p)/(1-p)}$ ,таким образом $P(k)$ следует степенному закону с показателем степени, который варьируется от 2 (для $p\rightarrow 0$ ) и $\infty$ (для $p\rightarrow 1$ ).

Выше представлена модель копирования с линейным ростом. Поскольку Интернет в настоящее время растет в геометрической прогрессии,существует модель копирования экспоненциального роста. На каждом шаге наступает новая эпоха вершин, размер которых постоянен.часть текущего графика. Каждая из этих вершин можетссылаются только на вершины из предыдущих эпох.

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

Неориентированные модели

Сети взаимодействия белков

Васкес предложил растущий граф, основанный на моделировании взаимодействий белков дупликацией. На каждом временном шаге прототип выбирается случайным образом. С вероятностью q копируются ребра прототипа. С вероятностью p создается ребро прототипа. ^[2]

Протеомные сети

Соул предложил растущий граф, инициализированный подложкой из 5 колец. На каждом временном шаге добавляется новый узел ипрототип выбирается случайным образом. Ребра прототипа копируются с вероятностью δ. Кроме того, случайные узлы подключаются к вновь введенному узлу с вероятностью α = β/N, где δ и β — заданные параметры в (0,1), а N — общее количество узлов на рассматриваемом временном шаге. (см. рис. 1). ^[3]

Направленные модели

Биологические сети

Миддендорф-Зив (МЗ) предложил растущий ориентированный граф, моделирующий динамику биологической сети. Прототип выбирается случайным образом и дублируется. У узла-прототипа или прародителя ребра обрезаны с вероятностью β, а ребра добавлены с вероятностью α<<β. На основе модели ненаправленной белковой сети Sole et al. ^[3]

WWW-сети и сети цитирования

Васкес предложил модель роста, основанную на рекурсивном механизме «копирования», продолжающемся до 2-го ближайшего соседа, 3-го ближайшего соседа и т. д. Авторы называют это механизмом «случайного блуждания». ^[4]

Растущая сеть с копированием (GNC)

Крапивский и Реднер предложили новую модель растущей сети, которая растет за счет добавления узлов по одному. Вновь введенный узел случайным образом выбирает целевой узел и связывается с ним, а также со всеми узлами-предками целевого узла (рис. 2). Если целевой узел является исходным корневым узлом, механизм копирования не создает никаких дополнительных ссылок. Если бы вновь введенный узел всегда выбирал корневой узел в качестве цели, был бы сгенерирован звездчатый граф. С другой стороны, если целевой узел всегда является самым последним в сети, все предыдущие узлы являются предками целевого узла, и механизм копирования даст полный граф. Соответственно, общее количество ссылок $L_{N}$ в сети из N узлов может варьироваться от N-1 (звездчатый граф) до N(N-1)/2 (полный граф). Обратите также внимание, что количество исходящих ссылок от каждого нового узла (исходящая степень) может варьироваться от 1 до текущего количества узлов. ^[5]

Примечания

^ Когиас, А. (2005), «Моделирование и имитация веб-графа: оценка модели копирования с экспоненциальным ростом», Международный журнал веб-инженерии и технологий , 2 (1): 29, doi : 10.1504/IJWET.2005.007463 .
^ А. Васкес, А. Фламмини, А. Маритан, А. Веспиньяни, Моделирование сетей взаимодействия белков, arXiv : cond-mat/0108043 .
^ Jump up to: ^а ^б Р. В. Соле, Р. Пастор-Саторрас, Э. Смит, Т. Б. Кеплер, Модель крупномасштабной эволюции протеома, arXiv : cond-mat/0207311 .
^ А. Васкес, Познание сети путем прогулки по ней: появление масштабирования, arXiv : cond-mat/0006132 .
^ Крапивский, ПЛ; Реднер, С. (17 марта 2005 г.). «Рост сети путем копирования». Физический обзор E . 71 (3). Американское физическое общество (APS): 036118. arXiv : cond-mat/0410379 . дои : 10.1103/physreve.71.036118 . ISSN 1539-3755 .

Ссылки

Кляйнберг, Дж. М., Р. Кумар, П. Рагхаван, С. Раджагопалан и А. Томкинс, 1999, Материалы Международной конференции по комбинаторике и информатике.
Кумар Р., П. Рагхаван, С. Раджагопалан, Д. Сивакумар, А.С. Томкинс и Э. Упфал , 2000a, Труды 19-го симпозиума по принципам систем баз данных.
Кумар Р., П. Рагхаван, С. Раджагопалан, Д. Сивакумар, А.С. Томкинс и Э. Упфал , 2000b, Материалы 41-го симпозиума IEEE по основам компьютерных наук.

[kogias-1] Когиас, А. (2005), «Моделирование и имитация веб-графа: оценка модели копирования с экспоненциальным ростом», Международный журнал веб-инженерии и технологий , 2 (1): 29, doi : 10.1504/IJWET.2005.007463 .

[Vazquez-2] А. Васкес, А. Фламмини, А. Маритан, А. Веспиньяни, Моделирование сетей взаимодействия белков, arXiv : cond-mat/0108043 .

[Sole-3] Jump up to: ^а ^б Р. В. Соле, Р. Пастор-Саторрас, Э. Смит, Т. Б. Кеплер, Модель крупномасштабной эволюции протеома, arXiv : cond-mat/0207311 .

[VazquezII-4] А. Васкес, Познание сети путем прогулки по ней: появление масштабирования, arXiv : cond-mat/0006132 .

[Krapivsky-5] Крапивский, ПЛ; Реднер, С. (17 марта 2005 г.). «Рост сети путем копирования». Физический обзор E . 71 (3). Американское физическое общество (APS): 036118. arXiv : cond-mat/0410379 . дои : 10.1103/physreve.71.036118 . ISSN 1539-3755 .

[1]

[2]

[3]

[4]

[5]