ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (9 intermediate revisions by 3 users not shown) | |||
| Line 2: | Line 2: | ||
<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>(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>. ऊपरी बाएँ | ||
| Line 9: | Line 9: | ||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. | एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. सामान्यत: एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है: | ||
# प्रत्येक शीर्ष <math>j</math> ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है <math>u_{j}\sim U[0,1]</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>। | ||
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | ||
| 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>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 /> | ||
| Line 42: | Line 42: | ||
<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>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:[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> द्वारा प्रेरित प्रायिकता आव्यूह का अनुमान | पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, <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 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> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | ||
| Line 87: | Line 87: | ||
<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>(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>A_{H_n}</math>अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं। | ||
उदाहरण के लिए, आसन्न आव्यूह <math>H_{3}</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> | ||
| Line 98: | Line 98: | ||
और दूसरे भाग के शीर्षों को अंत में रखकर, | और दूसरे भाग के शीर्षों को अंत में रखकर, | ||
निकटतम आव्यूह <math>(K_{n,n})</math> एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। | निकटतम आव्यूह <math>(K_{n,n})</math> एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। | ||
उदाहरण के लिए, आसन्न आव्यूह <math>K_{2,2}</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> बड़ा हो जाता है, | ||
| Line 116: | Line 116: | ||
==== ए-यादृच्छिक रेखांकन की सीमा ==== | ==== ए-यादृच्छिक रेखांकन की सीमा ==== | ||
एक यादृच्छिक क्रम <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 \sim \mathbb{G}(n, W)</math> कुछ निश्चित ग्राफॉन के लिए <math>W</math>. | ||
फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप | फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप से है। | ||
=== ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | === ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | ||
| Line 124: | Line 124: | ||
यह है क्योंकि <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>W</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 135: | Line 135: | ||
यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | ||
तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | ||
उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के | उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के अनुसार इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बृहत् <math>n</math> के लिए उच्च संभावना है। | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। चूंकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी <math>\tfrac{1}{2}</math> है। | ||
दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | ||
| Line 144: | Line 144: | ||
चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | ||
इसके | इसके अतिरिक्त, दोनों आव्युह के अनुसार लिमिट ऑब्जेक्ट ग्राफॉन बन जाते हैं। | ||
अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन चुंग अर्ध-यादृच्छिक ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।{{r|qrandom}} | अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन चुंग अर्ध-यादृच्छिक ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।{{r|qrandom}} | ||
| Line 150: | Line 150: | ||
दो रेखांकन के बीच की दूरी को मापने का एक तरीका <math>G</math> और <math>H</math> के सापेक्ष सबग्राफ गणनांक की तुलना करना है। | दो रेखांकन के बीच की दूरी को मापने का एक तरीका <math>G</math> और <math>H</math> के सापेक्ष सबग्राफ गणनांक की तुलना करना है। | ||
अर्थात प्रत्येक ग्राफ के लिए हम <math>F</math> की प्रतियों की संख्या की तुलना कर सकते हैं <math>F</math> में <math>G</math> और <math>F</math> में <math>H</math>। | |||
यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | ||
सबग्राफ से सीधे | सबग्राफ से सीधे डीलिंग के अतिरिक्त, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है। | ||
इस परिदृश्य में बृहत्,सघन ग्राफ से | इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है, | ||
सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ | सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है। | ||
दो रेखांकन दिए गए हैं <math>F</math> और <math>G</math>, | दो रेखांकन दिए गए हैं <math>F</math> और <math>G</math>, [[समरूपता घनत्व]] <math>t(F, G)</math> का <math>F</math> में <math>G</math> से ग्राफ़ समरूपता की संख्या के रूप <math>F</math> को <math>G</math> में परिभाषित किया गया है। | ||
[[समरूपता घनत्व]] <math>t(F, G)</math> का <math>F</math> में <math>G</math> से ग्राफ़ समरूपता की संख्या के रूप | दूसरे शब्दों में, <math>t(F,G)</math> के शीर्ष से यादृच्छिक रूप से चुने गए मानचित्र की प्रायिकता है <math>F</math> के शिखर तक <math>G</math> सन्निकट शीर्षों को अंदर भेजता है <math>F</math> सन्निकट शीर्षों में <math>G</math> है। | ||
दूसरे शब्दों में, <math>t(F,G)</math> के शीर्ष से यादृच्छिक रूप से चुने गए मानचित्र की प्रायिकता है <math>F</math> के शिखर तक <math>G</math> सन्निकट शीर्षों को अंदर भेजता है <math>F</math> सन्निकट शीर्षों में <math>G</math> | |||
ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ||
दरअसल, एक ग्राफ | दरअसल, एक ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W_G</math> और दुसरी <math>F</math>, अपने पास है: | ||
<math display=block> t(F, G) = \int \prod_{(i,j)\in E(F)} W_G(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | <math display=block> t(F, G) = \int \prod_{(i,j)\in E(F)} W_G(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | ||
जहां | जहां अविभाज्य बहुआयामी है, यूनिट अतिविम पर लिया गया है <math>[0,1]^{V(F)}</math>. | ||
यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त | यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त एकीकृत के बराबर होता है <math>1</math>. | ||
फिर हम | फिर हम समरूपता घनत्व की परिभाषा को यादृच्छिक ग्राफॉन <math>W</math> तक बढ़ा सकते हैं, एक ही अभिन्न और परिभाषित करने का उपयोग करके: | ||
<math display=block> t(F, W) = \int \prod_{(i,j)\in E(F)} W(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | |||
किसी भी ग्राफ के लिए <math>F</math> | किसी भी ग्राफ के लिए <math>F</math> है। | ||
इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए | इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए <math>F</math> वाम-अभिसरण है, समरूपता घनत्व का क्रम <math>\left(t(F, G_n)\right)</math> अभिसरण। | ||
चूंकि अकेले परिभाषा से स्पष्ट नहीं है, यदि <math>(G_n)</math> इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन सम्मलित होता है <math>W</math> ऐसा है कि हर ग्राफ के लिए <math>F</math>, अपने पास है: | |||
<math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W) </math> | <math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W) </math> | ||
इसके साथ ही। | इसके साथ ही। | ||
| Line 179: | Line 178: | ||
दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर। | दो ग्राफ लीजिए <math>G</math> और <math>H</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>G</math> और <math>H</math> उसी शीर्ष सेट पर <math>V</math> आकार का <math>|V| = n</math>, | रेखांकन के किसी भी जोड़े के लिए दूरी की इस धारणा की प्रारंभिक औपचारिकता के रूप में <math>G</math> और <math>H</math> उसी शीर्ष सेट पर <math>V</math> आकार का <math>|V| = n</math>, <math>G</math> और <math>H</math> के बीच लेबल कट दूरी को परिभाषित करें: | ||
d_\square(G, H) = \frac 1{n^2} \max_{X, Y\subseteq V}\left|e_G(X,Y) - e_H(X,Y)\right|.</math> | d_\square(G, H) = \frac 1{n^2} \max_{X, Y\subseteq V}\left|e_G(X,Y) - e_H(X,Y)\right|.</math> | ||
दूसरे शब्दों में, लेबल की गई कट दूरी बीच के शीर्ष घनत्व की अधिकतम विसंगति को | दूसरे शब्दों में, लेबल की गई कट दूरी बीच के शीर्ष घनत्व की अधिकतम विसंगति को <math>G</math> और <math>H</math> कूटबद्ध करती है। हम शीर्ष के घनत्व को व्यक्त करके इस अवधारणा को ग्राफॉन के लिए सामान्यीकृत कर सकते हैं <math> \tfrac 1{n^2} e_G(X, Y) </math> संबंधित ग्राफॉन के संदर्भ में <math>W_G</math>, समानता दे रहा है: | ||
हम शीर्ष के घनत्व को व्यक्त करके इस अवधारणा को ग्राफॉन के लिए सामान्यीकृत कर सकते हैं <math> \tfrac 1{n^2} e_G(X, Y) </math> संबंधित ग्राफॉन के संदर्भ में <math>W_G</math>, समानता दे रहा है | |||
<math display=block> d_\square(G, H) = \max_{X, Y\subseteq V} \left| \int_{I_X} \int_{I_Y} W_G(x, y) - W_H(x, y) \; \mathrm{d}x \, \mathrm{d}y \right| </math> | <math display=block> d_\square(G, H) = \max_{X, Y\subseteq V} \left| \int_{I_X} \int_{I_Y} W_G(x, y) - W_H(x, y) \; \mathrm{d}x \, \mathrm{d}y \right| </math> | ||
जहाँ <math>I_X, I_Y \subseteq [0, 1]</math> में <math>X</math> और <math>Y</math> वर्टेक्स के अनुरूप अंतराल के संघ हैं। ध्यान दें कि इस परिभाषा का तब भी उपयोग किया जा सकता है जब तुलना किए जा रहे ग्राफ़ एक शीर्ष सेट को साझा नहीं करते हैं। | |||
यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है। | यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है। | ||
परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए <math>f : [0,1]^2 \to \mathbb{R}</math>, के कट मानदंड को | परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए <math>f : [0,1]^2 \to \mathbb{R}</math>, के कट मानदंड को <math>f</math> मात्रा परिभाषित करें: | ||
<math display=block> \lVert f \rVert_\square = \sup_{S, T\subseteq [0,1]} \left| \int_{S} \int_{T} f(x,y) \; \mathrm{d}x \, \mathrm{d}y \right|</math> | <math display=block> \lVert f \rVert_\square = \sup_{S, T\subseteq [0,1]} \left| \int_{S} \int_{T} f(x,y) \; \mathrm{d}x \, \mathrm{d}y \right|</math> | ||
सभी औसत दर्जे का सबसेट ले लिया <math>S, T</math> इकाई अंतराल | सभी औसत दर्जे का सबसेट ले लिया <math>S, T</math> इकाई अंतराल है।{{r|Lovasz:2013}} | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
यह लेबल कट दूरी की हम | |||