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

Модель Прайса (названа на честь англійського фізика Дерека Дж. Прайса) — це математична модель для , що зростають.

Це була перша модель, яка узагальнила , щоб можна було використовувати її для звичайних мереж та мереж, які можуть зростати. Модель Прайса відноситься до більш широкого класу мережевих моделей, що зростають (разом із достатньо відомою моделлю Барабаші — Альберта), чия головна мета пояснити виникнення мереж з сильно перекошеним ступенем розподілу. Модель включає ідеї , що зображають концепцію , також відому, як ефект Матфея. Прайс взяв приклад - мережу з посиланнями між науковими працями, і описав її властивості. Його ідея полягала в тому, що так як стара вершина (дійсний документ) знаходить нові грані (нові посилання) має бути пропорція до кількості дійсних граней (дійсних цитат) для яких вершина вже є. Це називається кумулятивною перевагою, тепер також відома як переважне приєднання. Робота Прайса також має велике значення в наданні першого відомого прикладу безмасштабних мереж (хоча вони були так названі пізніше). Його ідеї були використані для опису багатьох реальних мереж, таких як веб.

Модель

Основи

Розглянемо орієнтований граф з n вузлами. Нехай ${\displaystyle p_{k}}$ позначає частку вузлів з k ступенями і ${\displaystyle \sum _{k}{p_{k}}=1}$. Кожен новий вузол має вихідні ступені (а саме ті документи, на які він посилається) і він зафіксований в довгостроковій перспективі. Це не означає, що ступені можуть не відрізнятися між вузлами, просто ми припускаємо, що це означає ступінь m фіксується з плином часу. Зрозуміло, що ${\displaystyle \sum _{k}{kp_{k}}=m}$, отже m не обмежений цілими числами. Сама тривіальна форма вибіркового прикріплення означає, що новий вузол підключається до вузла, що існує, пропорційно його ступеню. Іншими словами, новий документ посилається на документ, який вже існує пропорційно до його ступеня. Нюанс такої ідеї полягає в тому, що ніяка нова стаття не цитується, коли він приєднався до мережі, тому він буде мати нульову ймовірність цитуються в майбутньому (коли є не обов'язково, як це відбувається). Щоб подолати це, Прайс запропонував, що вкладення повинні бути пропорційні деяким з констант. В цілому може бути довільним, але Прайс пропонує у цьому сенсі початкове цитування пов'язане з самим документом (тому коефіцієнт пропорційності тепер k + 1 замість k). Ймовірність нової грані підключитись до будь-якого вузла зі ступенем k є

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

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

Узагальнення

Зрозуміло, як узагальнити наведені вище результати на випадок, коли ${\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)}},}$

Що ще раз дає розподіл за степеневим законом ${\displaystyle p_{k}}$ з таким же показником ${\displaystyle \alpha =2+k_{0}/m}$ для великих k і фіксованого ${\displaystyle k_{0}}$.

Примітки

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

Посилання

1. de Solla Price, D. J. (30 липня 1965). Networks of Scientific Papers. Science. American Association for the Advancement of Science (AAAS). 149 (3683): 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), A general theory of bibliometric and other cumulative advantage processes, , 27 (5): 292—306, doi:10.1002/asi.4630270505
3. Simon, Herbert A. (1955). On a class of skew distribution functions. Biometrika. Oxford University Press (OUP). 42 (3–4): 425—440. doi:10.1093/biomet/42.3-4.425. ISSN 0006-3444.
4. Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N. (20 листопада 2000). Structure of Growing Networks with Preferential Linking. 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.
5. Krapivsky, P. L.; Redner, S. (24 травня 2001). Organization of growing random networks. Physical Review E. American Physical Society (APS). 63 (6): 066123. arXiv:cond-mat/0011094. Bibcode:2001PhRvE..63f6123K. doi:10.1103/physreve.63.066123. ISSN 1063-651X. PMID 11415189. S2CID 16077521.
6. Dorogovtsev, S. N.; Mendes, J. F. F. (2002). Evolution of networks. Advances in Physics. 51 (4): 1079—1187. arXiv:cond-mat/0106144. Bibcode:2002AdPhy..51.1079D. doi:10.1080/00018730110112519. ISSN 0001-8732. S2CID 429546.
7. Krapivsky, P. L. and Redner, S., Rate equation approach for growing networks, in R. Pastor-Satorras and J. Rubi (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics, Lecture Notes in Physics, Springer, Berlin (2003).

Джерела

• Newman, M. E. J. (2003). The Structure and Function of Complex Networks. SIAM Review. 45 (2): 167—256. arXiv:cond-mat/0303516. Bibcode:2003SIAMR..45..167N. doi:10.1137/s003614450342480. ISSN 0036-1445. S2CID 221278130.