Модель Воттса-Строгаца — це модель генерації випадкових графів, яка створює графи з властивостями тісного світу, зокрема з короткою середньою довжиною шляху та високою кластеризацією. Модель була запропонована [en] та Стівеном Строгацом у їх спільній статті в журналі Nature 1998 року. Модель також відома як (Watts) бета модель після того, як Воттс використовував для опису моделі в своїй популярній науковій книзі [en].
Обґрунтування для моделі
Формальне вивчення випадкових графів датується роботою Пала Ердеша та Альфреда Реньї. Графи, які вони розглядали, тепер відомі як класичні графи або модель Ердеша — Реньї, пропонують просту та потужну модель з багатьма додатками.
Проте модель Ердеша — Реньї не має двох важливих властивостей, що спостерігаються в багатьох реальних мережах:
- Вони не генерують місцеві кластери та [en]. Натомість, оскільки вони мають постійну, випадкову та незалежну ймовірність підключення двох вузлів, модель Ердеша — Реньї має низький коефіцієнт кластеризації.
- Вони не враховують утворення вузлів. Формально ступінь вершини розподілу графа Ердеша-Реньї сходиться до розподілу Пуассона, а не до закону потужності, що спостерігається в багатьох реальних безмасштабних мережах.
Модель Ердеша — Реньї була спроектована як найпростіша модель, яка стосується першого з двох обмежень. Це припускає кластеризацію, зберігаючи короткі довжини шляху моделі Ердеша-Реньї. Це відбувається шляхом інтерполяції між ЕР-графіком і регулярною кільцевою решіткою. Отже, модель здатна принаймні частково пояснити «малі світові» явища в різних мережах, таких як енергетична мережа, нейронна мережа C elegans та мережа кіноакторів. У 2015 році дослідники з Каліфорнійського технологічного інституту та Принстонського університету показали, що модель Воттса-Строгаца пояснює зв'язок жирового обміну в дріжджах, що починають жити.
Алгоритм
Враховуючи бажану кількість вузлів , означає ступінь (вважається рівним цілим числом) і спеціальний параметр , що задовольняє ( i . Модель конструює неорієнтований граф з -вузлами та зв'язками за таким чином:
- Побудуйте правильну кільцеву решітку, графік з вузлами, кожен з яких з'єднаний з сусідніми, з кожного боку. Тобто, якщо вузли позначені , є ребро якщо і тільки якщо
- Для кожного вузла , з , перемотати його з ймовірністю бета-версія. Перемотування здійснюється шляхом заміни з , де вибирається з рівномірною ймовірністю з усіх можливих значень, які уникають самоплетіння () та дублювання посилань (немає краю з в цій точці алгоритму).
Властивості
Основна решітка структури моделі створює локально кластеризовану мережу, а випадкові зв'язки різко зменшують середню довжину шляху. Алгоритм представляє решітчастих країв. Різні дозволяє інтерполювати між регулярною ґраткою () і випадковим графіком () наближаючись до випадкового графа Ердеша-Реньї з і .
Три цікаві властивості — це середня довжина шляху, високий коефіцієнт кластеризації та розподіл ступеня.
Середня довжина шляху
Для кільцевої решітки середня довжина шляху становить і масштабується лінійно з розміром системи. У граничному випадку граф сходиться до класичного випадкового графа з . Проте в проміжній області середня довжина шляху падає дуже швидко з збільшенням , швидко наближаючись до його граничного значення.
Коефіцієнт кластеризації
Для кільцевої решітки коефіцієнт кластеризації , і тому має тенденцію до , оскільки зростає незалежно від розміру системи. У граничному випадку коефіцієнт кластеризації досягає значення для класичних випадкових графів і, таким чином, обернено пропорційний розміру системи. У проміжному регіоні коефіцієнт кластеризації залишається досить близьким до його значення для звичайної решітки і лише падає при відносно високому (\ displaystyle \ beta) \ beta. Це призводить до регіону, де середня довжина шляху швидко падає, але коефіцієнт кластеризації не пояснюється явищем «малого світу».
- Якщо ми використовуємо міру Barrat і Weigt для кластеризації , визначеної як частка між середньою кількістю ребер між сусідами вузла та середньою кількістю можливі краї між цими сусідами або, альтернативно,
- то ми отримаємо
Розподіл ступеня
Розподіл ступенів у випадку кільцевої решітки є просто дельта-функцією Дірака, центрованою в . У граничному випадку це розподіл Пуассона, як з класичними графіками. Розподіл ступенів для можна записати як,
де — це кількість ребер, які мають вузол або її ступінь. Тут та . Форма розподілу ступенів аналогічна розподілу ступеня і має яскраво виражений пік при і розпадається експоненціально для великих . Топологія мережі є відносно однорідною, і всі вузли більш-менш однакові.
Обмеження
Основним обмеженням моделі є те, що він виробляє нереальний ступінь вершини. На відміну від цього, реальні мережі часто безмаштабні мережі, неоднорідні в ступені, мають концентратори та безмаштабний розподіл ступенів. Такі мережі краще описуються в цьому відношенні переважним сімейством моделей приєднання, такими як модель Барабаші-Альберта (БА). (З іншого боку, модель Барабаші-Альберт не здатна забезпечити високий рівень кластеризації в реальних мережах, це недолік, який не використовується моделями Воттса-Строгаца. Таким чином, ні модель Воттса-Строгаца, ні модель Барабаші-Альберт не можна вважати цілком реалістичними.)
Модель Воттса-Строгаца також передбачає фіксовану кількість вузлів і, таким чином, не може бути використана для моделювання зростання мережі.
Див. також
Посилання
- ; Strogatz, S. H. (1998). (PDF). Nature. 393 (6684): 440—442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. Архів оригіналу (PDF) за 11 квітня 2020. Процитовано 28 листопада 2017.
- Erdos, P. (1960). Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi. Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
- Ravasz, E. (30 серпня 2002). Hierarchical Organization of Modularity in Metabolic Networks. Science. 297 (5586): 1551—1555. Bibcode:2002Sci...297.1551R. doi:10.1126/science.1073374.
- Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network. PLOS Computational Biology. 11 (5): e1004264. Bibcode:2015PLSCB..11E4264A. doi:10.1371/journal.pcbi.1004264. PMID 26020510.
{{}}
: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом () - Albert, R., Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics. 74 (1): 47—97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
- Barrat, A.; Weigt, M. (2000). On the properties of small-world network models (PDF). European Physical Journal B. 13 (3): 547—560. doi:10.1007/s100510050067. Процитовано 26 лютого 2008.[недоступне посилання]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Model Vottsa Strogaca ce model generaciyi vipadkovih grafiv yaka stvoryuye grafi z vlastivostyami tisnogo svitu zokrema z korotkoyu serednoyu dovzhinoyu shlyahu ta visokoyu klasterizaciyeyu Model bula zaproponovana en ta Stivenom Strogacom u yih spilnij statti v zhurnali Nature 1998 roku Model takozh vidoma yak Watts beta model pislya togo yak Votts vikoristovuvav b displaystyle beta dlya opisu modeli v svoyij populyarnij naukovij knizi en Obgruntuvannya dlya modeliFormalne vivchennya vipadkovih grafiv datuyetsya robotoyu Pala Erdesha ta Alfreda Renyi Grafi yaki voni rozglyadali teper vidomi yak klasichni grafi abo model Erdesha Renyi proponuyut prostu ta potuzhnu model z bagatma dodatkami Prote model Erdesha Renyi ne maye dvoh vazhlivih vlastivostej sho sposterigayutsya v bagatoh realnih merezhah Voni ne generuyut miscevi klasteri ta en Natomist oskilki voni mayut postijnu vipadkovu ta nezalezhnu jmovirnist pidklyuchennya dvoh vuzliv model Erdesha Renyi maye nizkij koeficiyent klasterizaciyi Voni ne vrahovuyut utvorennya vuzliv Formalno stupin vershini rozpodilu grafa Erdesha Renyi shoditsya do rozpodilu Puassona a ne do zakonu potuzhnosti sho sposterigayetsya v bagatoh realnih bezmasshtabnih merezhah Model Erdesha Renyi bula sproektovana yak najprostisha model yaka stosuyetsya pershogo z dvoh obmezhen Ce pripuskaye klasterizaciyu zberigayuchi korotki dovzhini shlyahu modeli Erdesha Renyi Ce vidbuvayetsya shlyahom interpolyaciyi mizh ER grafikom i regulyarnoyu kilcevoyu reshitkoyu Otzhe model zdatna prinajmni chastkovo poyasniti mali svitovi yavisha v riznih merezhah takih yak energetichna merezha nejronna merezha C elegans ta merezha kinoaktoriv U 2015 roci doslidniki z Kalifornijskogo tehnologichnogo institutu ta Prinstonskogo universitetu pokazali sho model Vottsa Strogaca poyasnyuye zv yazok zhirovogo obminu v drizhdzhah sho pochinayut zhiti AlgoritmWatts Strogatz graph Vrahovuyuchi bazhanu kilkist vuzliv N displaystyle N oznachaye stupin K displaystyle K vvazhayetsya rivnim cilim chislom i specialnij parametr b displaystyle beta sho zadovolnyaye 0 b 1 displaystyle 0 leq beta leq 1 i N K ln N 1 displaystyle N gg K gg ln N gg 1 Model konstruyuye neoriyentovanij graf z N displaystyle N vuzlami ta N K 2 displaystyle frac NK 2 zv yazkami za takim chinom Pobudujte pravilnu kilcevu reshitku grafik z N displaystyle N vuzlami kozhen z yakih z yednanij z K displaystyle K susidnimi K 2 displaystyle K 2 z kozhnogo boku Tobto yaksho vuzli poznacheni n 0 n N 1 displaystyle n 0 ldots n N 1 ye rebro n i n j displaystyle n i n j yaksho i tilki yaksho 0 lt i j mod N 1 K 2 K 2 displaystyle 0 lt i j mod left N 1 frac K 2 right leq frac K 2 Dlya kozhnogo vuzla n i n 0 n N 1 displaystyle n i n 0 dots n N 1 n i n j displaystyle n i n j z i lt j displaystyle i lt j peremotati jogo z jmovirnistyu b displaystyle beta beta versiya Peremotuvannya zdijsnyuyetsya shlyahom zamini n i n j displaystyle n i n j z n i n k displaystyle n i n k de k displaystyle k vibirayetsya z rivnomirnoyu jmovirnistyu z usih mozhlivih znachen yaki unikayut samopletinnya k i displaystyle k neq i ta dublyuvannya posilan nemaye krayu n i n k displaystyle n i n k z k k displaystyle k k v cij tochci algoritmu VlastivostiOsnovna reshitka strukturi modeli stvoryuye lokalno klasterizovanu merezhu a vipadkovi zv yazki rizko zmenshuyut serednyu dovzhinu shlyahu Algoritm predstavlyaye b N K 2 displaystyle beta frac NK 2 reshitchastih krayiv Rizni b displaystyle beta dozvolyaye interpolyuvati mizh regulyarnoyu gratkoyu b 0 displaystyle beta 0 i vipadkovim grafikom b 1 displaystyle beta 1 nablizhayuchis do vipadkovogo grafa Erdesha Renyi G n p displaystyle G n p z n N displaystyle n N i p N K 2 N 2 displaystyle p frac NK 2 N choose 2 Tri cikavi vlastivosti ce serednya dovzhina shlyahu visokij koeficiyent klasterizaciyi ta rozpodil stupenya Serednya dovzhina shlyahuDlya kilcevoyi reshitki serednya dovzhina shlyahu stanovit ℓ 0 N 2 K 1 displaystyle ell 0 N 2K gg 1 i masshtabuyetsya linijno z rozmirom sistemi U granichnomu vipadku b 1 displaystyle beta rightarrow 1 graf shoditsya do klasichnogo vipadkovogo grafa z ℓ 1 ln N ln K displaystyle ell 1 frac ln N ln K Prote v promizhnij oblasti 0 lt b lt 1 displaystyle 0 lt beta lt 1 serednya dovzhina shlyahu padaye duzhe shvidko z zbilshennyam b displaystyle beta shvidko nablizhayuchis do jogo granichnogo znachennya Koeficiyent klasterizaciyiDlya kilcevoyi reshitki koeficiyent klasterizaciyi C 0 3 K 2 4 K 1 displaystyle C 0 frac 3 K 2 4 K 1 i tomu maye tendenciyu do 3 4 displaystyle 3 4 oskilki K displaystyle K zrostaye nezalezhno vid rozmiru sistemi U granichnomu vipadku b 1 displaystyle beta rightarrow 1 koeficiyent klasterizaciyi dosyagaye znachennya dlya klasichnih vipadkovih grafiv C 1 K N displaystyle C 1 K N i takim chinom oberneno proporcijnij rozmiru sistemi U promizhnomu regioni koeficiyent klasterizaciyi zalishayetsya dosit blizkim do jogo znachennya dlya zvichajnoyi reshitki i lishe padaye pri vidnosno visokomu displaystyle beta beta Ce prizvodit do regionu de serednya dovzhina shlyahu shvidko padaye ale koeficiyent klasterizaciyi ne poyasnyuyetsya yavishem malogo svitu Yaksho mi vikoristovuyemo miru Barrat i Weigt dlya klasterizaciyi C b displaystyle C beta viznachenoyi yak chastka mizh serednoyu kilkistyu reber mizh susidami vuzla ta serednoyu kilkistyu mozhlivi krayi mizh cimi susidami abo alternativno C b 3 number of triangles number of connected triples displaystyle C beta equiv frac 3 times text number of triangles text number of connected triples dd to mi otrimayemo C b C 0 1 b 3 displaystyle C beta sim C 0 1 beta 3 Rozpodil stupenyaRozpodil stupeniv u vipadku kilcevoyi reshitki ye prosto delta funkciyeyu Diraka centrovanoyu v K displaystyle K U granichnomu vipadku b 1 displaystyle beta rightarrow 1 ce rozpodil Puassona yak z klasichnimi grafikami Rozpodil stupeniv dlya 0 lt b lt 1 displaystyle 0 lt beta lt 1 mozhna zapisati yak P k n 0 f k K C K 2 n 1 b n b K 2 n b K 2 k K 2 n k K 2 n e b K 2 displaystyle P k sum n 0 f k K C K 2 n 1 beta n beta K 2 n frac beta K 2 k K 2 n k K 2 n e beta K 2 de k i displaystyle k i ce kilkist reber yaki mayut vuzol i th displaystyle i text th abo yiyi stupin Tut k K 2 displaystyle k geq K 2 ta f k K min k K 2 K 2 displaystyle f k K min k K 2 K 2 Forma rozpodilu stupeniv analogichna rozpodilu stupenya i maye yaskravo virazhenij pik pri k K displaystyle k K i rozpadayetsya eksponencialno dlya velikih k K displaystyle k K Topologiya merezhi ye vidnosno odnoridnoyu i vsi vuzli bilsh mensh odnakovi ObmezhennyaOsnovnim obmezhennyam modeli ye te sho vin viroblyaye nerealnij stupin vershini Na vidminu vid cogo realni merezhi chasto bezmashtabni merezhi neodnoridni v stupeni mayut koncentratori ta bezmashtabnij rozpodil stupeniv Taki merezhi krashe opisuyutsya v comu vidnoshenni perevazhnim simejstvom modelej priyednannya takimi yak model Barabashi Alberta BA Z inshogo boku model Barabashi Albert ne zdatna zabezpechiti visokij riven klasterizaciyi v realnih merezhah ce nedolik yakij ne vikoristovuyetsya modelyami Vottsa Strogaca Takim chinom ni model Vottsa Strogaca ni model Barabashi Albert ne mozhna vvazhati cilkom realistichnimi Model Vottsa Strogaca takozh peredbachaye fiksovanu kilkist vuzliv i takim chinom ne mozhe buti vikoristana dlya modelyuvannya zrostannya merezhi Div takozhSvit tisnij graf Graf Rado Model Erdesha Renyi Model Barabashi Albert Socialna merezhaPosilannya Strogatz S H 1998 PDF Nature 393 6684 440 442 Bibcode 1998Natur 393 440W doi 10 1038 30918 PMID 9623998 Arhiv originalu PDF za 11 kvitnya 2020 Procitovano 28 listopada 2017 Erdos P 1960 Publications Mathematicae 6 290 1959 P Erdos A Renyi Publ Math Inst Hung Acad Sci 5 17 Ravasz E 30 serpnya 2002 Hierarchical Organization of Modularity in Metabolic Networks Science 297 5586 1551 1555 Bibcode 2002Sci 297 1551R doi 10 1126 science 1073374 Al Anzi Bader Arpp Patrick Gerges Sherif Ormerod Christopher Olsman Noah Zinn Kai 2015 Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network PLOS Computational Biology 11 5 e1004264 Bibcode 2015PLSCB 11E4264A doi 10 1371 journal pcbi 1004264 PMID 26020510 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Obslugovuvannya CS1 Storinki iz nepoznachenim DOI z bezkoshtovnim dostupom posilannya Albert R Barabasi A L 2002 Statistical mechanics of complex networks Reviews of Modern Physics 74 1 47 97 arXiv cond mat 0106096 Bibcode 2002RvMP 74 47A doi 10 1103 RevModPhys 74 47 Barrat A Weigt M 2000 On the properties of small world network models PDF European Physical Journal B 13 3 547 560 doi 10 1007 s100510050067 Procitovano 26 lyutogo 2008 nedostupne posilannya