ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 30: | Line 30: | ||
# इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | # इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | ||
# सेटिंग <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> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | ||
| Line 49: | Line 49: | ||
विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष स्थितिा है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह <math>(X_{ij})</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>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> | ||
| Line 107: | Line 107: | ||
यदि हम इसके अतिरिक्त शीर्षों को आदेश दें <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 & 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 126: | Line 126: | ||
क्षेत्र के <math>1/n^2</math> जहाँ <math>W</math> के बराबर होती है <math>1</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 137: | Line 137: | ||
उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के अनुसार इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बृहत् <math>n</math> के लिए उच्च संभावना है। | उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के अनुसार इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बृहत् <math>n</math> के लिए उच्च संभावना है। | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। चूंकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। चूंकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी <math>\tfrac{1}{2}</math> है। | ||
दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | ||
| Line 157: | Line 157: | ||
दो रेखांकन दिए गए हैं <math>F</math> और <math>G</math>, [[समरूपता घनत्व]] <math>t(F, G)</math> का <math>F</math> में <math>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>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> है। | ||
ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ||
| Line 165: | Line 165: | ||
जहां अविभाज्य बहुआयामी है, यूनिट अतिविम पर लिया गया है <math>[0,1]^{V(F)}</math>. | जहां अविभाज्य बहुआयामी है, यूनिट अतिविम पर लिया गया है <math>[0,1]^{V(F)}</math>. | ||
यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त एकीकृत के बराबर होता है <math>1</math>. | यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त एकीकृत के बराबर होता है <math>1</math>. | ||
फिर हम समरूपता घनत्व की परिभाषा को यादृच्छिक ग्राफॉन <math>W</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 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> | ||
| Line 181: | Line 181: | ||
यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <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>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> | ||
| Line 192: | Line 192: | ||
परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए <math>f : [0,1]^2 \to \mathbb{R}</math>, के कट मानदंड को <math>f</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}} | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
| Line 201: | Line 201: | ||
यह कट दूरी की निम्नलिखित परिभाषा को प्रेरित करता है। | यह कट दूरी की निम्नलिखित परिभाषा को प्रेरित करता है। | ||
परिभाषा 2. ग्राफॉन के किसी भी जोड़े के लिए <math>U</math> और <math>W</math>, उनकी कट दूरी को परिभाषित करें | परिभाषा 2. ग्राफॉन के किसी भी जोड़े के लिए <math>U</math> और <math>W</math>, उनकी कट दूरी को परिभाषित करें: | ||
<math display=block> \delta_\square(U, W) = \inf_{\varphi} \lVert U - W^\varphi \rVert_\square</math> | <math display=block> \delta_\square(U, W) = \inf_{\varphi} \lVert U - W^\varphi \rVert_\square</math> | ||
जहाँ <math>W^\varphi(x,y) = W(\varphi(x), \varphi(y))</math> की रचना है <math>W</math> नक्शे के साथ <math>\varphi</math>, और न्यूनतम को सभी अपरिवर्तनीय उपाय पर ले लिया जाता है माप-संरक्षण आक्षेपों को इकाई अंतराल से स्वयं में।{{r|whatis}} | जहाँ <math>W^\varphi(x,y) = W(\varphi(x), \varphi(y))</math> की रचना है <math>W</math> नक्शे के साथ <math>\varphi</math>, और न्यूनतम को सभी अपरिवर्तनीय उपाय पर ले लिया जाता है माप-संरक्षण आक्षेपों को इकाई अंतराल से स्वयं में।{{r|whatis}} | ||
| Line 275: | Line 275: | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
लेकिन इसका उपयोग मजबूत नियमितता परिणाम सिद्ध करने के लिए किया जा सकता है, जैसे कि ज़ेमेरीडी नियमितता लेम्मा#मजबूत नियमितता लेम्मा | लेकिन इसका उपयोग मजबूत नियमितता परिणाम सिद्ध करने के लिए किया जा सकता है, जैसे कि ज़ेमेरीडी नियमितता लेम्मा#मजबूत नियमितता लेम्मा है। | ||
ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math> | ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math> | ||
| Line 298: | Line 298: | ||
चूंकि यह मात्रा लेबल दिए गए सबग्राफ की अपेक्षित संख्या है <math>H</math> एक यादृच्छिक ग्राफ में <math>G(n,p)</math>, | चूंकि यह मात्रा लेबल दिए गए सबग्राफ की अपेक्षित संख्या है <math>H</math> एक यादृच्छिक ग्राफ में <math>G(n,p)</math>, | ||
अनुमान की व्याख्या दावे के रूप में की जा सकती है | अनुमान की व्याख्या दावे के रूप में की जा सकती है | ||
कि किसी भी द्विदलीय ग्राफ के लिए <math>H</math>, यादृच्छिक ग्राफ प्राप्त करता है (उम्मीद में) प्रतियों की न्यूनतम संख्या <math>H</math> कुछ निश्चित बढ़त घनत्व के साथ सभी रेखांकन | कि किसी भी द्विदलीय ग्राफ के लिए <math>H</math>, यादृच्छिक ग्राफ प्राप्त करता है (उम्मीद में) प्रतियों की न्यूनतम संख्या <math>H</math> कुछ निश्चित बढ़त घनत्व के साथ सभी रेखांकन पर है। | ||
सिडोरेंको के अनुमान के कई दृष्टिकोण समस्या को ग्राफोन पर एक अभिन्न असमानता के रूप में तैयार करते हैं, जो तब अन्य विश्लेषणात्मक दृष्टिकोणों का उपयोग करके समस्या पर आक्षेप करने की अनुमति देता है। {{r|norms}} | सिडोरेंको के अनुमान के कई दृष्टिकोण समस्या को ग्राफोन पर एक अभिन्न असमानता के रूप में तैयार करते हैं, जो तब अन्य विश्लेषणात्मक दृष्टिकोणों का उपयोग करके समस्या पर आक्षेप करने की अनुमति देता है। {{r|norms}} | ||
Revision as of 15:35, 18 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ सम्मलित है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है