ग्राफॉन: 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>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। | पैनल ग्राफ प्राप्ति को आसन्न मैट्रिक्स के रूप में दिखाता है।]]ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन [[औसत दर्जे का]] कार्य है: <math>W:[0,1]^2\to[0,1]</math>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और [[विनिमेय यादृच्छिक चर]] यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल [[लगभग निश्चित रूप से]] सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बड़े सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं। | ||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
| Line 11: | Line 11: | ||
एक ग्राफॉन एक सममित मापने योग्य कार्य है <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>W(u_{i},u_{j})</math>। | # किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है <math>W(u_{i},u_{j})</math>। | ||
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है | एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | ||
एक निश्चित ग्राफॉन पर आधारित मॉडल <math>W</math> कभी-कभी निरूपित किया जाता है <math>\mathbb{G}(n, W)</math>, | एक निश्चित ग्राफॉन पर आधारित मॉडल <math>W</math> कभी-कभी निरूपित किया जाता है <math>\mathbb{G}(n, W)</math>, | ||
यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। | ||
ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक ग्राफ है। | ग्राफॉन से उत्पन्न ग्राफ <math>W</math> इस प्रकार कहा जाता है <math>W</math>-यादृच्छिक ग्राफ है। | ||
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि <math>W\neq0</math>विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से | यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि <math>W\neq0</math> विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।<ref name=Orbanz:Roy:2015 /> | ||
| Line 139: | Line 139: | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को किनारों की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़_एडिट_डिस्टेंस। हालाँकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी है <math>\tfrac{1}{2}</math>. | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को किनारों की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़_एडिट_डिस्टेंस। हालाँकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी है <math>\tfrac{1}{2}</math>. | ||
दो प्राकृतिक मेट्रिक्स हैं | दो प्राकृतिक मेट्रिक्स हैं जोसघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा व्यवहार करते हैं जो हम चाहते हैं। | ||
पहला एक नमूना मीट्रिक है, जो कहता है कि यदि सबग्राफ के वितरण करीब हैं तो दो ग्राफ़ करीब हैं। | पहला एक नमूना मीट्रिक है, जो कहता है कि यदि सबग्राफ के वितरण करीब हैं तो दो ग्राफ़ करीब हैं। | ||
दूसरा एक बढ़त विसंगति सिद्धांत मीट्रिक है, जो कहता है कि दो ग्राफ़ करीब होते हैं जब उनके किनारे घनत्व उनके सभी संबंधित उपसमुच्चय के करीब होते हैं। | दूसरा एक बढ़त विसंगति सिद्धांत मीट्रिक है, जो कहता है कि दो ग्राफ़ करीब होते हैं जब उनके किनारे घनत्व उनके सभी संबंधित उपसमुच्चय के करीब होते हैं। | ||
| Line 155: | Line 155: | ||
सीधे सबग्राफ से निपटने के बजाय, यह निकला | सीधे सबग्राफ से निपटने के बजाय, यह निकला | ||
ग्राफ समरूपता के साथ काम करना आसान। | ग्राफ समरूपता के साथ काम करना आसान। | ||
इस परिदृश्य में बड़े, | इस परिदृश्य में बड़े,सघन ग्राफ से निपटने के दौरान यह ठीक है | ||
सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ होमोमोर्फिम्स की संख्या असम्बद्ध रूप से बराबर होती है। | सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ होमोमोर्फिम्स की संख्या असम्बद्ध रूप से बराबर होती है। | ||
| Line 252: | Line 252: | ||
यह स्थान कॉम्पैक्ट स्थान बन जाता है। | यह स्थान कॉम्पैक्ट स्थान बन जाता है। | ||
इसके अलावा, इसमें सभी परिमित रेखांकन का सेट होता है, जो उनके संबंधित ग्राफों द्वारा | इसके अलावा, इसमें सभी परिमित रेखांकन का सेट होता है, जो उनके संबंधित ग्राफों द्वारा एकसघन सेट के रूप में दर्शाया जाता है। | ||
इन अवलोकनों से पता चलता है कि ग्राफ़ॉन का स्थान एक पूर्ण_मीट्रिक_स्थान है#कट की गई दूरी के संबंध में ग्राफ़ के स्थान का पूरा होना। इसका एक तात्कालिक परिणाम निम्नलिखित है। | इन अवलोकनों से पता चलता है कि ग्राफ़ॉन का स्थान एक पूर्ण_मीट्रिक_स्थान है#कट की गई दूरी के संबंध में ग्राफ़ के स्थान का पूरा होना। इसका एक तात्कालिक परिणाम निम्नलिखित है। | ||
| Line 308: | Line 308: | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
ग्राफोन स्वाभाविक रूप | ग्राफोन स्वाभाविक रूप सेसघन सरल रेखांकन से जुड़े होते हैं। | ||
सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें अक्सर अलंकृत ग्राफॉन कहा जाता है।{{r|decorate}} रेंडम ग्राफ मॉडल के दोनों दृष्टिकोणों से विरल ग्राफ शासन के हाल के विस्तार भी हैं <ref name=Veitch:Roy:2015 />और ग्राफ सीमा सिद्धांत।<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 /><ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 /> | सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें अक्सर अलंकृत ग्राफॉन कहा जाता है।{{r|decorate}} रेंडम ग्राफ मॉडल के दोनों दृष्टिकोणों से विरल ग्राफ शासन के हाल के विस्तार भी हैं <ref name=Veitch:Roy:2015 />और ग्राफ सीमा सिद्धांत।<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 /><ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 /> | ||
Revision as of 16:01, 17 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक किनारे सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ मौजूद है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न मैट्रिक्स के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बड़े सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:
- प्रत्येक शीर्ष ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है ।
- किनारा संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है ।
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर आधारित मॉडल कभी-कभी निरूपित किया जाता है , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ इस प्रकार कहा जाता है -यादृच्छिक ग्राफ है।
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।[1]
उदाहरण
ग्राफॉन का सबसे सरल उदाहरण है कुछ स्थिर के लिए . इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है