ग्राफॉन

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$