Модель Прайса
Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. (травень 2017) |
Модель Прайса (названа на честь англійського фізика Дерека Дж. Прайса) — це математична модель для мереж посилань, що зростають. Це була перша модель, яка узагальнила модель Саймона[1] , щоб можна було використовувати її для звичайних мереж та мереж, які можуть зростати. Модель Прайса відноситься до більш широкого класу мережевих моделей, що зростають (разом із достатньо відомою моделлю Барабаші — Альберта), чия головна мета пояснити виникнення мереж з сильно перекошеним ступенем розподілу. Модель включає ідеї моделі Саймона, що зображають концепцію багаті багатіють, також відому, як ефект Матфея. Прайс взяв приклад - мережу з посиланнями між науковими працями, і описав її властивості. Його ідея полягала в тому, що так як стара вершина (дійсний документ) знаходить нові грані (нові посилання) має бути пропорція до кількості дійсних граней (дійсних цитат) для яких вершина вже є. Це називається кумулятивною перевагою, тепер також відома як переважне приєднання. Робота Прайса також має велике значення в наданні першого відомого прикладу безмасштабних мереж (хоча вони були так названі пізніше). Його ідеї були використані для опису багатьох реальних мереж, таких як веб.
Модель
Основи
Розглянемо орієнтований граф з n вузлами. Нехай позначає частку вузлів з k ступенями і . Кожен новий вузол має вихідні ступені (а саме ті документи, на які він посилається) і він зафіксований в довгостроковій перспективі. Це не означає, що ступені можуть не відрізнятися між вузлами, просто ми припускаємо, що це означає ступінь m фіксується з плином часу. Зрозуміло, що , отже m не обмежений цілими числами. Сама тривіальна форма вибіркового прикріплення означає, що новий вузол підключається до вузла, що існує, пропорційно його ступеню. Іншими словами, новий документ посилається на документ, який вже існує пропорційно до його ступеня. Нюанс такої ідеї полягає в тому, що ніяка нова стаття не цитується, коли він приєднався до мережі, тому він буде мати нульову ймовірність цитуються в майбутньому (коли є не обов'язково, як це відбувається). Щоб подолати це, Прайс запропонував, що вкладення повинні бути пропорційні деяким з констант. В цілому може бути довільним, але Прайс пропонує у цьому сенсі початкове цитування пов'язане з самим документом (тому коефіцієнт пропорційності тепер k + 1 замість k). Ймовірність нової грані підключитись до будь-якого вузла зі ступенем k є
Еволюція мережі
Наступним питанням є зміни в мережі кількості вузлів зі ступенем k при додаванні нових вузлів мережі. Природно, це число зменшується, так як деякі k-ступеневі вузли мають нові грані, звідси стає (k + 1)-ступеневі вузли; але, з іншого боку, це число теж зростає, так як деякі (k − 1)-ступеневі вузли можуть отримати нові грані, стаючи k-ступеневими вузлами. Щоб виразити цю зміну мережі формально, позначимо частку k-ступеневих вузлів в мережі з n вершинами як :
і
Для отримання стаціонарного рішення для спочатку дозвольте виразити використовуючи відомі майстер-рівняння метод, як
Після деяких маніпуляцій, вираз вище буде мати вигляд
і
з , що є бета-функція. Як наслідок, . Це рівнозначно тому, що слідує степеневому закону розподілу з показником . Як правило, це показник між 2 і 3, що характерно для багатьох реальних мереж. Прайс протестував свою модель шляхом порівняння з даними мереж посилань і прийшли до висновку, що в результаті можливо зробити досить хороший розподіл за степеневим законом.
Узагальнення
Зрозуміло, як узагальнити наведені вище результати на випадок, коли . Елементарні розрахунки показують, що
Що ще раз дає розподіл за степеневим законом з таким же показником для великих k і фіксованого .
Примітки
Для подальшого обговорення, див.,[2][3] в.[4][5] Прайс зумів вивести ці результати, але це було все, що він міг зробити без обчислювальних ресурсів. На щастя, багато робіт, присвячені вибірковим прикріпленням і мережам, що зростають, стали можливими завдяки недавнім технологічним прогресом.
Джерела
- Newman, M. E. J., The Structure and Function of Complex Networks, SIAM Review, 45(2), 167—256 (2003)
Посилання
- ↑ Simon, H. A., On a class of skew distribution functions, Biometrika 42, 425—440 (1955).
- ↑ Dorogovtsev, S. N., Mendes, J. F. F., and Samukhin, A. N., Structure of growing networks with preferential linking, Phys.
- ↑ Krapivsky, P. L. and Redner, S., Organization of growing random networks, Phys.
- ↑ Dorogovtsev, S. N. and Mendes, J. F. F., Evolution of networks, Advances in Physics 51, 1079—1187 (2002).
- ↑ Krapivsky, P. L. and Redner, S., Rate equation approach for growing networks, in R. Pastor-Satorras and J. Rubi (eds.