ग्राफॉन: Difference between revisions

Revision as of 14:47, 18 May 2023

File:Exchangeable random graph from graphon.png

एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ

n

स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है

k\in \{1,\dotsc ,n\}

एक अव्यक्त यादृच्छिक चर

U_{k}\sim \mathrm {U} (0,1)

(ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित

(k,l)

संभावना के साथ स्वतंत्र रूप से

f(U_{k},U_{l})

. उदाहरण के लिए, किनारा

(3,5)

(हरा, बिंदीदार) संभावना के साथ मौजूद है

f(0.72,0.9)

; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य

(u_{3},u_{5})

और

(u_{5},u_{3})

. ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।

ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: $W:[0,1]^{2}\to [0,1]$ , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।

सांख्यिकीय सूत्रीकरण

एक ग्राफॉन एक सममित मापने योग्य कार्य है $W:[0,1]^{2}\to [0,1]$ . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:

प्रत्येक शीर्ष $j$ ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है $u_{j}\sim U[0,1]$ ।
किनारा $(i,j)$ संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है $W(u_{i},u_{j})$ ।

एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल $W$ कभी-कभी निरूपित किया जाता है $\mathbb {G} (n,W)$ , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ $W$ इस प्रकार कहा जाता है $W$ -यादृच्छिक ग्राफ है।

यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि $W\neq 0$ विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।^[1]

उदाहरण

ग्राफॉन का सबसे सरल उदाहरण है $W(x,y)\equiv p$ कुछ स्थिर के लिए $p\in [0,1]$ . इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है $G(n,p)$ जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है $p$ ।

यदि हम इसके बजाय एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है:

इकाई वर्ग को विभाजित करना $k\times k$ ब्लॉक, और
सेटिंग $W$ के बराबर $p_{lm}$ पर $(l,m)^{\text{th}}$ अवरोध पैदा करना,

परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल $k$ सामुदायिक स्टोकेस्टिक ब्लॉक मॉडल, एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं $k$ मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ

[1]

@@ Line 153: / Line 153: @@
 यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से  <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं।
 सबग्राफ से सीधे डीलिंग के बजाय, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है।
-इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है
+इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है,
 सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है।
@@ Line 160: / Line 160: @@
 ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं।
-दरअसल, एक ग्राफ दिया <math>G</math> संबद्ध ग्राफॉन के साथ <math>W_G</math> और दुसरी <math>F</math>, अपने पास
+दरअसल, एक ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W_G</math> और दुसरी <math>F</math>, अपने पास है:
 <math display=block> t(F, G) = \int \prod_{(i,j)\in E(F)} W_G(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math>
-जहां इंटीग्रल बहुआयामी है, यूनिट हाइपरक्यूब पर लिया गया है <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>(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> अभिसरण।
-हालांकि अकेले परिभाषा से स्पष्ट नहीं है, अगर <math>(G_n)</math> इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन मौजूद होता है <math>W</math> ऐसा है कि हर ग्राफ के लिए <math>F</math>, अपने पास
+हालांकि अकेले परिभाषा से स्पष्ट नहीं है, अगर <math>(G_n)</math> इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन मौजूद होता है <math>W</math> ऐसा है कि हर ग्राफ के लिए <math>F</math>, अपने पास है:
 <math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W) </math>
 इसके साथ ही।
@@ Line 178: / Line 178: @@
 दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर।
 क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं,
-उनकी दूरी को मापने का एक तरीका सबसेट तक सीमित करना है <math>X, Y</math> वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए अश्रि की संख्या की तुलना करें <math>e_G(X,Y)</math> से <math>X</math> को <math>Y</math> में <math>G</math> अश्रि की संख्या के लिए <math>e_H(X,Y)</math> बीच में <math>X</math> और <math>Y</math> में <math>H</math>.
+उनकी दूरी को मापने का एक तरीका <math>X, Y</math> सबसेट तक सीमित करना है  वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए अश्रि की संख्या की तुलना करें <math>e_G(X,Y)</math> से <math>X</math> को <math>Y</math> में <math>G</math> अश्रि की संख्या के लिए <math>e_H(X,Y)</math> बीच में <math>X</math> और <math>Y</math> में <math>H</math>.
 यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं।
@@ Line 227: / Line 227: @@
 </ब्लॉककोट>
-गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा होमोमोर्फिज्म घनत्व पर देती है <math>t(F, W)</math>, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा Szemerédi_regularity_lemma#Graph_counting_lemma का एक सामान्यीकरण है जो Szemerédi_regularity_lemma के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के तहत अभिसरण का अर्थ बाएं-अभिसरण है।
+गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा समरूपता घनत्व पर देती है <math>t(F, W)</math>, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा Szemerédi_regularity_lemma#Graph_counting_lemma का एक सामान्यीकरण है जो Szemerédi_regularity_lemma के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के तहत अभिसरण का अर्थ बाएं-अभिसरण है।
 उलटा काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या मौजूद है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ

Anonymous

Search

ग्राफॉन: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:47, 18 May 2023

Contents

सांख्यिकीय सूत्रीकरण

उदाहरण