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

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

Модель

Основы

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

${\displaystyle {\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 вершин как : ${\displaystyle p_{k,n}}$

${\displaystyle (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,}$

и

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

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

${\displaystyle 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}}}$

После некоторых преобразований приведенное выше выражение принимает вид

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

и

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

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

Обобщение

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

${\displaystyle 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)}},}$

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

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

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

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

Примечания

Для дальнейшего обсуждения см. ^{[5] [6]} и. ^{[7] [8]} Прайс смог получить эти результаты, но это то, чего он смог добиться без предоставления вычислительных ресурсов. К счастью, многие работы, посвященные предпочтительному присоединению и росту сетей, стали возможны благодаря недавнему технологическому прогрессу ^{[ по мнению кого? ]} .

Ссылки

1. de Solla Price, DJ (1965-07-30). "Сети научных статей". Science . 149 (3683). Американская ассоциация содействия развитию науки (AAAS): 510–515. Bibcode :1965Sci...149..510D. doi :10.1126/science.149.3683.510. ISSN  0036-8075. PMID  14325149.
2. de Solla Price, Derek J. (1976), «Общая теория библиометрических и других кумулятивных процессов преимуществ», J. Amer. Soc. Inform. Sci. , 27 (5): 292–306, CiteSeerX 10.1.1.161.114 , doi :10.1002/asi.4630270505, S2CID  8536863 
3. Саймон, Герберт А. (1955). «О классе функций косого распределения». Biometrika . 42 (3–4). Oxford University Press (OUP): 425–440. doi :10.1093/biomet/42.3-4.425. ISSN  0006-3444.
4. Эванс, ТС; Калмон, Л.; Василяускайте, В. (2020), «Самый длинный путь в модели цен», Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E, doi : 10.1038/s41598-020-67421-8, PMC 7324613 , PMID  32601403 
5. Дороговцев, SN; Мендес, JFF; Самухин, AN (2000-11-20). "Структура растущих сетей с предпочтительным связыванием". Physical Review Letters . 85 (21): 4633–4636. arXiv : cond-mat/0004434 . Bibcode : 2000PhRvL..85.4633D. doi : 10.1103/physrevlett.85.4633. ISSN  0031-9007. PMID  11082614. S2CID  118876189.
6. Крапивский, ПЛ; Реднер, С. (2001-05-24). "Организация растущих случайных сетей". Physical Review E. 63 ( 6). Американское физическое общество (APS): 066123. arXiv : cond-mat/0011094 . Bibcode : 2001PhRvE..63f6123K. doi : 10.1103/physreve.63.066123. ISSN  1063-651X. PMID  11415189. S2CID  16077521.
7. Дороговцев, СН; Мендес, Дж. Ф. Ф. (2002). «Эволюция сетей». Успехи физики . 51 (4): 1079–1187. arXiv : cond-mat/0106144 . Bibcode :2002AdPhy..51.1079D. doi :10.1080/00018730110112519. ISSN  0001-8732. S2CID  429546.
8. Крапивский, П. Л. и Реднер, С., Подход уравнения скорости для растущих сетей , в Р. Пастор-Саторрас и Дж. Руби (ред.), Труды XVIII конференции в Ситжесе по статистической механике, Конспект лекций по физике, Springer, Берлин (2003).

Источники

• Newman, MEJ (2003). «Структура и функции сложных сетей». SIAM Review . 45 (2): 167–256. arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N. doi : 10.1137/s003614450342480. ISSN  0036-1445. S2CID  221278130.