ग्राफॉन: 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>W</math> <math>p_{lm}</math>के बराबर है <math>(l,m)^{\text{th}}</math> ब्लाक पर | ||
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल <math>k</math> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल <math>k</math> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | ||
| Line 66: | Line 66: | ||
<math>(i,j)^{\text{th}}</math> | <math>(i,j)^{\text{th}}</math> | ||
का प्रवेश <math>A_G</math>. | का प्रवेश <math>A_G</math>. | ||
यह | यह फलन <math>W_G</math> ग्राफ का संबद्ध ग्राफॉन <math>G</math> से है। | ||
सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | ||
| 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> के बराबर है। | ||
| 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> मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है। | ||
Revision as of 14:12, 20 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ सम्मलित है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है . सामान्यत: एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:
- प्रत्येक शीर्ष ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है ।
- किनारा संभावना के साथ ग्राफ में स्वतंत्र रूप से सम्मलित है ।
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल कभी-कभी निरूपित किया जाता है , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ इस प्रकार कहा जाता है -यादृच्छिक ग्राफ है।
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।[1]
उदाहरण
ग्राफॉन का सबसे सरल उदाहरण है कुछ स्थिर के लिए . इस स्थितियों में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा सम्मलित है ।
यदि हम इसके अतिरिक्त एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है:
- इकाई वर्ग को विभाजित करना ब्लॉक, और
- सेटिंग के बराबर है ब्लाक पर
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल