ग्राफॉन

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]$. आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:

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

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

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

उदाहरण

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

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

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

परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल $k$ सामुदायिक स्टोकेस्टिक ब्लॉक मॉडल, एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं $k$ मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ $p_{ll}$ क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा $(l,l)$ और $(m,m)$ संभाव्यता के साथ स्वतंत्र रूप से शामिल है $p_{lm}$।

कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में शामिल किया गया है।

संयुक्त रूप से विनिमेय आसन्न आव्यूह

$n$ आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक $n\times n$ सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ n x n उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें $G_{n}$ उत्पन्न करने की अनुमति देता है एक $G_{n-1}$ नोड जोड़कर और अश्रि का नमूना $(j,n)$ $j<n$ के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक $(X_{ij})$ अनंत सममित सरणियों के रूप में परिभाषित किया जाता है।

शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; यानी यादृच्छिक आव्यूह संतोषजनक है:

$(X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})$

सभी क्रमपरिवर्तन के लिए $\sigma$ प्राकृतिक संख्याओं की, जहाँ ${\overset {d}{=}}$ का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है।

विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष मामला है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह $(X_{ij})$ द्वारा उत्पन्न होता है:

1. नमूना $u_{j}\sim U[0,1]$ स्वतंत्र रूप से
2. $X_{ij}=X_{ji}=1$ संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से $W(u_{i},u_{j}),$

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

ग्राफॉन अनुमान

पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, $W$ नोड अव्यक्त स्थिति $u_{i},$ और ग्राफॉन अनुमान की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य $W$ अनुमान लगाना है एक समकक्ष वर्ग तक, या $W$ द्वारा प्रेरित प्रायिकता आव्यूह का अनुमान लगाएं।

विश्लेषणात्मक सूत्रीकरण

कोई भी ग्राफ $n$ वर्टेक्स $\{1,2,\dots ,n\}$ इसके आसन्न आव्यूह के साथ पहचाना जा सकता है $A_{G}$. यह आव्यूह एक स्टेपफंक्शन से मेल खाता है $W_{G}:[0,1]^{2}\to [0,1]$, विभाजन द्वारा परिभाषित $[0,1]$ अंतराल में

$I_{1},I_{2},\dots ,I_{n}$ ऐसा है कि $I_{j}$ इंटीरियर है

$$\left({\frac {j-1}{n}},{\frac {j}{n}}\right)$$

और प्रत्येक के लिए $(x,y)\in I_{i}\times I_{j}$, सेटिंग $W_{G}(x,y)$ के बराबर

$(i,j)^{\text{th}}$

का प्रवेश $A_{G}$. यह समारोह $W_{G}$ ग्राफ का संबद्ध ग्राफॉन $G$ से है

सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है $(G_{n})$ जहां शीर्षों की संख्या $G_{n}$ अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं कार्यों के सीमित संचालन पर विचार करके अनुक्रम के संचालन को सीमित करना $(W_{G_{n}})$. यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी।

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

उदाहरण

लगातार ग्राफॉन

$(G_{n})$ एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए $G_{n}=G(n,p)$ कुछ निश्चित पैरामीटर के साथ $p$. सहज रूप से, जैसा $n$ अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के शीर्ष घनत्व द्वारा निर्धारित की जाती है। ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है $W(x,y)\equiv p$, जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है।

अर्द्ध ग्राफॉन

$(H_{n})$ अर्द्ध ग्राफ का क्रम लीजिए अर्द्ध ग्राफ, लेने से परिभाषित $H_{n}$ द्विदलीय ग्राफ पर होना $2n$ वर्टेक्स $u_{1},u_{2},\dots ,u_{n}$ और $v_{1},v_{2},\dots ,v_{n}$ ऐसा है कि $u_{i}$ लगी हुई है $v_{j}$ ठीक है जब $i\leq j$ है. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब निकटतम आव्यूह $A_{H_{n}}$अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं। उदाहरण के लिए, आसन्न आव्यूह $H_{3}$ द्वारा दिया गया है

$${\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}}.$$

जैसा $n$ बृहत् हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं। इस अंतर्ज्ञान का मिलान, अनुक्रम $(H_{n})$ अर्द्ध ग्राफॉन में परिवर्तित हो जाता है $W$ द्वारा परिभाषित $W(x,y)=1$ जब $|x-y|\geq 1/2$ और $W(x,y)=0$।

पूर्ण द्विदलीय ग्राफॉन

क्रम लीजिए $(K_{n,n})$ समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का क्रम लीजिए। यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं और दूसरे भाग के शीर्षों को अंत में रखकर, निकटतम आव्यूह $(K_{n,n})$ एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। उदाहरण के लिए, आसन्न आव्यूह $K_{2,2}$ द्वारा दिया गया है

$${\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.$$

जैसा $n$ बड़ा हो जाता है, आसन्न आव्यूह की यह ब्लॉक संरचना स्थिर रहती है, ताकि रेखांकन का यह क्रम पूर्ण द्विदलीय ग्राफॉन में परिवर्तित हो जाए $W$ द्वारा परिभाषित $W(x,y)=1$ जब कभी भी $\min(x,y)\leq 1/2$ और $\max(x,y)>1/2$, और सेटिंग $W(x,y)=0$ अन्यथा हो।

यदि हम इसके बजाय शीर्षों को आदेश दें $K_{n,n}$ भागों के बीच बारी-बारी से, आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। उदाहरण के लिए, इस आदेश के तहत, आसन्न आव्यूह $K_{2,2}$ द्वारा दिया गया है

$${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.$$

जैसा $n$ बड़ा हो जाता है, आसन्न आव्युह बेहतर और बेहतर शतरंजबोर्ड बन जाते हैं। इस संचालन के बावजूद, हम अभी भी चाहते हैं की सीमा $(K_{n,n})$