ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| Line 5: | Line 5: | ||
<math>f(0.72,0.9)</math>; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं | <math>f(0.72,0.9)</math>; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं | ||
के मूल्य <math>(u_{3},u_{5})</math> और <math>(u_{5},u_{3})</math>. ऊपरी बाएँ | के मूल्य <math>(u_{3},u_{5})</math> और <math>(u_{5},u_{3})</math>. ऊपरी बाएँ | ||
पैनल ग्राफ प्राप्ति को आसन्न मैट्रिक्स के रूप में दिखाता है।]]ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक | पैनल ग्राफ प्राप्ति को आसन्न मैट्रिक्स के रूप में दिखाता है।]]ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन [[औसत दर्जे का]] कार्य है: <math>W:[0,1]^2\to[0,1]</math>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। घने रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और [[विनिमेय यादृच्छिक चर]] यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल [[लगभग निश्चित रूप से]] सघन ग्राफ़ को जन्म देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन मनमाना बड़े सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं। | ||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
| Line 11: | Line 11: | ||
एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है: | एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है: | ||
# प्रत्येक शीर्ष <math>j</math> ग्राफ का एक स्वतंत्र यादृच्छिक मान | # प्रत्येक शीर्ष <math>j</math> ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है <math>u_{j}\sim U[0,1]</math> | ||
# किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है <math>W(u_{i},u_{j})</math> | # किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है <math>W(u_{i},u_{j})</math>। | ||
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है अगर और केवल अगर इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है अगर और केवल अगर इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | ||
एक निश्चित ग्राफॉन पर आधारित मॉडल <math>W</math> कभी-कभी निरूपित किया जाता है <math>\mathbb{G}(n, W)</math>, | एक निश्चित ग्राफॉन पर आधारित मॉडल <math>W</math> कभी-कभी निरूपित किया जाता है <math>\mathbb{G}(n, W)</math>, | ||
यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | ||
ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक | ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक ग्राफ है। | ||
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि <math>W\neq0</math>विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से घने हैं।<ref name=Orbanz:Roy:2015 /> | यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि <math>W\neq0</math>विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से घने हैं।<ref name=Orbanz:Roy:2015 /> | ||
| Line 25: | Line 25: | ||
=== उदाहरण === | === उदाहरण === | ||
ग्राफॉन का सबसे सरल उदाहरण है <math>W(x,y)\equiv p</math> कुछ स्थिर के लिए <math>p\in[0,1]</math>. इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है <math>G(n,p)</math> जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है <math>p</math> | ग्राफॉन का सबसे सरल उदाहरण है <math>W(x,y)\equiv p</math> कुछ स्थिर के लिए <math>p\in[0,1]</math>. इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है <math>G(n,p)</math> जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है <math>p</math>। | ||
यदि हम इसके बजाय एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े | यदि हम इसके बजाय एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है: | ||
# इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | # इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | ||
| Line 33: | Line 33: | ||
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल है <math>k</math> सामुदायिक [[ स्टोकेस्टिक ब्लॉक मॉडल ]], एर्डोस-रेनी मॉडल का एक सामान्यीकरण। | परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल है <math>k</math> सामुदायिक [[ स्टोकेस्टिक ब्लॉक मॉडल ]], एर्डोस-रेनी मॉडल का एक सामान्यीकरण। | ||
हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं <math>k</math> मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ <math>p_{ll}</math> क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा <math>(l,l)</math> और <math>(m,m)</math> संभाव्यता के साथ स्वतंत्र रूप से शामिल है <math>p_{lm}</math> | हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं <math>k</math> मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ <math>p_{ll}</math> क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा <math>(l,l)</math> और <math>(m,m)</math> संभाव्यता के साथ स्वतंत्र रूप से शामिल है <math>p_{lm}</math>। | ||
कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में शामिल है।<ref name=Orbanz:Roy:2015 /> | कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में शामिल है।<ref name=Orbanz:Roy:2015 /> | ||
| Line 54: | Line 54: | ||
=== ग्राफॉन अनुमान === | === ग्राफॉन अनुमान === | ||
पहचानने योग्य मुद्दों के कारण, ग्राफॉन | पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है <math>W</math> या नोड अव्यक्त स्थिति <math>u_i,</math> और ग्राफॉन अनुमान की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य अनुमान लगाना है <math>W</math>एक समकक्ष वर्ग तक,<ref>{{Cite arXiv|last1=Wolfe|first1=Patrick J.|last2=Olhede|first2=Sofia C.|date=2013-09-23|title=गैर पैरामीट्रिक ग्राफॉन अनुमान|eprint=1309.5936|class=math.ST}}</ref><ref>{{Cite journal|last1=Choi|first1=David|last2=Wolfe|first2=Patrick J.|date=February 2014|title=अलग-अलग विनिमेय नेटवर्क डेटा का सह-क्लस्टरिंग|arxiv=1212.4093|journal=The Annals of Statistics|volume=42|issue=1|pages=29–63|doi=10.1214/13-AOS1173|s2cid=16291079|issn=0090-5364}}</ref> या द्वारा प्रेरित प्रायिकता मैट्रिक्स का अनुमान लगाएं <math>W</math>.<ref>{{Cite journal|last1=Gao|first1=Chao|last2=Lu|first2=Yu|last3=Zhou|first3=Harrison H.|date=December 2015|title=दर-इष्टतम ग्राफॉन अनुमान|journal=The Annals of Statistics|volume=43|issue=6|pages=2624–2652|doi=10.1214/15-AOS1354|issn=0090-5364|arxiv=1410.5837|s2cid=14267617}}</ref><ref>{{Cite journal|last1=Yuan|first1=Zhang|last2=Elizaveta|first2=Levina|last3=Ji|first3=Zhu|date=2017|title=नेबरहुड स्मूथिंग द्वारा नेटवर्क एज संभावनाओं का अनुमान लगाना|url=https://academic.oup.com/biomet/article-abstract/104/4/771/4158787?redirectedFrom=fulltext|journal=Biometrika|volume=104|issue=4|pages=771–783|doi=10.1093/biomet/asx042|issn=0006-3444}}</ref> | ||
| Line 72: | Line 72: | ||
यदि ये ग्राफ़ अभिसरित होते हैं (सीक्वेंस की सीमा#Metric_spaces की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | यदि ये ग्राफ़ अभिसरित होते हैं (सीक्वेंस की सीमा#Metric_spaces की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | ||
यह एक सममित मापने योग्य | यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन (ग्राफ़ फलन के लिए छोटा) की परिभाषा को प्रेरित करता है <math>W:[0,1]^{2}\to[0,1]</math> कौन | ||
रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। | रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। | ||
यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।<ref name=Lovasz:2013 /> | यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।<ref name=Lovasz:2013 /> | ||
Revision as of 11:38, 16 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक किनारे सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ मौजूद है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न मैट्रिक्स के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। घने रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को जन्म देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन मनमाना बड़े सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:
- प्रत्येक शीर्ष ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है
- किनारा संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है ।
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है अगर और केवल अगर इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर आधारित मॉडल कभी-कभी निरूपित किया जाता है , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ इस प्रकार कहा जाता है -यादृच्छिक ग्राफ है।
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से घने हैं।[1]
उदाहरण
ग्राफॉन का सबसे सरल उदाहरण है कुछ स्थिर के लिए . इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है