ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| (20 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
[[File:Exchangeable random graph from graphon.png|thumb|300px|एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ <math>n</math> स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है <math>k \in \{1,\dotsc,n\}</math> एक अव्यक्त यादृच्छिक चर | [[File:Exchangeable random graph from graphon.png|thumb|300px|एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ <math>n</math> स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है <math>k \in \{1,\dotsc,n\}</math> एक अव्यक्त यादृच्छिक चर | ||
<math>U_{k} \sim \mathrm{U}(0,1)</math> (ऊर्ध्वाधर अक्ष के साथ मान) और | <math>U_{k} \sim \mathrm{U}(0,1)</math> (ऊर्ध्वाधर अक्ष के साथ मान) और | ||
प्रत्येक शीर्ष सहित <math>(k,l)</math> संभावना के साथ स्वतंत्र रूप से <math>f(U_{k},U_{l})</math>. | |||
उदाहरण के लिए, किनारा <math>(3,5)</math> (हरा, बिंदीदार) संभावना के साथ | उदाहरण के लिए, किनारा <math>(3,5)</math> (हरा, बिंदीदार) संभावना के साथ सम्मलित है | ||
<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>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और [[विनिमेय यादृच्छिक चर]] यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल [[लगभग निश्चित रूप से]] सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं। | |||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
एक ग्राफॉन एक सममित मापने योग्य कार्य है <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>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से सम्मलित है <math>W(u_{i},u_{j})</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>विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से | यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि <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>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> ब्लॉक, और | ||
# सेटिंग <math>W</math> | # सेटिंग <math>W</math> <math>p_{lm}</math>के बराबर है <math>(l,m)^{\text{th}}</math> ब्लाक पर | ||
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल | परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल <math>k</math> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | ||
हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं <math>k</math> मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ <math>p_{ll}</math> क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा <math>(l,l)</math> और <math>(m,m)</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 /> | ||
=== संयुक्त रूप से विनिमेय आसन्न | === संयुक्त रूप से विनिमेय आसन्न आव्यूह === | ||
<math>n</math> आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक <math>n\times n</math> सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ ''n'' x ''n'' उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें <math>G_{n}</math> उत्पन्न करने की अनुमति देता है एक <math>G_{n-1}</math> नोड जोड़कर और अश्रि का नमूना <math>(j,n)</math> <math>j<n</math> के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक <math>(X_{ij})</math> अनंत सममित सरणियों के रूप में परिभाषित किया जाता है। | |||
शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय | शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; अर्थात यादृच्छिक आव्यूह संतोषजनक है: | ||
: <math> (X_{ij}) \ \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})</math> | : <math> (X_{ij}) \ \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})</math> | ||
सभी क्रमपरिवर्तन के लिए <math>\sigma</math> प्राकृतिक संख्याओं की, जहाँ <math>\overset{d}{=}</math> का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है। | सभी क्रमपरिवर्तन के लिए <math>\sigma</math> प्राकृतिक संख्याओं की, जहाँ <math>\overset{d}{=}</math> का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है। | ||
विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न | विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष स्थितिा है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह <math>(X_{ij})</math> द्वारा उत्पन्न होता है: | ||
# नमूना <math>u_{j}\sim U[0,1]</math> स्वतंत्र रूप से | # नमूना <math>u_{j}\sim U[0,1]</math> स्वतंत्र रूप से है। | ||
# <math>X_{ij}=X_{ji}=1</math> संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से <math>W(u_i,u_j),</math> | # <math>X_{ij}=X_{ji}=1</math> संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से <math>W(u_i,u_j),</math> | ||
जहाँ <math>W:[0,1]^2\to[0,1]</math> एक (संभवतः यादृच्छिक) ग्राफॉन है। यही है, एक यादृच्छिक ग्राफ़ मॉडल में संयुक्त रूप से विनिमेय आसन्न आव्यूह होता है यदि यह केवल कुछ ग्राफ़ॉन के संदर्भ में परिभाषित संयुक्त रूप से विनिमेय यादृच्छिक ग्राफ़ मॉडल है। | |||
=== ग्राफॉन अनुमान === | === ग्राफॉन अनुमान === | ||
पहचानने योग्य मुद्दों के कारण, ग्राफॉन | पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, <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> | ||
== विश्लेषणात्मक सूत्रीकरण == | == विश्लेषणात्मक सूत्रीकरण == | ||
कोई भी ग्राफ <math>n</math> | कोई भी ग्राफ <math>n</math> वर्टेक्स <math>\{1, 2, \dots, n\}</math> इसके आसन्न आव्यूह के साथ पहचाना जा सकता है <math>A_G</math>. | ||
यह | यह आव्यूह एक स्टेपफंक्शन से मेल खाता है <math>W_G : [0,1]^2 \to [0, 1]</math>, | ||
विभाजन द्वारा परिभाषित <math>[0,1]</math> अंतराल में | विभाजन द्वारा परिभाषित <math>[0,1]</math> अंतराल में | ||
<math>I_1, I_2, \dots, I_n</math> ऐसा है कि <math>I_j</math> इंटीरियर है | <math>I_1, I_2, \dots, I_n</math> ऐसा है कि <math>I_j</math> इंटीरियर है | ||
| Line 66: | Line 66: | ||
<math>(i,j)^{\text{th}}</math> | <math>(i,j)^{\text{th}}</math> | ||
का प्रवेश <math>A_G</math>. | का प्रवेश <math>A_G</math>. | ||
यह | यह फलन <math>W_G</math> ग्राफ का संबद्ध ग्राफॉन <math>G</math> से है। | ||
सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | ||
कार्यों के सीमित | कार्यों के सीमित संचालन पर विचार करके अनुक्रम के संचालन को सीमित करना <math>(W_{G_n})</math>. | ||
यदि ये ग्राफ़ अभिसरित होते हैं ( | यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | ||
यह एक सममित मापने योग्य | यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन (ग्राफ़ फलन के लिए छोटा) की परिभाषा को प्रेरित करता है <math>W:[0,1]^{2}\to[0,1]</math> | ||
रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। | रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। | ||
यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।<ref name=Lovasz:2013 /> | यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।<ref name=Lovasz:2013 /> | ||
| Line 80: | Line 80: | ||
==== लगातार ग्राफॉन ==== | ==== लगातार ग्राफॉन ==== | ||
<math>(G_n)</math> एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए <math>G_n = G(n,p)</math> कुछ निश्चित पैरामीटर के साथ <math>p</math>. | |||
सहज रूप से, जैसा <math>n</math> अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के | सहज रूप से, जैसा <math>n</math> अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के शीर्ष घनत्व द्वारा निर्धारित की जाती है। | ||
ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है <math>W(x,y)\equiv p</math>, जो उपरोक्त अंतर्ज्ञान को | ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है <math>W(x,y)\equiv p</math>, जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है। | ||
==== | ==== अर्द्ध ग्राफॉन ==== | ||
<math>(H_n)</math> [[आधा ग्राफ|अर्द्ध ग्राफ]] का क्रम लीजिए अर्द्ध ग्राफ, लेने से परिभाषित <math>H_n</math> द्विदलीय ग्राफ पर होना <math>2n</math> वर्टेक्स <math>u_1, u_2, \dots, u_n</math> और <math>v_1, v_2, \dots, v_{n}</math> ऐसा है कि <math>u_i</math> लगी हुई है <math>v_j</math> ठीक है जब <math>i\le j</math> है. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब | |||
निकटतम आव्यूह <math>A_{H_n}</math>अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं। | |||
उदाहरण के लिए, आसन्न | उदाहरण के लिए, आसन्न आव्यूह <math>H_{3}</math> द्वारा दिया गया है: | ||
<math display=block> \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0\end{bmatrix}.</math> | <math display=block> \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0\end{bmatrix}.</math> | ||
जैसा <math>n</math> | जैसा <math>n</math> बृहत् हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं। | ||
इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> | इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> अर्द्ध ग्राफॉन में परिवर्तित हो जाता है <math>W</math> द्वारा परिभाषित <math>W(x,y) = 1</math> जब <math>|x-y| \ge 1/2</math> और <math>W(x,y) = 0</math>। | ||
==== पूर्ण द्विदलीय ग्राफॉन ==== | ==== पूर्ण द्विदलीय ग्राफॉन ==== | ||
क्रम लीजिए <math>(K_{n,n})</math> समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ | क्रम लीजिए <math>(K_{n,n})</math> समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का क्रम लीजिए। | ||
यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं | यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं | ||
और दूसरे भाग के शीर्षों को अंत में रखकर, | और दूसरे भाग के शीर्षों को अंत में रखकर, | ||
निकटतम आव्यूह <math>(K_{n,n})</math> एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। | |||
उदाहरण के लिए, आसन्न | उदाहरण के लिए, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है: | ||
<math display=block> \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}.</math> | <math display=block> \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}.</math> | ||
जैसा <math>n</math> बड़ा हो जाता है, आसन्न | जैसा <math>n</math> बड़ा हो जाता है, आसन्न आव्यूह की यह ब्लॉक संरचना स्थिर रहती है, | ||
जिससे कि रेखांकन का यह क्रम पूर्ण द्विदलीय ग्राफॉन में परिवर्तित हो जाए <math>W</math> | |||
द्वारा परिभाषित <math>W(x,y) = 1</math> जब कभी भी <math>\min(x,y) \le 1/2</math> और <math>\max(x,y) > 1/2</math>, और सेटिंग <math>W(x,y) = 0</math> | द्वारा परिभाषित <math>W(x,y) = 1</math> जब कभी भी <math>\min(x,y) \le 1/2</math> और <math>\max(x,y) > 1/2</math>, और सेटिंग <math>W(x,y) = 0</math> अन्यथा हो। | ||
यदि हम इसके | यदि हम इसके अतिरिक्त शीर्षों को आदेश दें <math>K_{n,n}</math> भागों के बीच बारी-बारी से, | ||
आसन्न | आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। | ||
उदाहरण के लिए, इस आदेश के | उदाहरण के लिए, इस आदेश के अनुसार, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है: | ||
<math display=block> \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}.</math> जैसा <math>n</math> बड़ा हो जाता है, | <math display=block> \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}.</math> जैसा <math>n</math> बड़ा हो जाता है, | ||
आसन्न | आसन्न आव्युह बेहतर और बेहतर शतरंजबोर्ड बन जाते हैं। | ||
इस | इस संचालन के बावजूद, हम अभी भी चाहते हैं की सीमा <math>(K_{n,n})</math> अद्वितीय हो और परिणाम उदाहरण 3 से ग्राफॉन में हो। | ||
इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए। | इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए। | ||
==== ए-यादृच्छिक रेखांकन की सीमा ==== | ==== ए-यादृच्छिक रेखांकन की सीमा ==== | ||
एक यादृच्छिक क्रम | एक यादृच्छिक क्रम <math>(G_n)</math> ग्राफॉन का#सांख्यिकीय_सूत्रीकरण लें। <math>W</math> आहरण आरेख द्वारा यादृच्छिक रेखांकन <math>G_n \sim \mathbb{G}(n, W)</math> कुछ निश्चित ग्राफॉन के लिए <math>W</math>. | ||
फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप | फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप से है। | ||
=== ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | === ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | ||
दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math> | दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ <math>G</math> सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>W</math> के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, शीर्ष का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। <math>G</math> अभिन्न द्वारा दिया गया है: | ||
<math display=block> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y .</math> | <math display=block> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y .</math> | ||
यह है क्योंकि <math>W</math> है <math>\{0,1\}</math>-मूल्यवान, और प्रत्येक किनारा <math>(i, j)</math> | यह है क्योंकि <math>W</math> है <math>\{0,1\}</math>-मूल्यवान, और प्रत्येक किनारा <math>(i, j)</math> | ||
में <math>G</math> एक क्षेत्र से मेल खाता है <math>I_i \times I_j</math> | में <math>G</math> एक क्षेत्र से मेल खाता है <math>I_i \times I_j</math> | ||
क्षेत्र के <math>1/n^2</math> | क्षेत्र के <math>1/n^2</math> जहाँ <math>W</math> बराबर होती है <math>1</math> के। | ||
इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या में <math>G</math> के बराबर | इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या में <math>G</math> के बराबर है। | ||
<math display=block> \frac 16 \int_{0}^1 \int_0^1 \int_0^1 W(x,y)W(y,z)W(z,x) \; \mathrm{d}x \, \mathrm{d}y \, \mathrm{d}z .</math> | <math display=block> \frac 16 \int_{0}^1 \int_0^1 \int_0^1 W(x,y)W(y,z)W(z,x) \; \mathrm{d}x \, \mathrm{d}y \, \mathrm{d}z .</math> | ||
| Line 133: | Line 133: | ||
दो ग्राफ़ के बीच की दूरी को मापने के कई अलग-अलग तरीके हैं। | दो ग्राफ़ के बीच की दूरी को मापने के कई अलग-अलग तरीके हैं। | ||
यदि हम | यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | ||
तो हमें अपना ध्यान उन | तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | ||
उदाहरण के लिए, यदि हम | |||