Vaqtinchalik tarmoq - Temporal network

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

A vaqtinchalik tarmoq, shuningdek, a vaqt o'zgaruvchan tarmoq, a tarmoq ularning havolalari faqat ma'lum vaqt nuqtalarida faol bo'ladi. Har bir havola faol bo'lganligi to'g'risidagi ma'lumotlarni va boshqa mumkin bo'lgan xususiyatlarni o'z ichiga oladi vazn. Vaqt bo'yicha o'zgarib turadigan tarmoqlar alohida ahamiyatga ega tarqalish jarayonlari, ma'lumot va kasallik tarqalishi kabi, chunki har bir havola aloqa qilish imkoniyati va aloqalarni tayinlash vaqti kiritilgan.

Vaqt bo'yicha o'zgarib turadigan tarmoqlarga misol qilib har bir havola nisbatan qisqa yoki bir zumda bo'lgan aloqa tarmoqlari, masalan, telefon qo'ng'iroqlari yoki elektron pochta xabarlari kiradi.^[1][2] Axborot ikkala tarmoq orqali tarqaladi, ba'zi kompyuter viruslari esa ikkinchisida tarqaladi. Jismoniy yaqinlik tarmoqlari, kim kimga va qachon duch kelishini kodlash, vaqt o'zgaruvchan tarmoqlar sifatida ifodalanishi mumkin.^[3] Ba'zi kasalliklar, masalan, havodagi patogenlar, jismoniy yaqinlik orqali tarqaladi. Yaxshilash uchun o'z vaqtida aniqlangan jismoniy yaqinlik tarmoqlari haqidagi real ma'lumotlar ishlatilgan epidemiyani modellashtirish.^[4]Neyron tarmoqlari va miya tarmoqlari vaqt o'zgaruvchan tarmoqlar sifatida ifodalanishi mumkin, chunki neyronlarning faollashishi vaqt bilan bog'liq.^[5]

Vaqt bo'yicha o'zgarib turadigan tarmoqlar alohida ulanishlar miqyosida intervalgacha faollashuvi bilan tavsiflanadi. Bu turli xil modellardan farq qiladi tarmoq evolyutsiyasi, bu umuman tarmoq miqyosida vaqtga bog'liqlikni o'z ichiga olishi mumkin.

Amaliyligi

Vaqt bo'yicha o'zgaruvchan tarmoqlar tabiatan dinamik bo'lib, modellashtirish uchun ishlatiladi tarqalish jarayonlari tarmoqlarda. Vaqt bo'yicha o'zgarib turadigan tarmoqlardan foydalanish qo'shimcha murakkablikka loyiq bo'ladimi, qarindoshga bog'liq vaqt o'lchovlari savol ostida. Vaqt o'zgaruvchan tarmoqlar, tarmoqdagi tarqalish jarayoni va tarmoqning o'zi o'xshash vaqt o'lchovlarida rivojlanib boradigan tizimlarni tavsiflashda eng foydalidir.^[6]

Tarmoq evolyutsiyasi uchun xarakterli vaqt shkalasi bo'lsin ${ displaystyle t_ {N}}$va tarqalish jarayoni evolyutsiyasi uchun xarakterli vaqt o'lchovi bo'lishi kerak ${ displaystyle t_ {P}}$. Tarmoqdagi jarayon uchta toifadan biriga kiradi:

• Statik yaqinlashish - qaerda ${ displaystyle t_ {N} gg t_ {P}}$. Tarmoq nisbatan sekin rivojlanib boradi, shuning uchun jarayonning dinamikasini tarmoqning statik versiyasi yordamida taxmin qilish mumkin.
• Vaqt o'zgaruvchan tarmoq - qaerda ${ displaystyle t_ {N} sim t_ {P}}$. Tarmoq va jarayon taqqoslanadigan vaqt jadvallarida rivojlanib boradi, shuning uchun ular orasidagi o'zaro bog'liqlik muhim ahamiyat kasb etadi.
• Tavsiya etilgan yaqinlashish - qaerda ${ displaystyle t_ {N} ll t_ {P}}$. Tarmoq nisbatan tez rivojlanib boradi, shuning uchun jarayonning dinamikasini tarmoqning o'rtacha vaqt versiyasi yordamida taxmin qilish mumkin.

Internet orqali ma'lumotlar oqimi birinchi holatga misol bo'la oladi, bu erda tarmoq bir soniya ichida juda oz o'zgaradi tarmoq paketi uni bosib o'tish.^[7] Ning tarqalishi jinsiy yo'l bilan yuqadigan kasalliklar ikkinchisining misoli, bu erda kasallik tarqalishi evolyutsiya darajasiga to'g'ridan-to'g'ri bog'liqlikda tarqaladi. jinsiy aloqa tarmog'i o'zi.^[8] Xulq-atvorning yuqishi uchinchi holatning misoli, bu erda xatti-harakatlar populyatsiya orqali ko'plab kundalik ijtimoiy aloqalarning birlashtirilgan tarmog'i orqali tarqaladi.^[9]

Vakolatxonalar

Vaqt bo'yicha o'zgarib turadigan tarmoq ma'lumotlari uchun uchta umumiy vakolatxona mavjud.^[10]

• Kontaktlar ketma-ketligi - agar o'zaro ta'sirlarning davomiyligi ahamiyatsiz bo'lsa, tarmoq to'plam sifatida ifodalanishi mumkin ${ displaystyle C}$ kontaktlar ${ displaystyle (i, j, t)}$ qayerda ${ displaystyle i}$ va ${ displaystyle j}$ tugunlari va ${ displaystyle t}$ o'zaro ta'sir vaqti. Shu bilan bir qatorda, uni chekka ro'yxat sifatida ko'rsatish mumkin ${ displaystyle E}$ har bir chekka qaerda ${ displaystyle e}$ tugunlar juftligi va faol vaqtlar to'plamiga ega ${ displaystyle T_ {e} = {t_ {1}, ldots, t_ {n} }}$.
• Intervalli grafikalar - agar o'zaro ta'sirlarning davomiyligi ahamiyatsiz bo'lsa, ${ displaystyle T_ {e}}$ chekka bo'lgan oraliqlarning to'plamiga aylanadi ${ displaystyle e}$ faol. ${ displaystyle T_ {e} = {(t_ {1}, t_ {1} '), ldots, (t_ {n}, t_ {n}') }}$
• Oniy tasvirlar - vaqt bo'yicha o'zgarib turadigan tarmoqlar, shuningdek, har bir qadam uchun bitta statik tarmoq qatori sifatida ifodalanishi mumkin.

Xususiyatlari

Statik tarmoqlarni tavsiflash uchun qo'llaniladigan chora-tadbirlar vaqt o'zgaruvchan tarmoqlarga darhol o'tkazilmaydi. Qarang Yo'l, Ulanish, Masofa, Markazlik. Biroq, ushbu tarmoq kontseptsiyalari vaqt o'zgaruvchan tarmoqlarda qo'llanilishi uchun moslangan.

Vaqtni hurmat qilish yo'llari

Yo'llarni hurmat qilish vaqti vaqt o'tishi bilan o'zgarib turadigan tarmoqda o'tish mumkin bo'lgan bog'lanishlar ketma-ketligi, keyingi o'tish kerak bo'lgan havola joriy havoladan keyin biron bir vaqtda faollashishi cheklovi ostida. A kabi yo'naltirilgan grafik, dan yo'l ${ displaystyle i}$ ga ${ displaystyle j}$ dan yo'l borligini anglatmaydi ${ displaystyle j}$ ga ${ displaystyle i}$. Aksincha yo'llar statik va rivojlanayotgan tarmoqlarda, vaqtni hurmat qilish yo'llari ham mavjud o'tmaydigan. Bu yo'l borligi sababli ${ displaystyle i}$ ga ${ displaystyle j}$ va dan ${ displaystyle j}$ ga ${ displaystyle k}$ dan yo'l borligini anglatmaydi ${ displaystyle i}$ ga ${ displaystyle k}$. Bundan tashqari, vaqtni hurmat qilish yo'llari o'zlari uchun vaqt jihatidan farq qiladi va faqat ma'lum bir vaqt oralig'ida to'g'ri yo'llardir.^[11]

Reachability

Ga o'xshash bo'lsa-da ulanish statik tarmoqlarda, erishish imkoniyati tarmoqdagi har bir tugun uchun eng yaxshi aniqlangan vaqtni o'zgartiruvchi xususiyatdir. The ta'sir to'plami tugunning ${ displaystyle i}$ - erishish mumkin bo'lgan barcha tugunlarning to'plami ${ displaystyle i}$ vaqtni hurmat qilish yo'li bilan, uning boshlanish vaqtiga bog'liqligini unutmang ${ displaystyle t}$. The manba to'plami tugunning ${ displaystyle i}$ erishish mumkin bo'lgan barcha tugunlarning to'plamidir ${ displaystyle i}$ ma'lum bir vaqt oralig'ida yo'llarni hurmat qilish orqali. The erishish darajasi barcha tugunlar bo'yicha o'rtacha sifatida aniqlanishi mumkin ${ displaystyle i}$ ichidagi tugunlarning ulushini ta'sir to'plami ning ${ displaystyle i}$.^[12]

Ulanish butun bir tarmoq kamroq aniq belgilangan, garchi ba'zi birlari taklif qilingan bo'lsa ham. Agar komponentning barcha tugunlarini har ikki yo'nalishda birlashtiradigan vaqtga to'g'ri keladigan yo'l mavjud bo'lsa, tarkibiy qism kuchli bog'langan deb ta'riflanishi mumkin. Agar komponentning barcha tugunlarini ikkala yo'nalishda birlashtiradigan vaqt yo'nalishi mavjud bo'lsa, komponent zaif ulangan deb ta'riflanishi mumkin.^[13] Bundan tashqari, agar tarkibiy qism transitiv ravishda bog'langan bo'lsa, aniqlanishi mumkin tranzitivlik ushbu komponentdagi tugunlarning pastki qismini ushlab turadi.

Vaqtinchalik tarmoqlarning ulanishini yo'naltirilgan perkolatsiya muammosiga xaritalash orqali o'rganish mumkin.^[14]Vaqtinchalik bog'lanish ehtimoli juda muhim qiymatga ega, uning ostida ulanish nolga teng, deyarli barcha tugunlarni ulash mumkin. Buni fazali o'tish deb hisoblash mumkin.

Sababli vafo

Sababli vafo vaqtinchalik tarmoqning statik yaqinlashuvining yaxshiliklarini aniqlaydi. Bunday statik yaqinlashish vaqt o'tishi bilan vaqtinchalik tarmoq chekkalarini yig'ish natijasida hosil bo'ladi. Nedensel sodiqlik g'oyasi vaqtinchalik tarmoqdagi barcha tugun juftliklari orasidagi yo'llarning sonini taqqoslashdir ${ displaystyle P_ {temp}}$ (ya'ni har doim yo'llarni hurmat qilish) yo'llarning soni bilan ${ displaystyle P_ {stat}}$ tarmoqning statik yaqinlashuvidagi barcha tugunlar o'rtasida.^[15] Keyin sababiy vafodorlik bilan belgilanadi

${ displaystyle c = { frac {P_ {temp}} {P_ {stat}}}}$.

Yildan beri ${ displaystyle P_ {temp}}$ faqat vaqtni hurmat qilish yo'llari hisobga olinadi, ${ displaystyle P_ {temp} leq P_ {stat}}$va natijada ${ displaystyle 0 leq c leq 1}$. Yuqori nedensel vafo ${ displaystyle c taxminan 1}$ ko'rib chiqilgan vaqtinchalik tarmoq statik (yig'ilgan) hamkasbi tomonidan yaxshi taxmin qilinganligini anglatadi. Agar ${ displaystyle c ll 1}$, keyin statik ko'rinishga ega bo'lgan ko'pgina tugun juftliklari vaqtinchalik tarmoqdagi vaqtni hisobga olgan holda bog'liq emas.

Kechikish

Shuningdek, chaqirildi vaqtinchalik masofa, kechikish uchun vaqt o'zgaruvchan ekvivalenti masofa. Vaqt o'zgarib turadigan tarmoqda har qanday vaqtda hurmat qilish yo'li bor a davomiyligi, ya'ni bu yo'lni bosib o'tish uchun zarur bo'lgan vaqt. Ikki tugun orasidagi eng tezkor yo'l bu kechikish, shuningdek, boshlash vaqtiga bog'liqligini unutmang. Tugundan kechikish ${ displaystyle i}$ tugun ${ displaystyle j}$ vaqtida boshlanadi ${ displaystyle t}$ bilan belgilanadi ${ displaystyle lambda _ {i, t} (j)}$.

Markazlik o'lchovlari

Vaqt bo'yicha o'zgaruvchan tarmoqlarda markaziylikni o'lchash to'g'ridan-to'g'ri almashtirishni o'z ichiga oladi masofa bilan kechikish.^[16] Statik tarmoqdagi markazlashtirish choralarini muhokama qilish uchun qarang Markazlik.

• Yaqinlik markazligi tugunlar uchun katta ${ displaystyle i}$ boshqa barcha tugunlarga yaqin (ya'ni kichik kechikish mavjud) ${ displaystyle lambda _ {i} (j)}$ Barcha uchun ${ displaystyle j}$)

${ displaystyle C_ {C} (i, t) = { frac {N-1} { sum _ {j not = i} { lambda _ {i, t} (j)}}}}$

• Markazlik o'rtasida ko'pincha boshqa juft tugunlar orasidagi eng kichik kechikish yo'llarining bir qismi bo'lgan tugunlar uchun katta. Bu eng kichik kechikish yo'llari sonining nisbati sifatida aniqlanadi ${ displaystyle j}$ va ${ displaystyle k}$ o'tib ketadi ${ displaystyle i}$ dan kechikish yo'llarining umumiy soniga ${ displaystyle j}$ va ${ displaystyle k}$

${ displaystyle C_ {B} (i, t) = { frac { sum _ {i not = j not = k} { nu _ {i} (j, k)}} { sum _ { i not = j not = k} { nu _ {(} j, k)}}}}$

Kechikish vaqtining o'zgaruvchanligi, xususan, barcha tugun juftliklari uchun abadiylikka aylanishi, vaqt ishlatilgan tarmoq oralig'ining oxiriga yaqinlashganda, muqobillik o'lchovini foydali qiladi. Samaradorlik Buning o'rniga kechikishning o'zaro ta'siridan foydalanadi, shuning uchun samaradorlik farqlash o'rniga nolga yaqinlashadi. Samaradorlik uchun yuqori ko'rsatkichlar tarmoqdagi ko'proq markaziy tugunlarga to'g'ri keladi.

${ displaystyle C_ {E} (i, t) = { frac {1} {N-1}} sum _ {j not = i} { frac {1} { lambda _ {i, t} (j)}}}$

Vaqtinchalik naqshlar

Vaqt o'zgaruvchan tarmoq, tarmoqning aniq vaqtga bog'liq xususiyatlarini tahlil qilishga imkon beradi. Turli xil ma'lumotlardan takroriy va doimiy aloqalarni ko'p jihatdan olish mumkin. Bu doimiy izlanishlar sohasi.

• Tizimning xarakterli vaqtlarini o'zgaruvchida aniq o'zgarishlarni izlash orqali topish mumkin, masalan erishish darajasi. Masalan, kechikishni hisoblashda barcha tugunlarda faqat kutish vaqtini cheklash mumkin bo'lsa, natijada erishish darajasida qiziqarli naqshlarni topish mumkin. Mobil qo'ng'iroqlar tarmog'i uchun kamida ikki kunga kechiktirishga yo'l qo'yilsa, ulanish koeffitsienti keskin o'sishi aniqlandi va aviakompaniya tarmog'i uchun xuddi shunday ta'sir 30 daqiqada aniqlandi.^[17] Bundan tashqari, vaqtinchalik tarmoqning xarakterli vaqt o'lchovi eng qisqa yo'l davomiyligini taqsimlash usuli bilan berilgan. Ushbu taqsimotni tarmoqdagi barcha tugun juftliklari orasidagi erishish imkoniyati yordamida hisoblash mumkin.^[15]
• Doimiy naqshlar - bu tizimda tez-tez takrorlanadigan naqshlar. Ularni o'rtacha har xilligi bo'yicha topish mumkin ${ displaystyle Delta t}$ tizimning vaqt oralig'ida va belgilangan chegarada takrorlanadigan naqshlarni izlash.^[18]
• Motiflar - bu tizimda kutilgan tez-tez uchraydigan o'ziga xos vaqtinchalik naqshlar. Vaqt bo'yicha o'zgarib turadigan Facebook-dagi devor nashrlarining tarmog'i, masalan, tasodifiy tarmoq uchun kutish mumkin bo'lgan zanjirlar, yulduzlar va oldinga va orqaga o'zaro ta'sirlarning yuqori chastotasiga ega.^[19]
• Yo'qolgan havolalarni aniqlash

Dinamika

Vaqt o'zgaruvchan tarmoqlar tarmoqlarda dinamik jarayonlarning mutlaqo yangi o'lchamlarini tahlil qilishga imkon beradi. Tarmoq va jarayon evolyutsiyasining vaqt o'lchovlari o'xshash bo'lgan hollarda, vaqt o'zgaruvchan tarmoqlarning vaqtinchalik tuzilishi jarayonning tarmoq orqali tarqalishiga keskin ta'sir ko'rsatadi.

Burstness

Ikkala ketma-ket hodisalar orasidagi vaqt, alohida tugun yoki bog'lanish uchun, deyiladi voqealararo vaqt. Ning taqsimlanishi voqealararo vaqtlar tobora ko'payib borayotgan muhim, real, vaqt o'zgaruvchan tarmoqlarning soni aniqlandi yorilgan, hodisalararo vaqtlar juda heterojen degan ma'noni anglatadi - ular a og'ir dumaloq taqsimot. Bu faollikning uzoqroq vaqtlari bilan ajralib turadigan portlashlar natijasida paydo bo'ladigan faollashuv uslubiga aylanadi.^[20]

Voqealar oralig'idagi bo'shliq tarmoqlarda tarqaladigan jarayonlarni keskin sekinlashtirishi mumkin,^[21] bu kasallik, ma'lumotlar, g'oyalar va kompyuter viruslarining tarqalishiga ta'sir qiladi. Shu bilan birga, yorilish tarqalish jarayonlarini tezlashtirishi mumkin va boshqa tarmoq xususiyatlari ham tarqalish tezligiga ta'sir qiladi.^[22] Haqiqiy vaqt o'zgaruvchan tarmoqlar, voqealararo vaqt taqsimotiga ega bo'lishiga qaramay, tarqalish jarayonlarini rag'batlantirishi mumkin.^[23]

Burstness hodisa oralig'idagi har qanday ketma-ketlik uchun empirik miqdorni hisoblash mumkin, ${ displaystyle tau}$, ketma-ketlikni a tomonidan yaratilgan bilan taqqoslash orqali Poisson jarayoni. Ning nisbati standart og'ish, ${ displaystyle sigma}$, uchun anglatadi, ${ displaystyle m}$, Puasson jarayonining 1. bu o'lchov solishtiradi ${ displaystyle sigma _ { tau} / m _ { tau} }$ 1 ga.

${ displaystyle B = { frac { sigma _ { tau} / m _ { tau} -1} { sigma _ { tau} / m _ { tau} +1}}}$

Burstness -1 dan 1 gacha o'zgarib turadi. B = 1 maksimal yorilgan ketma-ketlikni bildiradi, B = 0 Puasson taqsimotini bildiradi va B = -1 davriy ketma-ketlikni bildiradi.^[24]

Shuningdek qarang

• Murakkab yuqumli kasallik
• Kompleks tarmoq
• Epidemik model
• Yo'naltirilgan perkolatsiya
• Eksponentli tasodifiy grafik modellari
• Havolaga yo'naltirilgan imtiyozli biriktirma
• Miqyosiz tarmoq
• Perkolyatsiya nazariyasi

Adabiyotlar