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

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

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

Модель

Основи

Розглянемо орієнтований граф з n вузлами. Нехай $p_k$ позначає частку вузлів з k ступенями і $\sum _k{p}_k=1$. Кожен новий вузол має вихідні ступені (а саме ті документи, на які він посилається) і він зафіксований в довгостроковій перспективі. Це не означає, що ступені можуть не відрізнятися між вузлами, просто ми припускаємо, що це означає ступінь m фіксується з плином часу. Зрозуміло, що $\sum _{k}k{p}_k=m$, отже m не обмежений цілими числами. Сама тривіальна форма вибіркового прикріплення означає, що новий вузол підключається до вузла, що існує, пропорційно його ступеню. Іншими словами, новий документ посилається на документ, який вже існує пропорційно до його ступеня. Нюанс такої ідеї полягає в тому, що ніяка нова стаття не цитується, коли він приєднався до мережі, тому він буде мати нульову ймовірність цитуються в майбутньому (коли є не обов'язково, як це відбувається). Щоб подолати це, Прайс запропонував, що вкладення повинні бути пропорційні деяким з констант. В цілому може бути довільним, але Прайс пропонує у цьому сенсі початкове цитування пов'язане з самим документом (тому коефіцієнт пропорційності тепер 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}-n{p}_{k,n}=[k{p}_{k-1,n}-(k+1)p_{k,n}]\frac{m}{m+1}\text{ for }k\ge 1,$

і

$(n+1)p_{0,n+1}-n{p}_{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{array}{cc}[k{p}_{k-1}-(k+1)p_k]\frac{m}{m+1}& \text{for }k\ge 1\\ 1-p_0\frac{m}{m+1}& \text{for }k=0\end{array}$

Після деяких маніпуляцій, вираз вище буде мати вигляд

$p_0=\frac{m+1}{2m+1}$

і

$p_k=\frac{k!}{(k+2+1/m)\cdots (3+1/m)}{p}_0=(1+1/m)𝐁(k+1,2+1/m),$

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

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

Зрозуміло, як узагальнити наведені вище результати на випадок, коли $k_0\ne 1$. Елементарні розрахунки показують, що

$p_k=\frac{m+k_0}{m(k_0+1)+k_0}\frac{𝐁(k+k_0,2+k_0/m)}{𝐁(k_0,2+k_0/m)},$

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

Примітки

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

Джерела

• Шаблон:Cite journal