यादृच्छिक ग्राफ

For गिनती-अनंत यादृच्छिक ग्राफ, see राडो ग्राफ.

गणित में यादृच्छिक ग्राफ़ सामान्य शब्द है। जो ग्राफ़ (असतत) पर संभाव्यता वितरण को संदर्भित करता है। यादृच्छिक रेखांकन को केवल संभाव्यता वितरण द्वारा या यादृच्छिक प्रक्रिया द्वारा वर्णित किया जा सकता है। जो उन्हें उत्पन्न करता है। यादृच्छिक रेखांकन का सिद्धांत ग्राफ सिद्धांत और संभाव्यता सिद्धांत के बीच प्रतिच्छेदन पर स्थित है। गणितीय दृष्टिकोण से यादृच्छिक ग्राफ़ का उपयोग विशिष्ट ग्राफ़ के गुणों के बारे में प्रश्नों के उत्तर देने के लिए किया जाता है। इसके व्यावहारिक अनुप्रयोग उन सभी क्षेत्रों में पाए जाते हैं। जिनमें जटिल नेटवर्क को मॉडलिंग करने की आवश्यकता होती है। इस प्रकार कई यादृच्छिक ग्राफ़ मॉडल ज्ञात होते हैं। जो विभिन्न क्षेत्रों में सामने आने वाले विविध प्रकार के जटिल नेटवर्क को प्रतिबिंबित करते हैं। गणितीय संदर्भ में यादृच्छिक ग्राफ लगभग विशेष रूप से एर्डोस-रेनी मॉडल को संदर्भित करता है। एर्डोस-रेनी यादृच्छिक ग्राफ मॉडल अन्य संदर्भों में किसी भी ग्राफ़ मॉडल को यादृच्छिक ग्राफ़ के रूप में संदर्भित किया जा सकता है।

मॉडल

यादृच्छिक ग्राफ n अलग-अलग कोने के समूह से प्रारम्भ करके और यादृच्छिक रूप से उनके बीच क्रमिक किनारों को जोड़कर प्राप्त किया जाता है। इस क्षेत्र में अध्ययन का उद्देश्य यह निर्धारित करना है कि ग्राफ की एक विशेष गुण किस स्तर पर उत्पन्न होने की संभावना है। अलग-अलग यादृच्छिक ग्राफ़ मॉडल ग्राफ़ पर अलग-अलग संभाव्यता वितरण उत्पन्न करते हैं। एडगर गिल्बर्ट द्वारा प्रस्तावित सबसे सामान्यतः अध्ययन किया जाने वाला है। जिसे G(n,p) निरूपित किया गया है। जिसमें हर संभावित बढ़त स्वतंत्र रूप से प्रायिकता 0 < p < 1 के साथ होती है। m किनारों के साथ$N={\tbinom {n}{2}}$ किसी एक विशेष यादृच्छिक ग्राफ को प्राप्त करने की प्रायिकता $p^{m}(1-p)^{N-m}$ है।

एक निकटतम संबंधित मॉडल एर्डोस-रेनी मॉडल G(n,M) को दर्शाता है। बिल्कुल M किनारों वाले सभी ग्राफों के लिए समान संभावना प्रदान करता है। 0 ≤ M ≤ N के साथ G(n,M) है। ${\tbinom {N}{M}}$ तत्व और प्रत्येक तत्व प्रायिकता के साथ होता $1/{\tbinom {N}{M}}$ है। बाद वाले मॉडल को 'यादृच्छिक ग्राफ प्रक्रिया' के एक विशेष समय (M) पर एक स्नैपशॉट के रूप में देखा जा सकता है। ${\tilde {G}}_{n}$, जो एक अनेक संभावनाओं में से चुनी हूई प्रक्रिया है। जो n कोने और बिना किनारों से प्रारम्भ होती है और प्रत्येक चरण में किनारों के समूह से समान रूप से चुने गए नए किनारे को जोड़ती है।

यदि इसके अतिरिक्त हम वर्टिकल के अनंत समूह के साथ प्रारम्भ करते हैं और फिर से हर संभावित किनारे को प्रायिकता 0 <p <1 के साथ स्वतंत्र रूप से होने देते हैं। तो हमें एक वस्तु G मिलती है। जिसे 'अनंत यादृच्छिक ग्राफ' कहा जाता है। कुछ स्थितियों को छोड़कर जहां p, 0 या 1 के बीच में है। ऐसे G में लगभग निश्चित रूप से निम्नलिखित गुण होती है:

कोई भी n + m तत्व दिया गया है $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V$, V में एक शीर्ष c है। जो प्रत्येक $a_{1},\ldots ,a_{n}$ के निकट है और किसी $b_{1},\ldots ,b_{m}$ के निकट नहीं है।

यह पता चला है कि यदि वर्टेक्स समूह गणनीय है। तो ग्राफ समरूपता तक इस गुण के साथ केवल एक ही ग्राफ है अर्थात् राडो ग्राफ। इस प्रकार कोई भी अनगिनत अनंत यादृच्छिक ग्राफ लगभग निश्चित रूप से राडो ग्राफ है। जिसे इस कारण से कभी-कभी केवल यादृच्छिक ग्राफ कहा जाता है। चूंकि ग्राफ़ के लिए अनुरूप परिणाम सही नहीं है। जिनमें से कई (नॉनिसोमोर्फिक) ग्राफ़ हैं। जो उपरोक्त गुण को संतुष्ट करते हैं।

एक अन्य मॉडल, जो गिल्बर्ट के यादृच्छिक ग्राफ मॉडल का सामान्यीकरण करता है, यादृच्छिक डॉट-उत्पाद मॉडल है। यादृच्छिक डॉट-उत्पाद ग्राफ प्रत्येक शीर्ष के साथ एक रियल वेक्टर को जोड़ता है। किसी भी कोने u और v के बीच किनारे uv की संभावना उनके संबंधित वैक्टर के डॉट प्रोडक्ट u • v का कार्य है।

नेटवर्क संभाव्यता मैट्रिक्स किनारे की संभावनाओं के माध्यम से यादृच्छिक रेखांकन करता है। जो $p_{i,j}$ संभावना का प्रतिनिधित्व करता है। वह दिया हुआ किनारा $e_{i,j}$ एक निर्दिष्ट समय अवधि के लिए उपस्थित है। यह मॉडल निर्देशित और अप्रत्यक्ष रूप से एक्स्टेंसिबल है; भारित और भारित और स्थिर या गतिशील रेखांकन संरचना भी उस्थित होता है।

M ≃ pN के लिए, जहां N संभव किनारों की अधिकतम संख्या है, दो सबसे व्यापक रूप से प्रयोग किए जाने वाले मॉडल, G(n,M) और G(n,p) लगभग विनिमेय हैं।

यादृच्छिक नियमित ग्राफ एक विशेष स्थिति बनाते हैं। ऐसे गुणों के साथ जो सामान्य रूप से रैंडम ग्राफ़ से भिन्न हो सकते हैं।

एक बार जब हमारे पास यादृच्छिक ग्राफ़ का एक मॉडल होता है। तो ग्राफ़ पर प्रत्येक फलन यादृच्छिक चर बन जाता है। इस मॉडल का अध्ययन यह निर्धारित करने के लिए है कि क्या या कम से कम संभावना का अनुमान है कि एक गुण हो सकती है।

शब्दावली

यादृच्छिक ग्राफ के संदर्भ में 'लगभग हर' शब्द रिक्त स्थान और संभावनाओं के अनुक्रम को संदर्भित करता है, जैसे कि त्रुटि संभावना शून्य हो जाती है।

गुण

यादृच्छिक रेखांकन का सिद्धांत यादृच्छिक रेखांकन के विशिष्ट गुणों का अध्ययन करता है, जो किसी विशेष वितरण से तैयार किए गए रेखांकन के लिए उच्च संभावना रखते हैं। उदाहरण के लिए, हम दिए गए मान के लिए पूछ सकते हैं $n$ और $p$ इसकी क्या संभावना है $G(n,p)$ कनेक्शन (गणित) है। ऐसे प्रश्नों का अध्ययन करने में, शोधकर्ता अक्सर यादृच्छिक रेखांकन के स्पर्शोन्मुख व्यवहार पर ध्यान केंद्रित करते हैं - वे मूल्य जो विभिन्न संभावनाओं के रूप में परिवर्तित होते हैं $n$ बहुत बड़ा हो जाता है। परकोलेशन सिद्धांत यादृच्छिक रेखांकन की संबद्धता की विशेषता बताता है, विशेष रूप से असीम रूप से बड़े वाले।

परकोलेशन ग्राफ की मजबूती से संबंधित है (जिसे नेटवर्क भी कहा जाता है)। का एक यादृच्छिक ग्राफ दिया $n$ नोड्स और एक औसत डिग्री $\langle k\rangle$. अगला हम बेतरतीब ढंग से एक अंश निकालते हैं $1-p$ नोड्स की और केवल एक अंश छोड़ दें $p$. एक महत्वपूर्ण रिसाव सीमा उपस्थित है $p_{c}={\tfrac {1}{\langle k\rangle }}$ जिसके नीचे ऊपर रहते हुए नेटवर्क खंडित हो जाता है $p_{c}$ एक विशाल जुड़ा हुआ घटक उपस्थित है।

स्थानीयकृत परकोलेशन एक नोड को उसके पड़ोसियों, अगले निकटतम पड़ोसियों आदि को एक अंश तक हटाने के लिए संदर्भित करता है $1-p$ नेटवर्क से नोड्स हटा दिए जाते हैं। यह दिखाया गया था कि डिग्री के प्वासों वितरण के साथ यादृच्छिक ग्राफ के लिए $p_{c}={\tfrac {1}{\langle k\rangle }}$ बिल्कुल यादृच्छिक हटाने के लिए।

संभाव्यता पद्धति में रैंडम ग्राफ़ का व्यापक रूप से उपयोग किया जाता है, जहाँ कोई कुछ गुणों वाले ग्राफ़ के अस्तित्व को सिद्ध करने का प्रयास करता है। एक यादृच्छिक ग्राफ पर एक गुण का अस्तित्व अक्सर ज़ेमेरीडी नियमितता लेम्मा के माध्यम से, लगभग सभी ग्राफों पर उस गुण के अस्तित्व का संकेत दे सकता है।

यादृच्छिक नियमित रेखांकन में, $G(n,r-reg)$ का समूह हैं $r$-नियमित रेखांकन के साथ $r=r(n)$ ऐसा है कि $n$ और $m$ प्राकृतिक संख्या हैं, $3\leq r<n$, और $rn=2m$ सम है।

एक ग्राफ का डिग्री अनुक्रम $G$ में $G^{n}$ समूह में केवल किनारों की संख्या पर निर्भर करता है:$V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.$ अगर किनारे, $M$ एक यादृच्छिक ग्राफ में $G_{M}$ यह सुनिश्चित करने के लिए काफी बड़ा है कि लगभग हर $G_{M}$ न्यूनतम डिग्री कम से कम 1 है, तो लगभग हर $G_{M}$ जुड़ा हुआ है और, अगर $n$ सम है, लगभग हर $G_{M}$ पूर्ण मिलान है। विशेष रूप से, जिस क्षण लगभग हर यादृच्छिक ग्राफ में अंतिम पृथक शीर्ष गायब हो जाता है, ग्राफ जुड़ा हो जाता है।

लगभग हर ग्राफ़ प्रक्रिया सम संख्याओं पर होती है, जिसके किनारे न्यूनतम डिग्री को 1 तक बढ़ाते हैं या एक यादृच्छिक ग्राफ़ से थोड़ा अधिक होता है ${\tfrac {n}{4}}\log(n)$ किनारों और 1 के करीब संभावना के साथ यह सुनिश्चित करता है कि ग्राफ़ में पूर्ण मिलान हो, अधिकतम एक शीर्ष के अपवाद के साथ।

कुछ स्थिर के लिए $c$, लगभग हर लेबल वाले ग्राफ़ के साथ $n$ शिखर और कम से कम $cn\log(n)$ किनारों हैमिल्टनियन चक्र है। प्रायिकता 1 की ओर अग्रसर होने के साथ, वह विशेष किनारा जो न्यूनतम डिग्री को 2 तक बढ़ाता है, ग्राफ को हैमिल्टनियन बनाता है।

यादृच्छिक ग्राफ के गुण ग्राफ परिवर्तनों के तहत बदल सकते हैं या अपरिवर्तित रह सकते हैं। उदाहरण के लिए, अलिर्ज़ा माशघी | मशघी ए. एट अल। ने प्रदर्शित किया कि एक परिवर्तन जो यादृच्छिक ग्राफ़ को उनके किनारे-दोहरे ग्राफ़ (या लाइन ग्राफ़) में परिवर्तित करता है, लगभग समान डिग्री वितरण के साथ ग्राफ़ का एक समूह बनाता है, लेकिन डिग्री सहसंबंध और ए के साथ महत्वपूर्ण रूप से उच्च क्लस्टरिंग गुणांक।

रंग

शीर्ष V (G) = {1, ..., n} के साथ ऑर्डर n के एक यादृच्छिक ग्राफ G को देखते हुए, रंगों की संख्या पर लालची एल्गोरिथ्म द्वारा, रंगों को 1, 2, ... रंगों से रंगा जा सकता है। (शीर्ष 1 रंगीन 1 है, शीर्ष 2 रंगीन 1 है यदि यह शीर्ष 1 के निकट नहीं है, अन्यथा यह 2 रंगीन है, आदि)।कई क्यू रंगों को दिए गए यादृच्छिक ग्राफ़ के उचित रंगों की संख्या, जिसे इसके रंगीन बहुपद कहा जाता है, अब तक अज्ञात है। पैरामीटर n और किनारों की संख्या m या कनेक्शन प्रायिकता p के साथ यादृच्छिक ग्राफ़ के रंगीन बहुपद के शून्य के स्केलिंग को सांकेतिक पैटर्न मिलान के आधार पर एक एल्गोरिथ्म का उपयोग करके अनुभवजन्य रूप से अध्ययन किया गया है।

रैंडम पेड़

Main article: Random tree

एक रैंडम ट्रीप एक ट्री (ग्राफ थ्योरी) या आर्बोरेसेंस (ग्राफ थ्योरी) है जो एक स्टोचैस्टिक प्रक्रिया द्वारा बनता है। क्रम n और आकार M(n) के यादृच्छिक रेखांकन की एक बड़ी श्रृंखला में क्रम k के पेड़ घटकों की संख्या का वितरण विषम रूप से पॉइसन वितरण है। यादृच्छिक पेड़ के प्रकारों में एक समान फैला हुआ पेड़ , यादृच्छिक न्यूनतम फैले पेड़, यादृच्छिक बाइनरी ट्री , ट्रैप, तेजी से रैंडम ट्री, ब्राउनियन पेड़ और यादृच्छिक वन शामिल हैं।

सशर्त यादृच्छिक रेखांकन

संभाव्यता स्थान पर परिभाषित दिए गए यादृच्छिक ग्राफ मॉडल पर विचार करें $(\Omega ,{\mathcal {F}},P)$ और जाने ${\mathcal {P}}(G):\Omega \rightarrow R^{m}$ एक वास्तविक मूल्यवान फलन बनें जो प्रत्येक ग्राफ़ को निर्दिष्ट करता है $\Omega$ एम गुणों का एक वेक्टर। एक निश्चित के लिए $\mathbf {p} \in R^{m}$, सशर्त यादृच्छिक रेखांकन वे मॉडल हैं जिनमें संभाव्यता मापी जाती है $P$ सभी ग्राफों को शून्य प्रायिकता प्रदान करता है जैसे कि '${\mathcal {P}}(G)\neq \mathbf {p}$.

विशेष मामले सशर्त रूप से समान यादृच्छिक ग्राफ हैं, जहां $P$ निर्दिष्ट गुणों वाले सभी ग्राफ़ों को समान संभावना प्रदान करता है। उन्हें एर्डोस-रेनी मॉडल जी (एन, एम) के सामान्यीकरण के रूप में देखा जा सकता है, जब कंडीशनिंग जानकारी जरूरी नहीं कि किनारों की संख्या एम हो, लेकिन जो भी अन्य मनमाने ढंग से ग्राफ गुण है ${\mathcal {P}}(G)$. इस मामले में बहुत कम विश्लेषणात्मक परिणाम उपलब्ध हैं और औसत गुणों के अनुभवजन्य वितरण प्राप्त करने के लिए सिमुलेशन की आवश्यकता है।

इतिहास

रैंडम ग्राफ मॉडल का सबसे पहला उपयोग 1938 में हेलेन हॉल जेनिंग्स और याकूब मोरेनो द्वारा किया गया था, जहां यादृच्छिक मॉडल के साथ उनके नेटवर्क डेटा में पारस्परिक लिंक के अंश की तुलना करने के अध्ययन में एक चांस सोशियोग्राम (एक निर्देशित एर्दोस-रेनी मॉडल) पर विचार किया गया था। 1951 में रे सोलोमनॉफ़ और अनातोल रैपोपोर्ट द्वारा रेंडम नेट नाम के तहत एक और प्रयोग, निश्चित आउट-डिग्री के साथ निर्देशित ग्राफ़ के एक मॉडल का उपयोग करके और बेतरतीब ढंग से चुने गए अनुलग्नकों को अन्य कोने में किया गया था। रैंडम ग्राफ़ के एर्डोस-रेनी मॉडल को पहली बार पॉल एर्दोस और अल्फ्रेड रेनी द्वारा उनके 1959 के पेपर ऑन रैंडम ग्राफ़ में परिभाषित किया गया था। और स्वतंत्र रूप से गिल्बर्ट द्वारा अपने पेपर रैंडम ग्राफ़ में।

यह भी देखें

• बोस-आइंस्टीन संक्षेपण: एक नेटवर्क सिद्धांत दृष्टिकोण
• गुहा विधि
• जटिल नेटवर्क
• दोहरे चरण का विकास
• एर्डोस-रेनी मॉडल
• घातीय यादृच्छिक ग्राफ मॉडल
• ग्राफ सिद्धांत
• अन्योन्याश्रित नेटवर्क
• नेटवर्क विज्ञान
• टपकन
• परकोलेशन थ्योरी
• जेलेशन का रैंडम ग्राफ थ्योरी
• नियमित ग्राफ
• स्केल मुक्त नेटवर्क
• सेमीलाइनर प्रतिक्रिया
• स्टोकेस्टिक ब्लॉक मॉडल
• लांचिनेट्टी-फॉर्चुनैटो-रेडिची बेंचमार्क

संदर्भ

*