Tasodifiy tarmoqning rivojlanishi - Evolution of a random network

Tasodifiy tarmoqning rivojlanishi odatda paydo bo'lishiga olib keladigan dinamik jarayondir ulkan komponent tarmoq topologiyasida ajoyib natijalar bilan birga. Ushbu jarayonni miqdoriy baholash uchun tarmoq ichidagi eng katta ulangan klasterning hajmini tekshirishga ehtiyoj bor, ${ displaystyle {N_ {G}}}$ , o'rtacha bilan farq qiladi daraja ${ displaystyle { left langle k right rangle}}$ .^[1] Tarmoqlar o'zlarining topologiyalarini rivojlanib borishi bilan o'zgarib, fazali o'tishga o'tishadi. Faza o'tishlari odatda fizikadan ma'lum, bu erda uning holati issiqlik energiyasi darajasiga qarab o'zgarganda yoki ba'zi materiallar tarkibida sovib ketganda ferromagnitik xususiyatlar paydo bo'ladi. Bunday fazali o'tishlar materiyada sodir bo'ladi, chunki u zarrachalar tarmog'i va shu sababli tarmoq fazasiga o'tish qoidalari bevosita unga taalluqlidir. Tarmoqlarda bosqichma-bosqich o'tish tarmoqqa ulanishlar qo'shilishi bilan sodir bo'ladi, ya'ni har tugmachada N tugunlari, ularning tasodifiy tanlangan juftligi o'rtasida bog'lanish o'rnatiladi. O'chirilgan tugunlar to'plamidan to'liq ulangan tarmoqqa o'tish tarmoq evolyutsiyasi deb ataladi.

Agar biz umuman N tugunlari ajratilgan tarmoqdan boshlasak (havolalar soni nolga teng bo'lsa) va tasodifiy tanlangan juft tugunlar orasidagi bog'lanishlarni qo'shishni boshlasak, tarmoq evolyutsiyasi boshlanadi. Bir muncha vaqt biz faqat juft tugunlarni yaratamiz. Biroz vaqt o'tgach, bu juftlarning ba'zilari birlashib, kichik daraxtlarni hosil qiladi. Tarmoqqa qo'shimcha havolalar qo'shishni davom etar ekanmiz, tarmoqdagi ulkan tarkibiy qism paydo bo'lishi kerak, chunki bu izolyatsiya qilingan daraxtlarning ba'zilari bir-biriga ulanadi. Bunga tanqidiy nuqta deyiladi. Bizning tabiiy misolimizda bu nuqta materiallarning holatini o'zgartiradigan haroratga mos keladi. Keyinchalik tizimga tugunlarni qo'shish, ulkan komponent yanada kattalashadi, chunki tobora ko'proq tugunlar ulkan komponentning bir qismi bo'lgan boshqa tugunga bog'lanishadi. Ushbu o'tishning boshqa bir muhim momenti - bu tarmoq to'liq ulangan bo'lsa, ya'ni barcha tugunlar bitta ulkan komponentga tegishli bo'lsa, u shu nuqtada tarmoqning o'zi samarali bo'ladi.^[1]

Gigant komponentning paydo bo'lishi uchun shartlar

In Erdős-Rényi modeli,^[2]^[3] o'rtacha daraja ${ displaystyle langle k rangle}$ n qirralari va N qirralari bo'lgan grafika tomonidan berilgan ${ displaystyle langle k rangle = { frac {2N} {n}}}$ .Gigant komponentning paydo bo'lishi sharti:

${ displaystyle { left langle k right rangle = 1}}$ .

Shunday qilib, ulkan komponentning paydo bo'lishi uchun bitta havola etarli^{[iqtibos kerak ]}.Agar shartni ifoda etgan holda ${ displaystyle {p}}$ , biri oladi^{[iqtibos kerak ]}:
${ displaystyle {P_ {c} = { frac {1} {N-1}} taxminan { frac {1} {N}}}}$ (1)
Qaerda ${ displaystyle {N}}$ tugunlarning soni, ${ displaystyle {P_ {c}}}$ ehtimolligi klasterlash^{[iqtibos kerak ]}. Shuning uchun, tarmoq qanchalik katta bo'lsa, shunchalik kichik bo'ladi ${ displaystyle {p}}$ ulkan komponent uchun etarli.

Tasodifiy tarmoq evolyutsiyasi rejimlari

Tarmoq fanida o'ziga xos xususiyatlarga ega uchta topologik rejimni ajratish mumkin: subkritik, superkritik va bog'liq rejimlar.

Subkritik rejim

Subkritik bosqich kichik izolyatsiya qilingan klasterlar bilan tavsiflanadi, chunki bog'lanishlar soni tugunlar sonidan kamroq. Gigant komponentni istalgan vaqtda eng katta ajratilgan kichik komponent sifatida belgilash mumkin, ammo bu bosqichda klaster o'lchamlari farqi deyarli ahamiyatsiz.

${ displaystyle {0 < left langle k right rangle <1}}$ , ${ displaystyle { chap (p <{ frac {1} {n}} o'ng)}}$

Uchun ${ displaystyle { left langle k right rangle = 0}}$ tarmoq quyidagilardan iborat ${ displaystyle {N}}$ ajratilgan tugunlar. Ko'paymoqda ${ displaystyle { left langle k right rangle}}$ qo'shishni anglatadi ${ displaystyle {N chap langle k right rangle = pN (N-1) / 2}}$ tarmoqqa ulanish. Shunga qaramay, buni hisobga olgan holda ${ displaystyle { left langle k right rangle <1}}$ , bu rejimda juda oz sonli bo'g'inlar mavjud, shuning uchun asosan mayda klasterlar kuzatilishi mumkin edi. Har qanday vaqtda eng katta klaster ulkan komponent sifatida belgilanishi mumkin. Shunga qaramay, ushbu rejimda eng katta klasterning nisbiy hajmi, ${ displaystyle { frac {N_ {G}} {N}}}$ , nol bo'lib qoladi. Buning sababi shundaki ${ displaystyle { left langle k right rangle <1}}$ eng katta klaster - bu o'lchamga ega bo'lgan daraxt ${ displaystyle {N_ {G} sim lnN}}$ , shuning uchun uning hajmi tarmoq hajmiga qaraganda ancha sekin o'sadi. ${ displaystyle {N_ {G} / N = lnN / N rightarrow 0}}$ ichida ${ displaystyle {N rightarrow infty}}$ Xulosa qilib aytganda, subkritik rejimda tarmoq ko'plab kichik tarkibiy qismlardan iborat bo'lib, ularning kattaligi eksponent taqsimotga mos keladi. Shunday qilib, ushbu komponentlar solishtirma o'lchamlarga ega, chunki biz gigant sifatida belgilashimiz mumkin bo'lgan aniq g'olib yo'q.^[1]

Muhim nuqta

Tugunlarni bir-biriga bog'lashda davom etayotganimizda, juftliklar birlashganda kichik daraxtlar hosil bo'ladi va agar biz tugunlarni bir-biriga bog'lab tursak, = 1 muhim nuqtasida ajralib turadigan ulkan komponent paydo bo'ladi.

Bu shuni anglatadiki, har bir komponent o'rtacha 1 ta havolaga ega bo'lgan paytda ulkan komponent paydo bo'ladi. Ushbu nuqta p = 1 / (N-1) ehtimolga mos keladi, chunki ikkita tugun o'rtasida bog'lanish ehtimoli bitta havola bo'lib, bu bitta bog'lanish tasodifiy tanlangan ikkita tugunni birlashtirganda, boshqa imkoniyatlarga bo'linib bitta ulanish tugunlardan birini boshqa tugunga ulashi mumkin, bu N-1, chunki tugun boshqa barcha tugunlarga ulanishi mumkin, lekin o'zi (ushbu modeldagi o'z-o'zidan halqa olish imkoniyatini hisobga olmaganda).

Bundan tashqari, shuni anglatadiki, tarmoq qanchalik katta bo'lsa, kichikroq chuqurga ulkan komponent paydo bo'lishi kerak.

${ displaystyle {0 < left langle k right rangle = 1}}$ , ${ displaystyle { chap (p = { frac {1} {n}} o'ng)}}$ .

Muhim nuqta rejimni hali ulkan tarkibiy qismi bo'lmagan joyda ajratib turadi ( ${ displaystyle {0 < left langle k right rangle <1}}$ ) mavjud bo'lgan rejimdan ( ${ displaystyle { left langle k right rangle> 1}}$ ). Ushbu nuqtada, eng katta komponentning nisbiy hajmi hali ham nolga teng. Darhaqiqat, eng katta komponentning o'lchami ${ displaystyle {N_ {G} sim N ^ { tfrac {2} {3}}}}$ . Binobarin, ${ displaystyle {N_ {G}}}$ tarmoq hajmiga qaraganda ancha sekin o'sadi, shuning uchun uning nisbiy hajmi kamayadi ${ displaystyle {{ frac {N_ {G}} {N}} sim N ^ {- { tfrac {1} {3}}}}}$ ichida ${ displaystyle {N rightarrow infty}}$ limit.Lekin, shuni yodda tutingki, absolyut ravishda eng katta komponentning kattaligida sezilarli sakrash mavjud ${ displaystyle { left langle k right rangle = 1}}$ .Masalan, bilan tasodifiy tarmoq uchun ${ displaystyle {N = 7 ast 109}}$ dunyoning ijtimoiy tarmog'i bilan taqqoslanadigan tugunlar ${ displaystyle {0 < left langle k right rangle <1}}$ eng katta klaster tartibda ${ displaystyle {N_ {G} simeq lnN = ln (7 ast 109) simeq 22.7}}$ . Aksincha at ${ displaystyle { left langle k right rangle = 1}}$ biz kutmoqdamiz ${ displaystyle {N_ {G} simeq N ^ { tfrac {2} {3}} = (7 ast 109) { tfrac {2} {3}} sim 3 ast 106}}$ , taxminan beshta kattalikdagi sakrash. Shunga qaramay, subkritik rejimda ham, kritik nuqtada ham eng katta tarkibiy qism tarmoqdagi tugunlarning umumiy sonining faqat yo'q bo'lib ketadigan qismini o'z ichiga oladi. . Quvvat to'g'risidagi qonun shakli turli o'lchamdagi tarkibiy qismlar mavjudligini ko'rsatadi. Ushbu ko'p sonli kichik qismlar asosan daraxtlardir, ulkan komponent esa ko'chadan iborat bo'lishi mumkin. E'tibor bering, kritik nuqtadagi tarmoqning ko'pgina xususiyatlari faza o'tayotgan fizik tizim xususiyatlariga o'xshaydi.^[1]

Superkritik rejim

Kritik nuqtadan o'tib, ulkan tarkibiy qism paydo bo'lgandan so'ng, biz ko'proq ulanishlarni qo'shganimizda, tarmoq o'sib borayotgan ulkan tarkibiy qismdan va kamroq va kamroq kichik izolyatsiya qilingan klasterlar va tugunlardan iborat bo'ladi, aksariyat haqiqiy tarmoqlar th rejimiga tegishli. Gigant komponentning kattaligi quyidagicha tavsiflanadi Ng = (p - dona) N.

${ displaystyle { left langle k right rangle> 1}}$ , ${ displaystyle { chap (p> { frac {1} {n}} o'ng)}}$ .

Ushbu rejim haqiqiy tizimlar uchun eng dolzarbdir, chunki biz birinchi marta tarmoqqa o'xshash ulkan komponentga egamiz. Kritik nuqta yaqinida ulkan komponentning hajmi quyidagicha o'zgarib turadi:
${ displaystyle {N_ {G} / N sim left langle k right rangle -1}}$
yoki
${ displaystyle {N_ {G} sim (p-p_ {c}) N}}$ (2)
bu erda kompyuter (1) bilan berilgan. Boshqacha qilib aytganda, ulkan komponent tugunlarning cheklangan qismini o'z ichiga oladi. Kritik nuqtadan qancha uzoqlashsak, tugunlarning katta qismi unga tegishli bo'ladi. E'tibor bering (2) faqat atrofida joylashgan ${ displaystyle { left langle k right rangle = 1}}$ . Katta uchun ${ displaystyle { left langle k right rangle}}$ o'rtasidagi bog'liqlik ${ displaystyle {N_ {G}}}$ va ${ displaystyle { left langle k right rangle}}$ Xulosa qilib aytganda, o'ta kritik rejimda juda ko'p ajratilgan komponentlar ulkan komponent bilan bir vaqtda mavjud bo'lib, ularning eksponensial taqsimotidan keyin ularning o'lchamlari taqsimlanadi. Ushbu kichik tarkibiy qismlar daraxtlardir, ulkan komponent esa ko'chadan va tsikllardan iborat. Superkritik rejim barcha tugunlar gigant tomonidan singib ketguncha davom etadi.^[1]

Ulangan rejim

Tarmoqqa ulanishlar qo'shilganda, = lnN bo'lganda nuqta keladi va gigantkomponent barcha tugunlarni o'zlashtiradi, shuning uchun ajratilgan tugunlar va o'zaro bog'liq bo'lmagan komponentlar bo'lmaydi.

${ displaystyle { left langle k right rangle> ln N}}$ , ${ displaystyle { chap (p> { frac { ln N} {N}} o'ng)}}$ .

Etarli darajada katta p uchun ulkan komponent barcha tugunlarni va tarkibiy qismlarni o'zlashtiradi ${ displaystyle {N_ {G} simeq N}}$ . Izolyatsiya qilingan tugunlar bo'lmasa, tarmoq ulanadi. Bu sodir bo'ladigan o'rtacha darajaga bog'liq ${ displaystyle {N}}$ kabi ${ displaystyle { left ({ frac { ln N} {N}} right) rightarrow 0}}$ . E'tibor bering, biz ulangan rejimga kirganimizda, tarmoq hali ham nisbatan siyrak ${ displaystyle { left ({ frac { ln N} {N}} right) rightarrow 0}}$ katta N. uchun tarmoq faqat to'liq grafikaga aylanadi ${ displaystyle { left langle k right rangle = N-1}}$ .Xulosa qilib aytganda, tasodifiy tarmoq modeli tarmoqning paydo bo'lishi silliq, asta-sekinlik bilan emasligini taxmin qiladi: kichik uchun kuzatilgan izolyatsiya qilingan tugunlar va mayda komponentlar faza orqali ulkan tarkibiy qismga aylanadi.^[1]

Tabiatdagi hodisalarga misollar

Suv-muz o'tish

Faza o'tishlari materiyada sodir bo'ladi, chunki uni zarralar tarmog'i deb hisoblash mumkin. Suv bo'lganda muzlatilgan, 0 darajaga (kritik nuqtaga) etib kelganida, muzning kristalli tuzilishi tasodifiy tarmoqlarning fazali o'tishlariga ko'ra paydo bo'ladi: Sovutish davom etar ekan, har bir suv molekulasi to'rtta boshqa bilan kuchli bog'lanib, paydo bo'layotgan tarmoq bo'lgan muz panjarasini hosil qiladi.

Magnit fazali o'tish

Xuddi shunday, magnit fazali o'tish ferromagnitik materiallar, shuningdek, tarmoq evolyutsiyasi namunasiga amal qiladi: ma'lum bir haroratdan yuqori, aylantiradi alohida atomlar ikki xil yo'nalishga ishora qilishi mumkin. Biroq, material soviganida, ma'lum bir kritik haroratga yetganda, spinlar bir xil yo'nalishga ishora qiladi va hosil bo'ladi magnit maydon. Material tarkibidagi magnit xususiyatlarning paydo bo'lishi tasodifiy tarmoq evolyutsiyasiga o'xshaydi.^[1]

Ilovalar

Fizika va kimyo

Yuqoridagi misollarda ko'rib turganimizdek, tarmoq nazariyasi materiallarning tuzilishiga taalluqlidir, shuning uchun u fizika va kimyo bo'yicha materiallar va ularning xususiyatlari bilan bog'liq tadqiqotlarda ham qo'llaniladi.

Ayniqsa muhim sohalar polimerlar,^[4] jellar,^[5] kabi boshqa moddiy rivojlanish tsellyuloza sozlanishi xususiyatlarga ega.^[6]

Biologiya va tibbiyot

Faza o'tishlari oqsillarning ishlashi yoki hujayra darajasida diabet paydo bo'lishi bilan bog'liq tadqiqotlarda qo'llaniladi.^[7] Neyrologiya, shuningdek, tarmoqlarning evolyutsiyasi modelidan keng foydalanadi, chunki fazali o'tish neyron tarmoqlarida sodir bo'ladi.^[8]

Tarmoq fanlari, statistika va mashinalarni o'rganish

Tarmoqning bosqichma-bosqich o'tishi tabiiy ravishda o'z intizomi doirasida yanada rivojlangan modellarning asosidir. Bu tarmoqlarda klasterlash va perkolatsiyani o'rganishda olib borilgan tadqiqotlarda qaytib keladi,^[9] yoki tugun xususiyatlarini bashorat qilish.^[10]

Adabiyotlar

^ ^a ^b ^v ^d ^e ^f ^g Albert-Laslo Barabasi. Tarmoq fanlari: 3-bob
^ Erdos, Pol va Alfred Reniy. "Tasodifiy grafikalar evolyutsiyasi to'g'risida". Publ. Matematika. Inst. Osildi. Akad. Ilmiy 5.1 (1960): 17-60. http://leonidzhukov.net/hse/2014/socialnetworks/papers/erdos-1960-10.pdf
^ Erdos P., Rényi A. "I tasodifiy grafikalar to'g'risida". Publ. matematik. debretsen 6.290-297 (1959): 18. http://www.leonidzhukov.net/hse/2016/networks/papers/erdos-1959-11.pdf
^ Samulionis, V., Svirskas, SH., Banys, J., Sanches-Ferrer, A., Gimeno, N., & Ros, M. B. (2015). Dielektrik va ultratovush usullari bilan aniqlangan smektik egilgan yadroli asosiy zanjirli polimer tarmoqlaridagi fazali o'tish. Ferroelektriklar, 479(1), 76-81. doi:10.1080/00150193.2015.1012011
^ Habicht, A., Schmolke, W., Lange, F., Saalwachter, K., & Seiffert, S. (nd). Mikrogel hajmining o'zgarishi jarayonida polimer-tarmoq bir xilligining ta'sir etmasligi: o'rtacha maydon istiqbolini qo'llab-quvvatlash. Makromolekulyar kimyo va fizika, 215(11), 1116-1133.
^ Liu, C., Zhong, G., Huang, H., va Li, Z. (nd). O'zgaruvchan xususiyatlarga ega bo'lgan g'ovakli tsellyulozada uch o'lchovli nanofibril - varaqli tarmoqlarga fazali yig'ilish natijasida o'tish. Tsellyuloza, 21(1), 383-394.
^ Stamper, I., Jekson, E., va Vang, X. (nd). Pankreatik adacık uyali aloqa tarmoqlarida o'zgarishlar o'tishi va 1-toifa diabetga ta'siri. Jismoniy sharh E, 89(1),
^ Li, KE Lopes, MA Mendes, JFF Goltsev, AV (2014). "Kritik hodisalar va neyronal tarmoqlarda shovqinga sabab bo'lgan fazali o'tish". Jismoniy sharh E. 89: 012701. arXiv:1310.4232. Bibcode:2014PhRvE..89a2701L. doi:10.1103 / PhysRevE.89.012701.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
^ Colomer-de-Simon, P., & Boguna, M. (2014). Klasterli kompleks tarmoqlarda ikki marta perkolatsiya fazasiga o'tish.
^ Chjan, P., Mur, S, va Zdeborova, L. (2014). Noyob tarmoqlarda yarim nazorat ostida klasterlashda fazali o'tish.

[:1-1] v ^d ^e ^f ^g Albert-Laslo Barabasi. Tarmoq fanlari: 3-bob

[2] Erdos, Pol va Alfred Reniy. "Tasodifiy grafikalar evolyutsiyasi to'g'risida". Publ. Matematika. Inst. Osildi. Akad. Ilmiy 5.1 (1960): 17-60. http://leonidzhukov.net/hse/2014/socialnetworks/papers/erdos-1960-10.pdf

[3] Erdos P., Rényi A. "I tasodifiy grafikalar to'g'risida". Publ. matematik. debretsen 6.290-297 (1959): 18. http://www.leonidzhukov.net/hse/2016/networks/papers/erdos-1959-11.pdf

[4] Samulionis, V., Svirskas, SH., Banys, J., Sanches-Ferrer, A., Gimeno, N., & Ros, M. B. (2015). Dielektrik va ultratovush usullari bilan aniqlangan smektik egilgan yadroli asosiy zanjirli polimer tarmoqlaridagi fazali o'tish. Ferroelektriklar, 479(1), 76-81. doi:10.1080/00150193.2015.1012011

[5] Habicht, A., Schmolke, W., Lange, F., Saalwachter, K., & Seiffert, S. (nd). Mikrogel hajmining o'zgarishi jarayonida polimer-tarmoq bir xilligining ta'sir etmasligi: o'rtacha maydon istiqbolini qo'llab-quvvatlash. Makromolekulyar kimyo va fizika, 215(11), 1116-1133.

[6] Liu, C., Zhong, G., Huang, H., va Li, Z. (nd). O'zgaruvchan xususiyatlarga ega bo'lgan g'ovakli tsellyulozada uch o'lchovli nanofibril - varaqli tarmoqlarga fazali yig'ilish natijasida o'tish. Tsellyuloza, 21(1), 383-394.

[7] Stamper, I., Jekson, E., va Vang, X. (nd). Pankreatik adacık uyali aloqa tarmoqlarida o'zgarishlar o'tishi va 1-toifa diabetga ta'siri. Jismoniy sharh E, 89(1),

[8] Li, KE Lopes, MA Mendes, JFF Goltsev, AV (2014). "Kritik hodisalar va neyronal tarmoqlarda shovqinga sabab bo'lgan fazali o'tish". Jismoniy sharh E. 89: 012701. arXiv:1310.4232. Bibcode:2014PhRvE..89a2701L. doi:10.1103 / PhysRevE.89.012701.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)

[9] Colomer-de-Simon, P., & Boguna, M. (2014). Klasterli kompleks tarmoqlarda ikki marta perkolatsiya fazasiga o'tish.

[10] Chjan, P., Mur, S, va Zdeborova, L. (2014). Noyob tarmoqlarda yarim nazorat ostida klasterlashda fazali o'tish.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]