WikiDer > Eksponentli tasodifiy grafik modellar

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 Darajani taqsimlash 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
v t e

Eksponentli tasodifiy grafik modellari (ERGMlar) - bular oilasi statistik modellar haqidagi ma'lumotlarni tahlil qilish uchun ijtimoiy va boshqa tarmoqlar.^[1] ERGM yordamida tekshirilgan tarmoqlarning namunalariga bilim tarmoqlari,^[2] tashkiliy tarmoqlar,^[3] hamkasblar tarmoqlari,^[4] ijtimoiy tarmoqlar, ilmiy rivojlanish tarmoqlari,^[5] va boshqalar.

Fon

Ko'pgina ko'rsatkichlar kuzatilgan tarmoqning zichligi, markaziyligi yoki assortativligi kabi tizimli xususiyatlarini tavsiflash uchun mavjud.^[6][7] Biroq, ushbu ko'rsatkichlar ko'plab mumkin bo'lgan muqobil tarmoqlarning faqat bir nusxasi bo'lgan kuzatilgan tarmoqni tavsiflaydi. Ushbu muqobil tarmoqlar to'plami o'xshash yoki o'xshash bo'lmagan tarkibiy xususiyatlarga ega bo'lishi mumkin. Qo'llab quvvatlamoq statistik xulosa tarmoq tarkibini shakllantirishga ta'sir qiluvchi jarayonlar to'g'risida, a statistik model kuzatilgan tarmoqqa o'xshashligi bo'yicha tortilgan barcha mumkin bo'lgan muqobil tarmoqlar to'plamini ko'rib chiqishi kerak. Biroq, tarmoq ma'lumotlari o'zaro bog'liq bo'lganligi sababli, bu mustaqillik haqidagi taxminlarni va standart statistik modellarning bir xil taqsimlanishini buzadi. chiziqli regressiya.^[8][9] Shu bilan bir qatorda statistik modellar berilgan kuzatuv bilan bog'liq bo'lgan noaniqlikni aks ettirishi, nazariy qiziqish uyg'otadigan tarmoq tuzilmalarining nisbiy chastotasi to'g'risida xulosa chiqarishga, chalkash jarayonlarning ta'sirini ajratib turishga, murakkab tuzilmalarni samarali ifodalashga va mahalliy darajadagi jarayonlarni global darajadagi xususiyatlarga bog'lashga imkon berishi kerak.^[10] Darajani saqlaydigan randomizatsiyaMasalan, kuzatilgan tarmoqni bir nechta muqobil tarmoqlar nuqtai nazaridan ko'rib chiqishning o'ziga xos usuli.

Ta'rif

The Eksponent oilasi nafaqat tarmoqlarni, balki ko'plab turdagi ma'lumotlarni qamrab olish uchun keng modellar oilasi. ERGM - bu ushbu oiladan model bo'lib, u tarmoqlarni tavsiflaydi.

Rasmiy ravishda a tasodifiy grafik ${ displaystyle Y in { mathcal {Y}}}$ to'plamidan iborat ${ displaystyle n}$ tugunlari va ${ displaystyle m}$ dyadlar (qirralar) ${ displaystyle {Y_ {ij}: i = 1, nuqta, n; j = 1, nuqta, n }}$ qayerda ${ displaystyle Y_ {ij} = 1}$ agar tugunlar bo'lsa ${ displaystyle (i, j)}$ ulangan va ${ displaystyle Y_ {ij} = 0}$ aks holda.

Ushbu modellarning asosiy farazi shundaki, bu kuzatilgan grafadagi tuzilish ${ displaystyle y}$ ning berilgan vektori bilan izohlash mumkin etarli statistika ${ displaystyle s (y)}$ ular kuzatilgan tarmoq funktsiyasi va ba'zi hollarda tugun atributlari. Shunday qilib, o'zgarmas o'zgaruvchilar o'rtasidagi har qanday bog'liqlikni tavsiflash mumkin:

${ displaystyle P (Y = y | theta) = { frac { exp ( theta ^ {T} s (y))} {c ( theta)}}, quad forall y in { matematik {Y}}}$

qayerda ${ displaystyle theta}$ bilan bog'liq bo'lgan model parametrlarining vektori ${ displaystyle s (y)}$ va ${ displaystyle c ( theta) = sum _ {y ' in { mathcal {Y}}} exp ( theta ^ {T} s (y'))}$ normalizatsiya doimiysi.

Ushbu modellar har bir mumkin bo'lgan tarmoqdagi ehtimollik taqsimotini aks ettiradi ${ displaystyle n}$ tugunlar. Shu bilan birga, o'lchamdagi yo'naltirilgan tarmoq (oddiy grafika) uchun mumkin bo'lgan tarmoqlar to'plamining hajmi ${ displaystyle n}$ bu ${ displaystyle 2 ^ {n (n-1) / 2}}$. To'siqdagi mumkin bo'lgan tarmoqlar soni modelni cheklashi mumkin bo'lgan parametrlar sonidan ancha kattaroq bo'lgani uchun ideal ehtimollik taqsimoti bu maksimal darajaga ko'tariladi. Gibbs entropiyasi.^[11]

Adabiyotlar

Qo'shimcha o'qish

• Bishkin, M .; Stivala, A .; Mira, A .; Robins, G.; Lomi, A. (2018). "Katta tarmoq ma'lumotlarini muvozanat kutish orqali maksimal tezlikni tezkor baholash". Ilmiy ma'ruzalar. 8 (1): 11509. arXiv:1802.10311. Bibcode:2018 yil NatSR ... 811509B. doi:10.1038 / s41598-018-29725-8. PMC 6068132. PMID 30065311.
• Kaymo, A .; Friel, N (2011). "Eksponentli tasodifiy grafik modellari uchun Bayes xulosasi". Ijtimoiy tarmoqlar. 33: 41–55. arXiv:1007.5192. doi:10.1016 / j.socnet.2010.09.004.
• Erdos, P .; Reniy, A (1959). "Tasodifiy grafikalarda". Mathematicae nashrlari. 6: 290–297.
• Fienberg, S. E.; Vasserman, S. (1981). "Golland va Leyxardt tomonidan yo'naltirilgan grafikalar uchun ehtimollik taqsimotining eksponent oilasini muhokama qilish". Amerika Statistik Uyushmasi jurnali. 76 (373): 54–57. doi:10.1080/01621459.1981.10477600.
• Frank, O .; Strauss, D (1986). "Markov grafikalari". Amerika Statistik Uyushmasi jurnali. 81 (395): 832–842. doi:10.2307/2289017. JSTOR 2289017.
• Xendok, M. S .; Hunter, D. R .; Tugmalar, C. T .; Goodreau, S. M.; Morris, M. (2008). "statnet: Tarmoq ma'lumotlarini namoyish qilish, vizualizatsiya qilish, tahlil qilish va simulyatsiya qilish uchun dasturiy vositalar". Statistik dasturiy ta'minot jurnali. 24: 1–11. doi:10.18637 / jss.v024.i01.
• Xarris, Jenine K (2014). Eksponentli tasodifiy graflarni modellashtirishga kirish. Bilge.^[1]
• Hunter, D. R .; Goodreau, S. M.; Handkok, M. S. (2008). "Ijtimoiy tarmoq modellarining muvofiqligi". Amerika Statistik Uyushmasi jurnali. 103 (481): 248–258. CiteSeerX 10.1.1.206.396. doi:10.1198/016214507000000446.
• Hunter, D. R; Handkok, M. S. (2006). "Tarmoqlar uchun egri eksponentli oilaviy modellar bo'yicha xulosa". Hisoblash va grafik statistika jurnali. 15 (3): 565–583. CiteSeerX 10.1.1.205.9670. doi:10.1198 / 106186006X133069.
• Hunter, D. R .; Xendok, M. S .; Tugmalar, C. T .; Goodreau, S. M.; Morris, M. (2008). "ergm: Tarmoqlar uchun eksponent-oilaviy modellarni moslashtirish, simulyatsiya qilish va diagnostika qilish uchun to'plam". Statistik dasturiy ta'minot jurnali. 24 (3): 1–29. doi:10.18637 / jss.v024.i03.
• Jin, I.H .; Liang, F. (2012). "MCMC algoritmining stoxastik yaqinlashishida turli xil qisqartirishlarni ishlatadigan ijtimoiy tarmoqlar modellarini o'rnatish". Hisoblash va grafik statistika jurnali. 22 (4): 927–952. doi:10.1080/10618600.2012.680851.
• Koskinen, J. H .; Robins, G. L .; Pattison, P. E. (2010). "Bayes ma'lumotlarini ko'paytirish yordamida eksponentli tasodifiy grafik (p-yulduz) modellarini etishmayotgan ma'lumotlar bilan tahlil qilish". Statistik metodologiya. 7 (3): 366–384. doi:10.1016 / j.stamet.2009.09.007.
• Morris, M.; Xendok, M. S .; Hunter, D. R. (2008). "Eksponent va oilaviy tasodifiy grafikalar modellarining spetsifikatsiyasi: shartlar va hisoblash aspektlari". Statistik dasturiy ta'minot jurnali. 24 (4). doi:10.18637 / jss.v024.i04.
• Rinaldo, A .; Fienberg, S. E.; Chjou, Y. (2009). "Eksponentli tasodifiy grafik modellariga tatbiq etiladigan deskretli eksponentli tasodifiy oilalar geometriyasi to'g'risida". Elektron statistika jurnali. 3: 446–484. arXiv:0901.0026. doi:10.1214 / 08-EJS350.
• Robins, G.; Snayderlar T.; Vang, P.; Handkok, M .; Pattison, P (2007). "Ijtimoiy tarmoqlar uchun eksponent tasodifiy grafik (p *) modellaridagi so'nggi o'zgarishlar" (PDF). Ijtimoiy tarmoqlar. 29 (2): 192–215. doi:10.1016 / j.socnet.2006.08.003.
• Shvaynberger, Maykl (2011). "Diskron eksponent oilalarning beqarorligi, sezgirligi va nasli". Amerika Statistik Uyushmasi jurnali. 106 (496): 1361–1370. doi:10.1198 / jasa.2011.tm10747. PMC 3405854. PMID 22844170.
• Shvaynberger, Maykl; Handcock, Mark (2015). "Tasodifiy grafik modellarida mahalliy bog'liqlik: tavsif, xususiyatlar va statistik xulosa". Qirollik statistika jamiyati jurnali, B seriyasi. 77 (3): 647–676. doi:10.1111 / rssb.12081. PMC 4637985. PMID 26560142.
• Shvaynberger, Maykl; Styuart, Jonatan (2020). "Tasodifiy grafikalarning kanonik va egri eksponensial-oilaviy modellari uchun konsentratsiya va barqarorlik natijalari". Statistika yilnomalari. 48 (1): 374–396. arXiv:1702.01812. doi:10.1214 / 19-AOS1810.
• Snayderlar, T. A. B. (2002). "Monte Karlo zanjiri eksponentli tasodifiy grafika modellarini baholash" (PDF). Ijtimoiy tuzilish jurnali. 3.
• Snayderlar, T. A. B.; Pattison, P. E.; Robins, G. L .; Handkok, M. S. (2006). "Eksponentli tasodifiy grafik modellari uchun yangi spetsifikatsiyalar". Sotsiologik metodologiya. 36: 99–153. CiteSeerX 10.1.1.62.7975. doi:10.1111 / j.1467-9531.2006.00176.x.
• Strauss, D; Ikeda, M (1990). "Ijtimoiy tarmoqlar uchun psevdolikelitetni baholash". Amerika Statistik Uyushmasi jurnali. 5 (409): 204–212. doi:10.2307/2289546. JSTOR 2289546.
• van Duijn, M. A .; Snayderlar, T. A. B.; Zijlstra, B. H. (2004). "p2: yo'naltirilgan grafikalar uchun kovariatsiyalangan tasodifiy effekt modeli". Statistica Neerlandica. 58 (2): 234–254. doi:10.1046 / j.0039-0402.2003.00258.x.
• van Duijn, M. A. J.; Gile, K. J.; Handkok, M. S. (2009). "Exponential oilaviy tasodifiy grafika modellarining maksimal psevdo-ehtimoli va maksimal ehtimolligini taqqoslash doirasi". Ijtimoiy tarmoqlar. 31 (1): 52–62. doi:10.1016 / j.socnet.2008.10.003. PMC 3500576. PMID 23170041.