ग्राफॉन: Difference between revisions

    प्रत्येक किनारे सहित <math>(k,l)</math> संभावना के साथ स्वतंत्र रूप से <math>f(U_{k},U_{l})</math>.

     उदाहरण के लिए, किनारा <math>(3,5)</math> (हरा, बिंदीदार) संभावना के साथ मौजूद है     

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

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

# किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है <math>W(u_{i},u_{j})</math>।

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

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

# सेटिंग <math>W</math> के बराबर <math>p_{lm}</math> पर <math>(l,m)^{\text{th}}</math> अवरोध पैदा करना,

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

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

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

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

# नमूना <math>u_{j}\sim U[0,1]</math> स्वतंत्र रूप से

पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, <math>W</math> नोड अव्यक्त स्थिति <math>u_i,</math> और ग्राफॉन अनुमान की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य <math>W</math> अनुमान लगाना है एक समकक्ष वर्ग तक,<ref>{{Cite arXiv|last1=Wolfe|first1=Patrick J.|last2=Olhede|first2=Sofia C.|date=2013-09-23|title=गैर पैरामीट्रिक ग्राफॉन अनुमान|eprint=1309.5936|class=math.ST}}</ref><ref>{{Cite journal|last1=Choi|first1=David|last2=Wolfe|first2=Patrick J.|date=February 2014|title=अलग-अलग विनिमेय नेटवर्क डेटा का सह-क्लस्टरिंग|arxiv=1212.4093|journal=The Annals of Statistics|volume=42|issue=1|pages=29–63|doi=10.1214/13-AOS1173|s2cid=16291079|issn=0090-5364}}</ref> या <math>W</math> द्वारा प्रेरित प्रायिकता आव्यूह का अनुमान लगाएं।<ref>{{Cite journal|last1=Gao|first1=Chao|last2=Lu|first2=Yu|last3=Zhou|first3=Harrison H.|date=December 2015|title=दर-इष्टतम ग्राफॉन अनुमान|journal=The Annals of Statistics|volume=43|issue=6|pages=2624–2652|doi=10.1214/15-AOS1354|issn=0090-5364|arxiv=1410.5837|s2cid=14267617}}</ref><ref>{{Cite journal|last1=Yuan|first1=Zhang|last2=Elizaveta|first2=Levina|last3=Ji|first3=Zhu|date=2017|title=नेबरहुड स्मूथिंग द्वारा नेटवर्क एज संभावनाओं का अनुमान लगाना|url=https://academic.oup.com/biomet/article-abstract/104/4/771/4158787?redirectedFrom=fulltext|journal=Biometrika|volume=104|issue=4|pages=771–783|doi=10.1093/biomet/asx042|issn=0006-3444}}</ref>

यह समारोह <math>W_G</math> ग्राफ का संबद्ध ग्राफॉन <math>G</math> से है

कार्यों के सीमित व्यवहार पर विचार करके अनुक्रम के व्यवहार को सीमित करना <math>(W_{G_n})</math>.

सहज रूप से, जैसा <math>n</math> अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के किनारे घनत्व द्वारा निर्धारित की जाती है।

उदाहरण के लिए, आसन्न आव्यूह <math>H_{3}</math> द्वारा दिया गया है

जैसा <math>n</math> बड़े हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं।

उदाहरण के लिए, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है

ताकि रेखांकन का यह क्रम पूर्ण द्विदलीय ग्राफॉन में परिवर्तित हो जाए <math>W</math>

यदि हम इसके बजाय शीर्षों को आदेश दें <math>K_{n,n}</math> भागों के बीच बारी-बारी से,

उदाहरण के लिए, इस आदेश के तहत, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है

इस व्यवहार के बावजूद, हम अभी भी चाहते हैं की सीमा <math>(K_{n,n})</math> अद्वितीय हो और परिणाम उदाहरण 3 से ग्राफॉन में हो।

फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप से।

दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ  <math>G</math> सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>W</math> के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, किनारे का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। <math>G</math> अभिन्न द्वारा दिया गया है:

क्षेत्र के <math>1/n^2</math> जहाँ <math>W</math> के बराबर होती है <math>1</math>.

इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या में <math>G</math> के बराबर है

यदि हम Metric_%28mathematics%29 में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है,

तो हमें अपना ध्यान उन मेट्रिक्स तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं।

उदाहरण के लिए, यदि हम बेतरतीब ढंग से एक Erdős–Rényi मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <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}}

दो रेखांकन के बीच की दूरी को मापने का एक तरीका <math>G</math> और <math>H</math> उनके सापेक्ष सबग्राफ काउंट्स की तुलना करना है।

यानी प्रत्येक ग्राफ के लिए <math>F</math> हम की प्रतियों की संख्या की तुलना कर सकते हैं <math>F</math> में <math>G</math> और <math>F</math> में <math>H</math>.

यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब

intuitively <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं।

सीधे सबग्राफ से निपटने के बजाय, यह निकला

ग्राफ समरूपता के साथ काम करना आसान।

इस परिदृश्य में बड़े,सघन ग्राफ से निपटने के दौरान यह ठीक है

सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ होमोमोर्फिम्स की संख्या असम्बद्ध रूप से बराबर होती है।

दो रेखांकन दिए गए हैं <math>F</math> और <math>G</math>, द

[[समरूपता घनत्व]] <math>t(F, G)</math> का <math>F</math> में <math>G</math> से ग्राफ़ समरूपता की संख्या के रूप में परिभाषित किया गया है <math>F</math> को <math>G</math>.

दूसरे शब्दों में, <math>t(F,G)</math> के शीर्ष से यादृच्छिक रूप से चुने गए मानचित्र की प्रायिकता है <math>F</math> के शिखर तक <math>G</math> सन्निकट शीर्षों को अंदर भेजता है <math>F</math> सन्निकट शीर्षों में <math>G</math>.