ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 30: | Line 30: | ||
# इकाई वर्ग को विभाजित करना <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> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | ||
| 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>(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 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 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> | ||
किसी भी ग्राफ के लिए <math>F</math> | किसी भी ग्राफ के लिए <math>F</math> है। | ||
इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए <math>F</math> वाम-अभिसरण है, समरूपता घनत्व का क्रम <math>\left(t(F, G_n)\right)</math> अभिसरण। | इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए <math>F</math> वाम-अभिसरण है, समरूपता घनत्व का क्रम <math>\left(t(F, G_n)\right)</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 210: | Line 210: | ||
अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के अनुसार अभिसारी है यदि यह कट दूरी के अनुसार एक कॉची अनुक्रम है <math>\delta_\square</math>. चूंकि यह परिभाषा का सीधा परिणाम नहीं है, यदि ग्राफ का ऐसा क्रम कॉची है, तो <math>W</math> हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है। | अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के अनुसार अभिसारी है यदि यह कट दूरी के अनुसार एक कॉची अनुक्रम है <math>\delta_\square</math>. चूंकि यह परिभाषा का सीधा परिणाम नहीं है, यदि ग्राफ का ऐसा क्रम कॉची है, तो <math>W</math> हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है। | ||
==== अभिसरण की समानता ==== | ==== अभिसरण की समानता ==== | ||
| Line 223: | Line 223: | ||
<ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास है: | <ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास है: | ||
<math display=block> |t(F, U) - t(F, W)| \le e(F) \delta_\square(U, W) </math> | <math display=block> |t(F, U) - t(F, W)| \le e(F) \delta_\square(U, W) </math> | ||
सभी रेखांकन के लिए <math>F</math> | सभी रेखांकन के लिए <math>F</math> है। | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
| Line 232: | Line 232: | ||
सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>, | सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>, | ||
हमारे पास यह होना चाहिए <math>\delta_\square(U, W) < \epsilon</math>. | हमारे पास यह होना चाहिए <math>\delta_\square(U, W) < \epsilon</math>. | ||
इस लेम्मा से पता चलता है कि वाम-अभिसरण का अर्थ कटी हुई दूरी के अंतर्गत अभिसरण है। | इस लेम्मा से पता चलता है कि वाम-अभिसरण का अर्थ कटी हुई दूरी के अंतर्गत अभिसरण है। | ||
=== ग्राफोन का स्थान === | === ग्राफोन का स्थान === | ||
| Line 252: | Line 251: | ||
अनुप्रमेय 1. प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक पूर्णांक है <math>N</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफ है <math>G</math> अधिक से अधिक के साथ <math>N</math> ऐसा शिखर <math>\delta_\square(W, W_G) < \epsilon</math>. | अनुप्रमेय 1. प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक पूर्णांक है <math>N</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफ है <math>G</math> अधिक से अधिक के साथ <math>N</math> ऐसा शिखर <math>\delta_\square(W, W_G) < \epsilon</math>. | ||
माना कि <math>\mathcal{G}</math> रेखांकन का सेट हो। प्रत्येक ग्राफ के लिए विचार करें <math>G \in \mathcal{G}</math> खुली गेंद <math>B_\square(G, \epsilon)</math> जिसमें सभी ग्राफोन हों <math>W</math> ऐसा है कि <math>\delta_\square(W, W_G) < \epsilon</math>. सभी ग्राफ कवर के लिए खुली गेंदों का सेट <math>\widetilde{\mathcal{W}}_0</math>, इसलिए सघन का अर्थ है कि एक परिमित उपकवर है <math>\{ B_\square(G, \epsilon) \mid G \in \mathcal{G}_0 \}</math> कुछ परिमित उपसमुच्चय के लिए <math>\mathcal{G}_0 \subset \mathcal{G}</math>. अब हम ले सकते हैं <math>N</math> रेखांकन के बीच शीर्षों की सबसे बड़ी संख्या होना <math>\mathcal{G}_0</math>. | माना कि <math>\mathcal{G}</math> रेखांकन का सेट हो। प्रत्येक ग्राफ के लिए विचार करें <math>G \in \mathcal{G}</math> खुली गेंद <math>B_\square(G, \epsilon)</math> जिसमें सभी ग्राफोन हों <math>W</math> ऐसा है कि <math>\delta_\square(W, W_G) < \epsilon</math>. सभी ग्राफ कवर के लिए खुली गेंदों का सेट <math>\widetilde{\mathcal{W}}_0</math>, इसलिए सघन का अर्थ है कि एक परिमित उपकवर है <math>\{ B_\square(G, \epsilon) \mid G \in \mathcal{G}_0 \}</math> कुछ परिमित उपसमुच्चय के लिए <math>\mathcal{G}_0 \subset \mathcal{G}</math>. अब हम ले सकते हैं <math>N</math> रेखांकन के बीच शीर्षों की सबसे बड़ी संख्या होना <math>\mathcal{G}_0</math>. | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
| Line 273: | Line 271: | ||
ग्राफन के लिए कमजोर नियमितता प्रमेयिका। हर ग्राफन के लिए <math>W</math> और <math>\epsilon > 0</math>, एक स्टेपफंक्शन है <math>W'</math> अधिक से अधिक के साथ <math>\lceil 4^{1/\epsilon^2} \rceil</math> ऐसे कदम <math> \lVert W - W' \rVert_\square \le \epsilon</math>. | ग्राफन के लिए कमजोर नियमितता प्रमेयिका। हर ग्राफन के लिए <math>W</math> और <math>\epsilon > 0</math>, एक स्टेपफंक्शन है <math>W'</math> अधिक से अधिक के साथ <math>\lceil 4^{1/\epsilon^2} \rceil</math> ऐसे कदम <math> \lVert W - W' \rVert_\square \le \epsilon</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> | ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <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> | ||
मजबूत नियमितता प्रमेयिका का प्रमाण ऊपर दिए गए परिणाम 1 की अवधारणा के समान है। यह पता चला है कि हर ग्राफॉन <math>W</math> एक स्टेपफंक्शन के साथ अनुमान लगाया जा सकता है <math>U</math> एलपी_स्पेस#एलपी_स्पेस_एंड_लेब्सग्यू_इंटीग्रल्स में <math>L_1</math> मानदंड, दिखा रहा है कि गेंदों का सेट <math>B_1(U, \epsilon_0)</math> ढकना <math>\widetilde{\mathcal{W}}_0</math>. ये सेट में नहीं खुले हैं <math>\delta_\square</math> मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है। | मजबूत नियमितता प्रमेयिका का प्रमाण ऊपर दिए गए परिणाम 1 की अवधारणा के समान है। यह पता चला है कि हर ग्राफॉन <math>W</math> एक स्टेपफंक्शन के साथ अनुमान लगाया जा सकता है <math>U</math> एलपी_स्पेस#एलपी_स्पेस_एंड_लेब्सग्यू_इंटीग्रल्स में <math>L_1</math> मानदंड, दिखा रहा है कि गेंदों का सेट <math>B_1(U, \epsilon_0)</math> ढकना <math>\widetilde{\mathcal{W}}_0</math>. ये सेट में नहीं खुले हैं <math>\delta_\square</math> मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है। | ||
=== सिदोरेंको का अनुमान === | === सिदोरेंको का अनुमान === | ||
| Line 298: | Line 294: | ||
चूंकि यह मात्रा लेबल दिए गए सबग्राफ की अपेक्षित संख्या है <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}} | ||
| Line 385: | Line 381: | ||
<ref name=Orbanz:Roy:2015>{{Cite journal| volume = 37| issue = 2| pages = 437–461| last1 = Orbanz| first1 = P.| last2 = Roy| first2 = D.M.| title = Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures| journal = IEEE Transactions on Pattern Analysis and Machine Intelligence| doi=10.1109/tpami.2014.2334607| pmid = 26353253| arxiv = 1312.7857| year = 2015| s2cid = 566759}}</ref> | <ref name=Orbanz:Roy:2015>{{Cite journal| volume = 37| issue = 2| pages = 437–461| last1 = Orbanz| first1 = P.| last2 = Roy| first2 = D.M.| title = Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures| journal = IEEE Transactions on Pattern Analysis and Machine Intelligence| doi=10.1109/tpami.2014.2334607| pmid = 26353253| arxiv = 1312.7857| year = 2015| s2cid = 566759}}</ref> | ||
</references> | </references> | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category: | |||
[[Category:Created On 08/05/2023]] | [[Category:Created On 08/05/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:ग्राफ सिद्धांत]] | |||
[[Category:सिद्धांत संभावना]] | |||
