ग्रेडिएंट नेटवर्क

नेटवर्क विज्ञान में, एक प्रवणता नेटवर्क एक अप्रत्यक्ष "सब्सट्रेट" नेटवर्क का एक निर्देशित सबनेटवर्क है जहां प्रत्येक नोड (नेटवर्किंग) में एक संबंधित स्केलर क्षमता होती है और एक आउट-लिंक होता है जो नोड को उसके निकट में सबसे छोटी (या सबसे बड़ी) क्षमता के रूप में परिभाषित करता है। सब्सट्रेट नेटवर्क पर स्वयं और उसके निकट (ग्राफ सिद्धांत) के संघ के रूप में परिभाषित किया गया है।

परिभाषा

परिवहन एक निश्चित नेटवर्क $G=G(V,E)$ पर होता है। सब्सट्रेट ग्राफ कहा जाता है। इसमें N नोड्स हैं, $V=\{0,1,...,N-1\}$ और सेट किनारों की $E=\{(i,j)|i,j\in V\}$ एक नोड i दिए जाने पर, द्वारा इसके निकटतम के समुच्चय को G में S_i⁽¹⁾ = {j ∈ V | (i,j)∈ E} द्वारा परिभाषित कर सकते हैं।

File:Gradient network (sample diagram).jpg

प्रवणता नेटवर्क का एक उदाहरण।

आइए हम नोड्स V के सेट पर परिभाषित एक स्केलर फ़ील्ड, h = {h0, .., hN−1} पर भी विचार करें, ताकि प्रत्येक नोड i का एक स्केलर मान hi से जुड़ा हो।

एक नेटवर्क पर प्रवणता: ∇h_i(i, μ(i))

अर्थात् i से μ(i) तक निर्देशित किनारा, जहां μ(i) ∈S_i⁽¹⁾ ∪ {i}, और h_μ में अधिकतम मान ${h_{j}|j\in S_{i}^{(1)}\cup {i}}$ है.

प्रवणता नेटवर्क: ∇$G=$ ∇$G$ $(V,F)$

जहां F G पर प्रवणता किनारों का सेट है।

सामान्य तौर पर, स्केलर क्षेत्र प्रवाह, बाहरी स्रोतों और नेटवर्क पर डूबने के कारण समय पर निर्भर करता है। इसलिए, प्रवणता नेटवर्क ∇$G$ गतिशील होगा।

प्रेरणा और इतिहास

प्रवणता नेटवर्क की अवधारणा को सबसे पहले तोरोज्काई और बैस्लर (2004) द्वारा पेश किया गया था।

सामान्यतः, वास्तविक विश्व नेटवर्क (जैसे उद्धरण ग्राफ, इंटरनेट, सेलुलर चयापचय नेटवर्क, विश्वव्यापी हवाईअड्डा नेटवर्क), जो अधिकांश सूचना, कारों, बिजली, पानी, बलों आदि जैसे परिवहन संस्थाओं के लिए विकसित होते हैं, यह विश्व स्तर पर डिज़ाइन नहीं किए गए हैं; इसके अतिरिक्त, यह स्थानीय परिवर्तनों के माध्यम से विकसित होते हैं। उदाहरण के लिए, यदि इंटरनेट पर एक राउटर (कंप्यूटिंग) अधिकांश भीड़भाड़ वाला होता है और उसके कारण पैकेट खो जाते हैं या विलंबित हो जाते हैं, तो इसे कई परस्पर जुड़े नए राउटर से बदल दिया जाएगा।

इसके अतिरिक्त, यह प्रवाह अधिकांश स्केलर के स्थानीय प्रवणता द्वारा उत्पन्न या प्रभावित होता है। उदाहरण के लिए: विद्युत प्रवाह विद्युत क्षमता के प्रवणता द्वारा संचालित होता है। सूचना नेटवर्क में, नोड्स के गुण नोड से उसके पड़ोसियों को सूचना प्रसारित करने के तरीके में एक पूर्वाग्रह उत्पन्न करेंगे। इस विचार ने प्रवणता नेटवर्क का उपयोग करके नेटवर्क की प्रवाह दक्षता का अध्ययन करने के दृष्टिकोण को प्रेरित किया, जब प्रवाह नेटवर्क पर वितरित अदिश क्षेत्र के प्रवणता द्वारा संचालित होता है।

हाल ही में किए गए शोध नेटवर्क टोपोलॉजी और परिवहन की प्रवाह दक्षता के बीच संबंध की जांच करता है।

File:Gradient network with node pointing to largest increase.jpg

नोड I पर प्रवणता एक निर्देशित किनारा है जो नोड के पड़ोस में स्केलर क्षमता की सबसे बड़ी वृद्धि की ओर इशारा करता है।

प्रवणता नेटवर्क का इन-डिग्री वितरण

प्रवणता नेटवर्क में, नोड i, k_i ⁽ⁱⁿ⁾-डिग्री की प्रवणता किनारों की संख्या i है, और इन-डिग्री वितरण $R(l)=P\{k_{i}^{(in)}=l\}$ है.

प्रवणता नेटवर्क का डिग्री वितरण और सब्सट्रेट (बीए मॉडल)।

जब सब्सट्रेट G एक यादृच्छिक ग्राफ होता है और नोड्स की प्रत्येक जोड़ी प्रायिकता P (यानी एक एर्दो-रेनी यादृच्छिक ग्राफ) से जुड़ी होती है, तो स्केलर h_i i.i.d. होते हैं। (स्वतंत्र समान रूप से वितरित) R(l) के लिए सटीक अभिव्यक्ति द्वारा दिया गया है

$R(l)={\frac {1}{N}}\sum _{n=0}^{N-1}\mathrm {C} _{l}^{N-1-n}[1-p(1-p)]^{N-1-n-l}[p(1-p)^{n}]^{l}]$

सीमा में $N\to \infty$ तथा $P\to 0$, डिग्री वितरण शक्ति कानून बन जाता है

$R(l)\approx l^{-1}$

यह इस सीमा में दिखाता है, यादृच्छिक नेटवर्क का प्रवणता नेटवर्क स्केल-फ्री है।

इसके अतिरिक्त, यदि सब्सट्रेट नेटवर्क जी स्केल-फ्री है, जैसे कि बारबासी-अल्बर्ट मॉडल में, तो प्रवणता नेटवर्क भी जी के समान प्रतिनिधि के साथ शक्ति नियम का पालन करता है।

नेटवर्क पर भीड़

तथ्य यह है कि सब्सट्रेट नेटवर्क की टोपोलॉजी नेटवर्क संकुलन के स्तर को प्रभावित करती है, इसे एक सरल उदाहरण द्वारा स्पष्ट किया जा सकता है: यदि नेटवर्क में स्टार जैसी संरचना है, तो केंद्रीय नोड पर, प्रवाह संकुलित हो जाएगा क्योंकि केंद्रीय नोड को अन्य नोड्स से सभी प्रवाह को संभालना चाहिए। चूंकि, यदि नेटवर्क में रिंग जैसी संरचना है, क्योंकि प्रत्येक नोड समान भूमिका निभाता है, तो कोई प्रवाह संकुलन नहीं होता है।

File:Star network vs ring network.jpg

प्रवाह पर संरचना के प्रभाव का चित्रण।

इस धारणा के तहत कि प्रवाह नेटवर्क में प्रवणता द्वारा उत्पन्न होता है, नेटवर्क पर प्रवाह दक्षता को जैमिंग कारक (या संकुलन कारक) के माध्यम से वर्णित किया जा सकता है, जिसे निम्नानुसार परिभाषित किया गया है:

$J=1-\langle \langle {\frac {N_{\text{receive}}}{N_{\text{send}}}}\rangle _{h}\rangle _{\text{network}}=R(0)$

जहां N_receive प्रवणता प्रवाह प्राप्त करने वाले नोड्स की संख्या है और N_send प्रवणता प्रवाह भेजने वाले नोड्स की संख्या है।

J का मान 0 और 1 के बीच है; $J=0$ अर्थ कोई भीड़ नहीं, और $J=1$ अधिकतम भीड़ के समान है।

$N\to \infty$ की सीमा में, एर्डोस-रेनी रैंडम ग्राफ़ के लिए, भीड़ कारक बन जाता है है

$J(N,P)=1-{\frac {\ln N}{N\ln({\frac {1}{1-P}})}}\left[1+O({\frac {1}{N}})\right]\rightarrow 1.$

इस परिणाम से पता चलता है कि यादृच्छिक नेटवर्क उस सीमा में अधिकतम भीड़भाड़ वाले होते हैं।

इसके विपरीत, स्केल-फ्री नेटवर्क के लिए, जे किसी भी एन के लिए स्थिर है, जिसका अर्थ है कि स्केल-फ्री नेटवर्क अधिकतम जैमिंग के लिए प्रवण नहीं हैं।

File:Congestion coefficient for random graphs and scale-free networks.jpg

चित्र 7. यादृच्छिक रेखांकन और स्केल-मुक्त नेटवर्क के लिए संकुलन गुणांक।

भीड़भाड़ को नियंत्रित करने के उपाय

संचार नेटवर्क में एक समस्या यह समझ रही है कि भीड़भाड़ को कैसे नियंत्रित किया जाए और सामान्य और कुशल नेटवर्क कार्य को कैसे बनाए रखा जाए। ज़ोंगहुआ लियू एट अल (2006) ने दिखाया कि नेटवर्क में उच्च डिग्री वाले नोड्स पर भीड़ होने की संभावना अधिक होती है, और नोड्स के एक छोटे अंश (जैसे 3%) की संदेश-प्रक्रिया क्षमता को चुनिंदा रूप से बढ़ाने का एक कुशल दृष्टिकोण सभी नोड्स की क्षमता को बढ़ाने के साथ-साथ प्रदर्शन करने के लिए दिखाया गया है।

एना एल पास्टर वाई पियोन्ती एट अल (2008) ने दिखाया कि विश्राम संबंधी गतिशीलता नेटवर्क की भीड़ को कम कर सकते हैं।

पान एट अल। (2011) ने एक योजना में जैमिंग गुणों का अध्ययन किया जहां किनारों को नोड क्षमता के बीच स्केलर अंतर की शक्ति का भार दिया जाता है।

नीयू और पान (2016) ने दिखाया कि ग्रेडिएंट फील्ड और स्थानीय नेटवर्क टोपोलॉजी के बीच संबंध स्थापित करके भीड़भाड़ को कम किया जा सकता है।

<n(k)> डिग्री, पैकेट-प्रसंस्करण क्षमताओं के कार्य के रूप में औसत पैकेट संख्या है: 0 (सर्कल), 0.05 (वर्ग), 0.1 (सितारे)।

File:Comparison between enhanced and normal approaches (packet-processing capability).jpg

शीर्ष 3% डिग्री नोड्स की क्षमता में वृद्धि के साथ कुशल दृष्टिकोण (सर्कल) और सभी नोड्स की क्षमता के साथ सामान्य दृष्टिकोण (सितारों) के बीच तुलना। (ए) पैकेट-प्रोसेसिंग क्षमता 0.05 के बराबर है, (बी) पैकेट-प्रोसेसिंग क्षमता 0.1 के बराबर है। <n(k)> डिग्री के एक समारोह के रूप में औसत पैकेट संख्या है।

यह भी देखें

• नेटवर्क गतिकी
• नेटवर्क टोपोलॉजी
• क्वांटम जटिल नेटवर्क