ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
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 15: | Line 15: | ||
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | ||
एक निश्चित ग्राफॉन पर | एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल <math>W</math> कभी-कभी निरूपित किया जाता है <math>\mathbb{G}(n, W)</math>, | ||
यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | ||
ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक ग्राफ है। | ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक ग्राफ है। | ||
| Line 32: | Line 32: | ||
# सेटिंग <math>W</math> के बराबर <math>p_{lm}</math> पर <math>(l,m)^{\text{th}}</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>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 /> | ||
=== संयुक्त रूप से विनिमेय आसन्न | === संयुक्त रूप से विनिमेय आसन्न आव्यूह === | ||
<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>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>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_{G_n})</math>. | ||
यदि ये ग्राफ़ अभिसरित होते हैं ( | यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | ||
यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन (ग्राफ़ फलन के लिए छोटा) की परिभाषा को प्रेरित करता है <math>W:[0,1]^{2}\to[0,1]</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>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> अन्यथा। | ||
==== पूर्ण द्विदलीय ग्राफॉन ==== | ==== पूर्ण द्विदलीय ग्राफॉन ==== | ||
| Line 97: | Line 97: | ||
यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं | यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं | ||
और दूसरे भाग के शीर्षों को अंत में रखकर, | और दूसरे भाग के शीर्षों को अंत में रखकर, | ||
की निकटता | की निकटता आव्यूह <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</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_{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> बड़ा हो जाता है, | ||
| Line 137: | Line 137: | ||
उदाहरण के लिए, यदि हम बेतरतीब ढंग से एक Erdős–Rényi मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के तहत इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बड़े के लिए उच्च संभावना है <math>n</math>. | उदाहरण के लिए, यदि हम बेतरतीब ढंग से एक Erdős–Rényi मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के तहत इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बड़े के लिए उच्च संभावना है <math>n</math>. | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़_एडिट_डिस्टेंस। हालाँकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी है <math>\tfrac{1}{2}</math>. | ||
दो प्राकृतिक मेट्रिक्स हैं जोसघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा व्यवहार करते हैं जो हम चाहते हैं। | दो प्राकृतिक मेट्रिक्स हैं जोसघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा व्यवहार करते हैं जो हम चाहते हैं। | ||
| Line 181: | Line 181: | ||
दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर। | दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर। | ||
क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं, | क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं, | ||
उनकी दूरी को मापने का एक तरीका सबसेट तक सीमित करना है <math>X, Y</math> वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए | उनकी दूरी को मापने का एक तरीका सबसेट तक सीमित करना है <math>X, Y</math> वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए अश्रि की संख्या की तुलना करें <math>e_G(X,Y)</math> से <math>X</math> को <math>Y</math> में <math>G</math> अश्रि की संख्या के लिए <math>e_H(X,Y)</math> बीच में <math>X</math> और <math>Y</math> में <math>H</math>. | ||
यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं ( | यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं। | ||
रेखांकन के किसी भी जोड़े के लिए दूरी की इस धारणा की प्रारंभिक औपचारिकता के रूप में <math>G</math> और <math>H</math> उसी शीर्ष सेट पर <math>V</math> आकार का <math>|V| = n</math>, लेबल की गई कट दूरी को परिभाषित करें <math>G</math> और <math>H</math> होना | रेखांकन के किसी भी जोड़े के लिए दूरी की इस धारणा की प्रारंभिक औपचारिकता के रूप में <math>G</math> और <math>H</math> उसी शीर्ष सेट पर <math>V</math> आकार का <math>|V| = n</math>, लेबल की गई कट दूरी को परिभाषित करें <math>G</math> और <math>H</math> होना | ||
| Line 202: | Line 202: | ||
इस दूरी के माप में अभी भी एक प्रमुख सीमा है: यह गैर-शून्य दूरी को दो आइसोमोर्फिक ग्राफों को निर्दिष्ट कर सकता है। | इस दूरी के माप में अभी भी एक प्रमुख सीमा है: यह गैर-शून्य दूरी को दो आइसोमोर्फिक ग्राफों को निर्दिष्ट कर सकता है। | ||
यह सुनिश्चित करने के लिए कि आइसोमॉर्फिक ग्राफ़ में दूरी शून्य है, हमें | यह सुनिश्चित करने के लिए कि आइसोमॉर्फिक ग्राफ़ में दूरी शून्य है, हमें वर्टेक्स के सभी संभावित रीलेबलिंग पर न्यूनतम कट मानदंड की गणना करनी चाहिए। | ||
यह कट दूरी की निम्नलिखित परिभाषा को प्रेरित करता है। | यह कट दूरी की निम्नलिखित परिभाषा को प्रेरित करता है। | ||
| Line 299: | Line 299: | ||
उदाहरण के लिए, | उदाहरण के लिए, | ||
सिडोरेंको का अनुमान [[चरम ग्राफ सिद्धांत]] में एक बड़ी खुली समस्या है, जो किसी भी ग्राफ के लिए दावा करता है <math>G</math> पर <math>n</math> औसत डिग्री के साथ शिखर <math>pn</math> (कुछ के लिए <math>p\in [0,1]</math>) और द्विदलीय ग्राफ <math>H</math> पर <math>v</math> शिखर और <math>e</math> | सिडोरेंको का अनुमान [[चरम ग्राफ सिद्धांत]] में एक बड़ी खुली समस्या है, जो किसी भी ग्राफ के लिए दावा करता है <math>G</math> पर <math>n</math> औसत डिग्री के साथ शिखर <math>pn</math> (कुछ के लिए <math>p\in [0,1]</math>) और द्विदलीय ग्राफ <math>H</math> पर <math>v</math> शिखर और <math>e</math> अश्रि, ग्राफ समरूपता की संख्या से <math>H</math> को <math>G</math> कम से कम है <math>p^{e}n^{v}</math>.{{r|sidorenko}} | ||
चूंकि यह मात्रा लेबल किए गए सबग्राफ की अपेक्षित संख्या है <math>H</math> एक यादृच्छिक ग्राफ में <math>G(n,p)</math>, | चूंकि यह मात्रा लेबल किए गए सबग्राफ की अपेक्षित संख्या है <math>H</math> एक यादृच्छिक ग्राफ में <math>G(n,p)</math>, | ||
अनुमान की व्याख्या दावे के रूप में की जा सकती है | अनुमान की व्याख्या दावे के रूप में की जा सकती है | ||
Revision as of 17:17, 17 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक किनारे सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा