Копирование сетевых моделей

Модели копирующей сети — это модели генерации сети, которые используют механизм копирования для формирования сети путем многократного дублирования и изменения существующих узлов сети. Такая сетевая модель была впервые предложена в 1999 году для объяснения сети связей между веб-страницами, но с тех пор она также использовалась для моделирования биологических сетей и сетей цитирования.

Происхождение

В 1999 году Джон Кляйнберг и трое соавторов опубликовали статью в журнале «Вычисления и комбинаторика», в которой пытались построить сетевую модель, объясняющую закономерности, обнаруженные при анализе Всемирной паутины . Интуиция модели заключалась в том, что когда пользователь решает создать и опубликовать свою собственную веб-страницу, он встречает в сети список ссылок на интересующую его тему и в конечном итоге копирует эту коллекцию или множество таких коллекций на свою собственную веб-страницу. . Это создает новый узел в сети — новую страницу — и копирует каким-то образом ребра из уже существующих узлов.

Они обрисовали модель в общих чертах, но не стали подробно анализировать предсказания точной модели, в основном из-за вычислительных ограничений, но предположили, что случайное копирование узлов является простым, достойным модели механизмом для создания зипфианских распределительных сетей. ^[1]

С тех пор эта статья была процитирована более 1200 раз, что сопоставимо со значительными статьями, внесшими вклад в сетевую науку, такими как статья, описывающая модель Эрдеша-Реньи (около 8300), и включает известные книги по сетевой науке, такие как работы Марка Ньюмана. ^[2]

Описание

Общая модель

Чтобы понять общую модель, возьмем базовую модель роста сети, которая характеризуется четырьмя случайными процессами. Процессы создания $C_{v}$ и $C_{e}$ для процессов создания и удаления узлов и ребер $D_{v}$ и $D_{e}$ для удаления узлов и ребер.

Возьмем дискретный временной интервал, где $C_{v}$ состоит из простого создания на каждом шаге узла с вероятностью $a_{c}(t)$ и аналогично $D_{v}$ удаляет узел с вероятностью a _d ( t ). Следовательно, это также означает $D_{e}$ включает в себя удаление всех ребер, принадлежавших удаленному узлу.

$C_{e}$ вот в чем суть модели копирования. В оригинальной статье они характеризуют $C_{e}$ с распределением вероятностей, определяющим узел $v$ добавить ребра из и количество ребер $k$ это будет добавлено. И с вероятностью $\beta$ что k ребер либо копируются, либо добавляются случайным образом. С вероятностью $\beta$ , все $k$ ребра из v нарисованы к узлам, выбранным независимо и равномерно случайным образом. С вероятностью $(1-\beta )$ , k ребер копируются из случайно выбранного узла $u$ . Это означает, что $k$ соседи $u$ стать соседями $v$ . Если $u$ имеет степень выше, чем $k$ , $k$ ребра выбираются случайным образом, и если они имеют меньшую степень $l<k$ , следующий узел выбирается случайным образом и $k-l$ копируются его края и так далее.

Можно показать, что такая сеть дает степенное распределение степеней с показателем степени $\gamma =$ ${\frac {2-a}{1-a}}$ где $a$ — это отношение количества случайно добавленных ребер к числу скопированных ребер. ^[3] Таким образом, при соотношении от нуля до 0,5 распределение по степенному закону с показателем степени $2<\gamma <3$ может быть достигнуто. Также обратите внимание, что когда отношение приближается к 1, показатель степени стремится к бесконечности.

Модель GNC

Другая простая модель, предложенная для объяснения наблюдения о том, что средний уровень узла растет с размером системы, добавляет узлы по одному. Новый узел случайным образом выбирает узел из существующих и помимо копирования всех ребер, назначенных целевому узлу при его введении, соединяется с самим узлом, тем самым несколько увеличивая среднюю степень. Например, если целевой узел является самым первым в сети, дополнительные ребра не добавляются, а только то, что находится между первым узлом и последним. Возьмем два крайних случая. Если новый узел всегда соединяется с первым узлом, модель формирует звездчатый граф , где каждый узел имеет степень один, но первый узел имеет возрастающее количество степеней. При этом средняя степень увеличивается на ${\frac {1}{N}}$ с каждым дополнительным узлом, где $N$ это количество узлов. В другом крайнем случае, когда новые узлы соединяются с добавленными до них, формируется полный граф, и средняя степень увеличивается на 1 с каждым новым узлом. ^[4]

Ходячая модель

Модель копирования, представляющая собой смесь этих двух моделей, была предложена Васкесом. В этой модели, когда добавляется новый узел, он соединяется с одним случайно выбранным узлом, который уже присутствует в сети, и с каждым из его соседей с $p$ возможность. Итак, с $p=0$ этот граф создает цепочку и $p=1$ создает полный график. В зависимости от $p$ этот график может дать ряд степенных распределений степеней с определенными ограничениями, которые хорошо характеризуют сети реального мира. ^[5]

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

Существует значительный интерес к моделированию биологических сетей, таких как сети взаимодействия белков и сети генетической регуляции, с использованием моделей копирующих сетей. Гены, содержащие информацию о том, как узел в сети должен взаимодействовать с другими, имеют тенденцию дублироваться в ходе эволюции, дублируя тем самым ребра, которые присутствовали в сети. Кроме того, сети предпочтительного прикрепления не могут на самом деле хорошо моделировать биологические сети как потому, что они неправдоподобны, так и потому, что ряд биологических сетей имеют степенное распределение степеней с показателем степени. $\gamma <2$ который не производится такими преференциальными сетевыми моделями.

Возьмем процесс дублирования узлов, в котором изначально каждый узел имеет равную вероятность дублирования за один временной шаг. Однако на вероятность дублирования влияет история предыдущих дублирований, и дублируются не все ребра, а только случайно выбранное их подмножество. Такая модель частичного дублирования может давать степенные распределения с показателями степени. $\gamma <2$ , что соответствует распределению степеней ряда биологических сетей независимо от исходного графа. ^[6]

Примечания

^ Кляйнберг, Джон (1999), «Сеть как график: измерения, модели и методы», Вычисление и комбинаторика : 1–17.
^ Ньюман, Марк (2003), «Структура и функции сложных сетей», SIAM Review , 45 (2): 167–256, arXiv : cond-mat/0303516 , Bibcode : 2003SIAMR..45..167N , doi : 10.1137 /S003614450342480 , S2CID 221278130
^ Кумар, Рави (2000), «Стохастические модели веб-графа», « Основы информатики » .
^ Крапивский Павел Л; Реднер, Сидни (2005), «Рост сети путем копирования», Physical Review , 71 (3): 036118, arXiv : cond-mat/0410379 , Bibcode : 2005PhRvE..71c6118K , doi : 10.1103/PhysRevE.71.036118 , PMID 15 903504
^ Васкес, Алексей Л. (2000), «Познание сети путем прогулки по ней: появление масштабирования», arXiv : cond-mat/0006132
^ Чунг, Фан (2003), «Модели дублирования для биологических сетей», Журнал вычислительной биологии , 10 (5): 677–687, arXiv : cond-mat/0209008 , doi : 10.1089/106652703322539024 , PMID 14633392 , S2CID 7592982 .

[klein-1] Кляйнберг, Джон (1999), «Сеть как график: измерения, модели и методы», Вычисление и комбинаторика : 1–17.

[newman-2] Ньюман, Марк (2003), «Структура и функции сложных сетей», SIAM Review , 45 (2): 167–256, arXiv : cond-mat/0303516 , Bibcode : 2003SIAMR..45..167N , doi : 10.1137 /S003614450342480 , S2CID 221278130

[kumar-3] Кумар, Рави (2000), «Стохастические модели веб-графа», « Основы информатики » .

[krapivsky-4] Крапивский Павел Л; Реднер, Сидни (2005), «Рост сети путем копирования», Physical Review , 71 (3): 036118, arXiv : cond-mat/0410379 , Bibcode : 2005PhRvE..71c6118K , doi : 10.1103/PhysRevE.71.036118 , PMID 15 903504

[alexei-5] Васкес, Алексей Л. (2000), «Познание сети путем прогулки по ней: появление масштабирования», arXiv : cond-mat/0006132

[bio-6] Чунг, Фан (2003), «Модели дублирования для биологических сетей», Журнал вычислительной биологии , 10 (5): 677–687, arXiv : cond-mat/0209008 , doi : 10.1089/106652703322539024 , PMID 14633392 , S2CID 7592982 .

[1]

[2]

[3]

[4]

[5]

[6]