ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Exchangeable random graph from graphon.png|thumb|300px|एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ <math>n</math> स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है <math>k \in \{1,\dotsc,n\}</math> एक अव्यक्त यादृच्छिक चर | [[File:Exchangeable random graph from graphon.png|thumb|300px|एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ <math>n</math> स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है <math>k \in \{1,\dotsc,n\}</math> एक अव्यक्त यादृच्छिक चर | ||
<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>(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>. ऊपरी बाएँ | ||
पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।]]ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन [[औसत दर्जे का]] कार्य है: <math>W:[0,1]^2\to[0,1]</math>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और [[विनिमेय यादृच्छिक चर]] यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल [[लगभग निश्चित रूप से]] सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक | पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।]]ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन [[औसत दर्जे का]] कार्य है: <math>W:[0,1]^2\to[0,1]</math>, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और [[विनिमेय यादृच्छिक चर]] यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल [[लगभग निश्चित रूप से]] सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं। | ||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
| Line 69: | Line 69: | ||
सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है <math>(G_n)</math> जहां शीर्षों की संख्या <math>G_{n}</math> अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं | ||
कार्यों के सीमित | कार्यों के सीमित संचालन पर विचार करके अनुक्रम के संचालन को सीमित करना <math>(W_{G_n})</math>. | ||
यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी। | ||
| Line 81: | Line 81: | ||
==== लगातार ग्राफॉन ==== | ==== लगातार ग्राफॉन ==== | ||
<math>(G_n)</math> एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए <math>G_n = G(n,p)</math> कुछ निश्चित पैरामीटर के साथ <math>p</math>. | <math>(G_n)</math> एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए <math>G_n = G(n,p)</math> कुछ निश्चित पैरामीटर के साथ <math>p</math>. | ||
सहज रूप से, जैसा <math>n</math> अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के | सहज रूप से, जैसा <math>n</math> अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के शीर्ष घनत्व द्वारा निर्धारित की जाती है। | ||
ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है <math>W(x,y)\equiv p</math>, जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है। | ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है <math>W(x,y)\equiv p</math>, जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है। | ||
| Line 90: | Line 90: | ||
<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> | ||
जैसा <math>n</math> | जैसा <math>n</math> बृहत् हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं। | ||
इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> अर्द्ध ग्राफॉन में परिवर्तित हो जाता है <math>W</math> द्वारा परिभाषित <math>W(x,y) = 1</math> जब <math>|x-y| \ge 1/2</math> और <math>W(x,y) = 0</math>। | इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> अर्द्ध ग्राफॉन में परिवर्तित हो जाता है <math>W</math> द्वारा परिभाषित <math>W(x,y) = 1</math> जब <math>|x-y| \ge 1/2</math> और <math>W(x,y) = 0</math>। | ||
| Line 111: | Line 111: | ||
<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> बड़ा हो जाता है, | ||
आसन्न आव्युह बेहतर और बेहतर शतरंजबोर्ड बन जाते हैं। | आसन्न आव्युह बेहतर और बेहतर शतरंजबोर्ड बन जाते हैं। | ||
इस | इस संचालन के बावजूद, हम अभी भी चाहते हैं की सीमा <math>(K_{n,n})</math> अद्वितीय हो और परिणाम उदाहरण 3 से ग्राफॉन में हो। | ||
इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए। | इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए। | ||
| Line 120: | Line 120: | ||
=== ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | === ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना === | ||
दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ <math>G</math> सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>W</math> के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, | दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ <math>G</math> सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>W</math> के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, शीर्ष का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। <math>G</math> अभिन्न द्वारा दिया गया है: | ||
<math display=block> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y .</math> | <math display=block> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y .</math> | ||
यह है क्योंकि <math>W</math> है <math>\{0,1\}</math>-मूल्यवान, और प्रत्येक किनारा <math>(i, j)</math> | यह है क्योंकि <math>W</math> है <math>\{0,1\}</math>-मूल्यवान, और प्रत्येक किनारा <math>(i, j)</math> | ||
| Line 135: | Line 135: | ||
यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | ||
तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | ||
उदाहरण के लिए, यदि हम | उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के तहत इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बृहत् <math>n</math> के लिए उच्च संभावना है। | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। हालाँकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी है <math>\tfrac{1}{2}</math>. | ||
दो प्राकृतिक आव्युह हैं | दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | ||
पहला एक नमूना मीट्रिक है, जो कहता है कि यदि सबग्राफ के वितरण करीब हैं तो दो ग्राफ़ करीब हैं। | पहला एक नमूना मीट्रिक है, जो कहता है कि यदि सबग्राफ के वितरण करीब हैं तो दो ग्राफ़ करीब हैं। | ||
दूसरा एक बढ़त विसंगति सिद्धांत मीट्रिक है, जो कहता है कि दो ग्राफ़ करीब होते हैं जब उनके | दूसरा एक बढ़त विसंगति सिद्धांत मीट्रिक है, जो कहता है कि दो ग्राफ़ करीब होते हैं जब उनके शीर्ष के घनत्व उनके सभी संबंधित उपसमुच्चय के करीब होते हैं। | ||
चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | ||
इसके अलावा, दोनों आव्युह के तहत लिमिट ऑब्जेक्ट ग्राफॉन बन जाते हैं। | इसके अलावा, दोनों आव्युह के तहत लिमिट ऑब्जेक्ट ग्राफॉन बन जाते हैं। | ||
अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन_चुंग#अर्ध-यादृच्छिक_ग्राफ | अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन_चुंग#अर्ध-यादृच्छिक_ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।{{r|qrandom}} | ||
==== समरूपता घनत्व ==== | ==== समरूपता घनत्व ==== | ||
| Line 155: | Line 155: | ||
सीधे सबग्राफ से निपटने के बजाय, यह निकला | सीधे सबग्राफ से निपटने के बजाय, यह निकला | ||
ग्राफ समरूपता के साथ काम करना आसान। | ग्राफ समरूपता के साथ काम करना आसान। | ||
इस परिदृश्य में | इस परिदृश्य में बृहत्,सघन ग्राफ से निपटने के दौरान यह ठीक है | ||
सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ होमोमोर्फिम्स की संख्या असम्बद्ध रूप से बराबर होती है। | सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ होमोमोर्फिम्स की संख्या असम्बद्ध रूप से बराबर होती है। | ||
| Line 187: | Line 187: | ||
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 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> | ||
Revision as of 23:12, 17 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ मौजूद है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:
- प्रत्येक शीर्ष ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है ।
- किनारा संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है ।
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल कभी-कभी निरूपित किया जाता है