Konfiguratsiya modeli - Configuration model - Wikipedia

Shakl 1. Konfiguratsiya modelidagi daraja ketma-ketligi va turli xil tarmoq realizatsiyasi^[1]

Yilda tarmoq fanlari, konfiguratsiya modeli berilganlardan tasodifiy tarmoqlarni yaratish usuli daraja ketma-ketlik. U real hayot uchun mos yozuvlar modeli sifatida keng qo'llaniladi ijtimoiy tarmoqlar, chunki u foydalanuvchiga o'zboshimchalik daraja taqsimotlarini kiritishga imkon beradi.

Tarmoq fanlari
Nazariya
Grafik Kompleks tarmoq Yuqish Kichik dunyo Miqyosiz Jamiyat tarkibi Perkulyatsiya Evolyutsiya Boshqarish qobiliyati Grafik rasm Ijtimoiy kapital Aloqa tahlili Optimallashtirish O'zaro munosabatlar Yopish Gomofil Transitivlik Imtiyozli biriktirma Balans nazariyasi Tarmoq effekti Ijtimoiy ta'sir
Tarmoq turlari
Axborot (hisoblash) Telekommunikatsiya Transport Ijtimoiy Ilmiy hamkorlik Biologik Sun'iy asab O'zaro bog'liq Semantik Mekansal Qaramlik Oqim chip
Graflar
Xususiyatlari Klik Komponent Kesilgan Velosiped Ma'lumotlar tarkibi Yon Loop Turar joy dahasi Yo'l Tepalik Yaqinlik ro'yxati  / matritsa Hodisa ro'yxati  / matritsa Turlari Ikki tomonlama Bajarildi Yo'naltirilgan Giper Ko'p Tasodifiy Og'irligi
Metrikalar Algoritmlar
Markazlik Darajasi O'rtada Yaqinlik PageRank Motiv Klasterlash Daraja taqsimoti Assortativlik Masofa Modullik Samaradorlik
Modellar
Topologiya Tasodifiy grafik Erduss-Renii Barabasi-Albert Fitness modeli Vatt-Strogatz Eksponentli tasodifiy (ERGM) Tasodifiy geometrik (RGG) Giperbolik (HGN) Ierarxik Stoxastik blok Maksimal entropiya Yumshoq konfiguratsiya LFR mezonlari Dinamika Mantiqiy tarmoq agentga asoslangan Epidemik /SIR
Ro'yxatlar Kategoriyalar
Mavzular Dasturiy ta'minot Tarmoq olimlari Kategoriya: Tarmoq nazariyasi Kategoriya: Grafika nazariyasi

Model uchun asos

Konfiguratsiya modelida berilgan daraja tanlangan ehtimollik taqsimotiga emas, balki har bir tepalikning darajasi oldindan belgilangan.^[2] Aksincha Erdős-Rényi modeli, konfiguratsiya modelining daraja ketma-ketligi a ga cheklangan emas Poisson-tarqatish, model foydalanuvchiga tarmoqqa istalgan darajadagi taqsimotni berishga imkon beradi.

Algoritm

Quyidagi algoritm model yaratilishini tavsiflaydi:

1. Bir daraja ketma-ketligini oling, ya'ni. e. ilmiy darajani tayinlash ${ displaystyle k_ {i}}$har bir tepaga. Tepaliklarning darajalari yarim bog'lanish yoki naycha sifatida ifodalanadi. Grafika tuzish uchun stublar yig'indisi teng bo'lishi kerak (${ displaystyle Sigma k_ {i} = 2m}$). Darajalar ketma-ketligini nazariy taqsimotdan olish mumkin yoki u haqiqiy tarmoqni ifodalashi mumkin qo'shni matritsa tarmoq).
2. Tasodifiy ravishda ikkita stubni tanlang va chekka hosil qilish uchun ularni ulang. Qolganlarning orasidan boshqa juftlikni tanlang ${ displaystyle 2m-2}$ stub va ularni ulang. Stublar tugamaguncha davom eting. Natijada oldindan belgilangan daraja ketma-ketligi bo'lgan tarmoq paydo bo'ladi. Tarmoqni amalga oshirish stublarni tanlash tartibiga qarab o'zgaradi, ular tsikllarni o'z ichiga olishi mumkin (b), o'z-o'zidan halqalar (c) yoki ko'p havolalar (d) (1-rasm) Shunga qaramay, kutilayotgan o'z-o'zini halqalar soni va ko'p havolalar nolga o'tadi N → ∞ limiti.^[1]

O'z-o'zidan halqalar, ko'p qirralar va natijalar

Yuqorida tavsiflangan algoritm bir xil ehtimollik bilan har qanday stubga mos keladi. Uyg'unlikning bir xil taqsimlanishi, yaratilgan tarmoqlarning boshqa xususiyatlarini hisoblash nuqtai nazaridan muhim xususiyatdir. Tarmoqni yaratish jarayoni o'z-o'zidan pastadir yoki bir nechta havolani yaratish hodisasini istisno etmaydi. Agar biz o'z-o'zidan halqa va ko'p qirralarga ruxsat berilmagan jarayonni ishlab chiqqan bo'lsak, stublarning bir-biriga mos kelishi bir xil taqsimotga mos kelmaydi. Biroq, o'z-o'zidan halqalar va ko'p qirralarning o'rtacha soni katta tarmoqlar uchun doimiydir, shuning uchun o'z-o'zidan halqalar va ko'p bog'lanishlarning zichligi nolga teng bo'ladi ${ displaystyle N rightarrow infty}$^[2] (batafsil ma'lumot uchun keltirilgan kitobga qarang).

O'z-o'zidan halqalar va ko'p qirralarning keyingi natijasi shundaki, barcha mumkin bo'lgan tarmoqlar bir xil ehtimollik bilan yaratilmaydi. Umuman olganda, barcha mumkin bo'lgan realizatsiya barcha tepaliklarning stublarini har qanday usul bilan almashtirish orqali hosil bo'lishi mumkin. Tugun stublarini almashtirish soni ${ displaystyle i}$ bu ${ displaystyle k_ {i}!}$, shuning uchun daraja ketma-ketligini amalga oshirish soni ${ displaystyle N {k_ {i} } = Pi _ {i} k_ {i}!}$. Bu shuni anglatadiki, har bir amalga oshirish bir xil ehtimollik bilan sodir bo'ladi. Biroq, o'z-o'zidan halqalar va ko'p qirralar amalga oshirish sonini o'zgartirishi mumkin, chunki o'z-o'zidan qirralarning joylashtirilishi o'zgarishsiz amalga oshirilishiga olib kelishi mumkin. O'z-o'zidan halqalar va ko'p bog'lanishlar soni yo'qolganligini hisobga olsak ${ displaystyle N rightarrow infty}$, turli xil realizatsiya ehtimoli o'zgarishi kichik bo'ladi, ammo mavjud bo'ladi.^[2]

Xususiyatlari

Yon ehtimoli

Tugun naychasi ${ displaystyle i}$ ga ulanishi mumkin ${ displaystyle 2m-1}$ boshqa stublar (bor ${ displaystyle 2m}$ stublar umuman, va biz hozir kuzatayotganimizni chiqarib tashlashimiz kerak). Tepalik ${ displaystyle j}$ bor ${ displaystyle k_ {j}}$ qaysi tugunga tegishli stublar ${ displaystyle i}$ bir xil ehtimollik bilan ulanishi mumkin (yagona taqsimot tufayli). Tugun stubining ehtimolligi ${ displaystyle i}$ ulardan biriga bog'langan ${ displaystyle k_ {j}}$ stublar ${ displaystyle { frac {k_ {j}} {2m-1}}}$. Tugundan beri ${ displaystyle i}$ bor ${ displaystyle k_ {i}}$ stublar, ehtimolligi ${ displaystyle i}$ ulangan ${ displaystyle j}$ bu ${ displaystyle { frac {k_ {i} k_ {j}} {2m-1}}}$ (${ displaystyle { frac {k_ {i} k_ {j}} {2m}}}$ etarli darajada katta ${ displaystyle m}$). O'z-o'zidan qirralarning paydo bo'lish ehtimoli ushbu formulada tavsiflanmaydi, lekin o'z-o'zidan qirralarning zichligi nolga teng bo'lganda ${ displaystyle N rightarrow infty}$, odatda yaxshi baho beradi.^[2]

Bir daraja taqsimotiga ega bo'lgan konfiguratsiya modeli berilgan ${ displaystyle p_ {k}}$, tasodifiy tanlangan tugunning ehtimoli ${ displaystyle i}$ darajaga ega ${ displaystyle k}$ bu ${ displaystyle p_ {k}}$. Ammo agar biz i qirralarining biridan keyin kelishimiz mumkin bo'lgan tepaliklardan birini olgan bo'lsak, k darajasiga ega bo'lish ehtimoli ${ displaystyle { frac {k} {2m}} * np_ {k} = { frac {kp_ {k}} {}}}$ . (K darajali tugunga erishish ehtimoli ${ displaystyle { frac {k} {2m}}}$va bor ${ displaystyle np_ {k}}$ bunday tugunlar.) Bu kasr bog'liq ${ displaystyle kp_ {k}}$ bilan odatdagi tugun darajasidan farqli o'laroq ${ displaystyle p_ {k}}$. Shunday qilib, odatdagi tugunning qo'shnisi odatdagi tugunning o'ziga qaraganda yuqori darajaga ega bo'lishi kutilmoqda. Konfiguratsiya modelining bu xususiyati "mening do'stlarim mendan ko'ra ko'proq do'stlarga ega" hodisasini yaxshi tasvirlaydi.

Klasterlash koeffitsienti

Global klasterlash koeffitsienti ${ displaystyle C_ {g}}$ (tugunning qo'shnilarining ulanishining o'rtacha ehtimoli) quyidagicha hisoblanadi:

${ displaystyle C_ {g} = sum _ {k_ {i}, k_ {j} = 0} ^ { infty} q_ {k} (i) q_ {k} (j) * { frac {k_ { i} k_ {j}} {2m}}}$,

qayerda ${ displaystyle q_ {k} (i), q_ {k} (j)}$ tepaliklarning ehtimollik taqsimotlarini bildiradi ${ displaystyle i}$ va ${ displaystyle j}$ ega bo'lish ${ displaystyle k_ {i}, k_ {j}}$ navbati bilan qirralarning.

${ displaystyle C_ {g} = { frac {1} {2m}} left [ sum _ {k = 0} ^ { infty} kq_ {k} right] ^ {2}}$

Yuqoridagi tenglamani o'zgartirgandan so'ng, biz taxminan olamiz

${ displaystyle thickapprox { frac {1} {2m}} * doimiy qalinapprox { frac {1} {N}} * doimiy}$, qayerda ${ displaystyle N}$ - bu tepalar soni va doimiyning kattaligi bog'liqdir ${ displaystyle p_ {k}}$.^[2] Shunday qilib, global klasterlash koeffitsienti ${ displaystyle C_ {g}}$katta n chegarada kichik bo'ladi.

Gigant komponent

Konfiguratsiya modelida, a ulkan komponent (GC) agar mavjud bo'lsa

${ displaystyle langle k ^ {2} rangle -2 langle k rangle> 0,}$

qayerda ${ displaystyle langle k rangle}$ va ${ displaystyle langle k ^ {2} rangle}$ ning birinchi va ikkinchi lahzalari daraja taqsimoti. Bu shuni anglatadiki, kritik chegara faqat daraja taqsimoti bilan aniqlanadigan miqdorlarga bog'liq ${ displaystyle p_ {k}}$.

Konfiguratsiya modeli mahalliy ravishda daraxtga o'xshash tarmoqlarni yaratadi, ya'ni bunday tarmoqdagi har qanday mahalliy mahalla daraxt shaklini oladi. Aniqrog'i, agar siz tarmoqdagi istalgan tugundan boshlasangiz va masofadan turib barcha tugunlar to'plamini shakllantirsangiz ${ displaystyle d}$ yoki undan boshlang'ich tugundan kamroq bo'lsa, to'siq $ 1 $ ga teng $ n to phi $ ga teng bo'lib, daraxt shaklini oladi.^[3] Daraxtga o'xshash inshootlarda ikkinchi qo'shnilar soni butun tarmoq bo'yicha o'rtacha hisobda, ${ displaystyle c_ {2}}$, bu: ${ displaystyle c_ {2} = langle k ^ {2} rangle - langle k rangle.}$

Keyinchalik, umuman olganda, masofadagi o'rtacha raqam ${ displaystyle d}$ quyidagicha yozilishi mumkin:

${ displaystyle c_ {d} = ({ frac {c_ {2}} {c_ {1}}}) ^ {d-1} c_ {1}.}$

Bu shuni anglatadiki, agar nisbati ${ displaystyle { frac {c_ {2}} {c_ {1}}}}$ bittadan kattaroq, keyin tarmoq ulkan komponentga ega bo'lishi mumkin. Bu Molloy-Reed mezonlari bilan mashhur.^[4] Ushbu mezon asosida sezgi shuki, agar ulkan komponent mavjud bo'lsa, unda tasodifiy tanlangan tepalikning o'rtacha darajasi ${ displaystyle i}$ ulangan komponentda kamida 2 bo'lishi kerak. Molloy-Reed mezonini quyidagicha ifodalash mumkin: ${ displaystyle sum _ {i} k_ {i} (k_ {i} -2)> 0,}$ bu shuni anglatadiki, garchi GK kattaligi bog'liq bo'lishi mumkin ${ displaystyle p_ {0}}$va ${ displaystyle p_ {2}}$, 0 va 2 darajali tugunlarning soni ulkan komponentning mavjud bo'lishida hech qanday hissa qo'shmaydi.^[3]

Diametri

Konfiguratsiya modeli har qanday darajadagi taqsimotni o'z zimmasiga olishi mumkin va kichik dunyo ta'siri, chunki buyurtma bo'yicha konfiguratsiya modelining diametri shunchaki ${ displaystyle d = { frac {ln (N)} {ln (c_ {2} / c_ {1})}}}$.^[5]

Cheklangan o'lchamdagi komponentlar

Tepaliklarning umumiy soni sifatida ${ displaystyle N}$ cheksizlikka intiladi, ikkita ulkan komponentni topish ehtimoli yo'qoladi. Bu shuni anglatadiki, siyrak rejimda model bitta ulkan komponentdan (agar mavjud bo'lsa) va cheklangan o'lchamdagi bir nechta ulangan komponentlardan iborat. Bog'langan tarkibiy qismlarning o'lchamlari ularning o'lchamlarini taqsimlash bilan tavsiflanadi ${ displaystyle w_ {n}}$- tasodifiy tanlangan tepalik o'lchamning bog'langan tarkibiy qismiga tegishli bo'lish ehtimoli ${ displaystyle n.}$ Daraja taqsimoti o'rtasida yozishmalar mavjud ${ displaystyle p_ {k}}$ va o'lchamlarni taqsimlash ${ displaystyle w_ {n}.}$ Tepaliklarning umumiy soni cheksizlikka intilsa, ${ displaystyle N rightarrow infty}$, quyidagi munosabat sodir bo'ladi:^[6]

${ displaystyle w_ {n} = { begin {case} { frac { langle k rangle} {n-1}} u_ {1} ^ {* n} (n-2), & n> 1, p_ {0} & n = 1, end {case}}}$

qayerda ${ displaystyle u_ {1} (k): = { frac {k + 1} { langle k rangle}} p_ {k + 1},}$ va ${ displaystyle u_ {1} ^ {* n}}$ belgisini bildiradi ${ displaystyle n}$- katlama konvolutsiya kuchi. Bundan tashqari, uchun aniq asimptotlar ${ displaystyle w_ {n}}$ qachon ma'lum ${ displaystyle n gg 1}$va ${ displaystyle | langle k ^ {2} rangle -2 langle k rangle |}$nolga yaqin.^[6] Ushbu asimptotlar uchun analitik iboralar momentlarning aniqligiga bog'liq ${ displaystyle p_ {k},}$ daraja taqsimoti quyruq ko'rsatkichi ${ displaystyle beta}$(qachon ${ displaystyle p_ {k}}$(og'ir dumi) va Molloy-Reed kriterium belgisi. Quyidagi jadvalda ushbu munosabatlar sarhisob qilingan (konstantalar berilgan^[6]).

Lahzalari ${ displaystyle p_ {k}}$	Quyruq ${ displaystyle p_ {k}}$	${ displaystyle { text {sign}} ( langle k ^ {2} rangle -2 langle k rangle)}$	${ displaystyle w_ {n}, ; n gg 1, ; alpha = beta -2}$
${ displaystyle langle k ^ {3} rangle < infty}$	engil quyruq	-1 yoki 1	${ displaystyle C_ {1} e ^ {- C_ {2} n} n ^ {- 3/2}}$
		0	${ displaystyle C_ {1} n ^ {- 3/2}}$
	og'ir quyruq, ${ displaystyle beta> 4}$	-1	${ displaystyle C_ {3} n ^ {- alfa -1}}$
		0	${ displaystyle C_ {1} n ^ {- 3/2}}$
		1	${ displaystyle C_ {1} e ^ {- C_ {2} n} n ^ {- 3/2}}$
${ displaystyle langle k ^ {3} rangle = infty,}$ ${ displaystyle langle k ^ {2} rangle < infty,}$	og'ir quyruq, ${ displaystyle beta = 4}$	-1	${ displaystyle C_ {3} n ^ {- alfa -1}}$
		0	${ displaystyle C_ {1} '{ frac {n ^ {- 3/2}} { sqrt { log n}}}}$
		1	${ displaystyle C_ {1} '{ frac {n ^ {- 3/2}} { sqrt { log n}}} e ^ {- C_ {2}' { frac {n} { log n }}}}$
	og'ir quyruq, ${ displaystyle 3 < beta <4}$	-1	${ displaystyle C_ {3} n ^ {- alfa -1}}$
		0	${ displaystyle C_ {4} n ^ {- { frac {1} { alpha}} - 1}}$
		1	${ displaystyle C_ {5} e ^ {- C_ {6} n} n ^ {- 3/2}}$
${ displaystyle langle k ^ {2} rangle = infty,}$ ${ displaystyle langle k rangle < infty,}$	og'ir quyruq, ${ displaystyle beta = 3}$	1	${ displaystyle C_ {7} e ^ {- C_ {8} -C_ {9} n ^ { frac {2} { pi}}} n ^ {{ frac {1} { pi}} - 2 }}$
	og'ir quyruq, ${ displaystyle 2 < beta <3}$	1	${ displaystyle C_ {10} e ^ {- C_ {11} n} n ^ {- 3/2}}$

Modellashtirish

Haqiqiy dunyo tarmoqlari bilan taqqoslash

Ning uchta umumiy xususiyati murakkab tarmoqlar heterojen daraja taqsimoti, qisqa o'rtacha yo'l uzunligi va yuqori klasterlash.^[1][7][8] Har qanday o'zboshimchalik daraja ketma-ketligini aniqlash imkoniyatiga ega bo'lgan holda, birinchi shartni loyihalashtirish bilan qondirish mumkin, ammo yuqorida ko'rsatilgandek global klasterlash koeffitsienti tarmoq hajmining teskari funktsiyasidir, shuning uchun katta konfiguratsion tarmoqlar uchun klasterlash kichik bo'lishga intiladi. Asosiy modelning bu xususiyati empirik tarmoqlarning ma'lum xususiyatlariga zid keladi, ammo modelning kengaytmalari bu muammoni hal qilishi mumkin (qarang. ^[9]).

Ilova: modullikni hisoblash

Konfiguratsiya modeli tarmoqni hisoblashda etalon sifatida qo'llaniladi modullik. Modullik tarmoqning modullarga bo'linish darajasini o'lchaydi. U quyidagicha hisoblanadi:

${ displaystyle Q = { frac {1} {2L}} sum _ {i neq j} { Bigl (} A_ {ij} - { frac {k_ {i} k_ {j}} {2L} } { Bigr)} delta (C_ {i}, C_ {j})}$^[10]

unda qo'shni matritsa tarmoqning tugun o'rtasida chekka bo'lish ehtimoli bilan taqqoslanadi ${ displaystyle i}$ va ${ displaystyle j}$ (ularning darajalariga qarab) konfiguratsiya modelida (sahifaga qarang modullik tafsilotlar uchun).

Yo'naltirilgan konfiguratsiya modeli

DCM-da (yo'naltirilgan konfiguratsiya modeli),^[11] har bir tugunga quyruq va bosh deb nomlangan bir nechta yarim qirralar beriladi. Keyin quyruq va boshlar tasodifiy ravishda bir xil tarzda mos ravishda yo'naltirilgan qirralarni hosil qiladi. Gigant komponentning hajmi,^[11][12] odatdagi masofa,^[13] va diametri^[14] DCM ning matematik tarzda o'rganilganligi. Shuningdek, bu borada keng qamrovli tadqiqotlar olib borildi tasodifiy yurish DCM-da.^[15][16][17]Ba'zi haqiqiy dunyo tarmoqlari DCM tomonidan modellashtirilgan, masalan, neyron tarmoqlar,^[18] Moliya^[19] va ijtimoiy tarmoqlar.^[20]

Yo'naltirilgan konfiguratsiya modeli

Adabiyotlar