Модель Прайса

Модель Прайса (названная в честь физика Дерека Дж. де Солла Прайса ) — это математическая модель роста сетей цитирования . Это была первая модель, обобщившая модель Саймона. для использования в сетях, особенно в растущих сетях. Модель Прайса принадлежит к более широкому классу моделей роста сетей (вместе с моделью Барабаши-Альберта ), основная цель которых — объяснить возникновение сетей с сильно искаженным распределением степеней. Модель подхватила идеи модели Саймона, отражающей концепцию « богатые становятся еще богаче» , также известную как эффект Мэтью . Прайс взял в качестве примера сеть цитирований между научными статьями и выразил ее свойства. Его идея заключалась в том, что способ, которым старая вершина (существующая статья) получает новые ребра (новые цитаты), должен быть пропорционален количеству существующих ребер (существующих цитат), которые уже есть в вершине. Это называлось кумулятивным преимуществом , теперь также известным как преференциальная привязанность . Работа Прайса также важна тем, что она предоставила первый известный пример безмасштабной сети (хотя этот термин был введен позже). Его идеи использовались для описания многих реальных сетей, таких как Интернет .

Модель

Основы

Рассмотрим ориентированный граф с n узлами. Позволять $p_{k}$ обозначим долю узлов степени k такую, что $\sum _{k}{p_{k}}=1$. Каждый новый узел имеет заданную исходную степень (а именно те статьи, которые он цитирует) и в конечном итоге фиксируется. Это не означает, что исходящие степени не могут меняться в разных узлах, просто мы предполагаем, что средняя исходящая степень m фиксирована с течением времени. Ясно, что $\sum _{k}{kp_{k}}=m$, следовательно, m не ограничивается целыми числами. Самая тривиальная форма предпочтительного присоединения означает, что новый узел соединяется с существующим узлом пропорционально его степеням. Другими словами, новая статья цитирует существующую статью пропорционально ее степени. Предостережение от такой идеи заключается в том, что ни одна новая статья не цитируется, когда она присоединяется к сети, поэтому вероятность ее цитирования в будущем будет равна нулю (что обязательно происходит не так). Чтобы преодолеть эту проблему, Прайс предложил, чтобы привязанность была пропорциональна некоторым $k+k_{0}$ с $k_{0}$ постоянный. В общем $k_{0}$ может быть произвольным, однако Прайс предлагает $k_{0}=1$, таким образом, первоначальная цитата связана с самой статьей (поэтому коэффициент пропорциональности теперь равен k + 1 вместо k ). Вероятность соединения нового ребра с любым узлом степени k равна

${\frac {(k+1)p_{k}}{\sum _{k}(k+1)p_{k}}}={\frac {(k+1)p_{k}}{m+1}}$

Эволюция сети

Следующий вопрос — чистое изменение количества узлов степени k при добавлении в сеть новых узлов. Естественно, это число уменьшается, поскольку некоторые узлы k -степени имеют новые ребра и, следовательно, становятся узлами ( k + 1)-степени; но, с другой стороны, это число также увеличивается, поскольку некоторые узлы ( k - 1)-степени могут получить новые ребра, становясь узлами k- степени. Чтобы формально выразить это чистое изменение, обозначим долю узлов k -степени в сети из n вершин с $p_{k,n}$:

$(n+1)p_{k,n+1}-np_{k,n}=[kp_{k-1,n}-(k+1)p_{k,n}]{\frac {m}{m+1}}{\text{ for }}k\geq 1,$

и

$(n+1)p_{0,n+1}-np_{0,n}=1-p_{0,n}{\frac {m}{m+1}}{\text{ for }}k=0.$

Чтобы получить стационарное решение для $p_{k,n+1}=p_{k,n}=p_{k}$, сначала выразим $p_{k}$ используя известный метод главных уравнений , т.к.

$p_{k}={\begin{cases}[kp_{k-1}-(k+1)p_{k}]{\frac {m}{m+1}}&{\text{for }}k\geq 1\\1-p_{0}{\frac {m}{m+1}}&{\text{for }}k=0\end{cases}}$

После некоторых манипуляций приведенное выше выражение превращается в

$p_{0}={\frac {m+1}{2m+1}}$

и

$p_{k}={\frac {k!}{(k+2+1/m)\cdots (3+1/m)}}p_{0}=(1+1/m)\mathbf {B} (k+1,2+1/m),$

с $\mathbf {B} (a,b)$ являющаяся бета-функцией . Как следствие, $p_{k}\sim k^{-(2+1/m)}$. Это то же самое, что сказать, что $p_{k}$ следует степенному закону распределения с показателем $\alpha =2+1/m$. Обычно при этом показатель степени находится между 2 и 3, что характерно для многих реальных сетей. Прайс протестировал свою модель, сравнив ее с данными сети цитирования, и пришел к выводу, что полученное m позволяет получить достаточно хорошее степенное распределение .

Обобщение

Несложно обобщить полученные выше результаты на случай, когда $k_{0}\neq 1$. Основные расчеты показывают, что

$p_{k}={\frac {m+k_{0}}{m(k_{0}+1)+k_{0}}}{\frac {\mathbf {B} (k+k_{0},2+k_{0}/m)}{\mathbf {B} (k_{0},2+k_{0}/m)}},$

что еще раз приводит к степенному закону распределения $p_{k}$ с тем же показателем $\alpha =2+k_{0}/m$ для больших k и фиксированных $k_{0}$.

Характеристики

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

Например, в ориентированном ациклическом графе как самые длинные , так и кратчайшие пути четко определены . В модели цены длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети масштабируется как $\ln(n)$

Примечания

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

Источники

• Ньюман, МЭД (2003). «Структура и функции сложных сетей». Обзор СИАМ . 45 (2): 167–256. arXiv : cond-mat/0303516 . Бибкод : 2003SIAMR..45..167N . дои : 10.1137/s003614450342480 . ISSN   0036-1445 . S2CID   221278130 .