Erdős–Rényi model
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एर्डोस-रेनी मॉडल यादृच्छिक ग्राफ उत्पन्न करने या यादृच्छिक नेटवर्क के विकास के लिए दो निकट से संबंधित मॉडल में से एक को संदर्भित करता है। इन मॉडलों का नाम हंगरी के गणितविदों पॉल एर्दोस और अल्फ्रेड रेनी के नाम पर रखा गया है, जिन्होंने 1959 में एक मॉडल पेश किया था। एडगर गिल्बर्ट ने दूसरे मॉडल को समकालीन रूप से एर्डोस और रेनी के साथ और स्वतंत्र रूप से पेश किया। एर्डोस और रेनी के मॉडल में, किनारों की एक निश्चित संख्या के साथ एक निश्चित शीर्ष सेट पर सभी ग्राफ समान रूप से संभावित हैं। गिल्बर्ट द्वारा पेश किए गए मॉडल में, जिसे एर्दोस-रेनी-गिल्बर्ट मॉडल भी कहा जाता है, प्रत्येक किनारे में अन्य किनारों से स्वतंत्र रूप से मौजूद या अनुपस्थित होने की एक निश्चित संभावना होती है। इन मॉडलों का उपयोग संभावित विधि में विभिन्न गुणों को संतुष्ट करने वाले ग्राफों के अस्तित्व को साबित करने के लिए किया जा सकता है, या लगभग सभी ग्राफों के लिए किसी गुण के धारण करने का क्या अर्थ है, इसकी एक कठोर परिभाषा प्रदान करने के लिए किया जा सकता है। परिभाषा एर्दोस-रेनी यादृच्छिक ग्राफ मॉडल के दो निकट से संबंधित रूप हैं। मॉडल में, एक ग्राफ को उन सभी ग्राफों के संग्रह से यादृच्छिक रूप से समान रूप से चुना जाता है जिनमें नोड्स और किनारे होते हैं। नोड्स को लेबल किया गया माना जाता है, जिसका अर्थ है कि शीर्षों को क्रमबद्ध करके एक दूसरे से प्राप्त ग्राफ को अलग माना जाता है। उदाहरण के लिए, मॉडल में, तीन लेबल वाले शीर्षों पर तीन दो-किनारे वाले ग्राफ हैं (दो-किनारे वाले मार्ग में मध्य शीर्ष के प्रत्येक विकल्प के लिए एक), और इन तीन ग्राफों में से प्रत्येक को संभावना के साथ शामिल किया गया है। मॉडल में, लेबल किए गए नोड्स को यादृच्छिक रूप से जोड़कर एक ग्राफ का निर्माण किया जाता है। प्रत्येक किनारे को ग्राफ में संभावना के साथ शामिल किया गया है, स्वतंत्र रूप से हर दूसरे किनारे से। समान रूप से, नोड्स और किनारों वाले प्रत्येक ग्राफ को उत्पन्न करने की संभावना है इस मॉडल में पैरामीटर को एक भार फलन के रूप में सोचा जा सकता है; जैसे-जैसे यह बढ़ता जाता है, मॉडल में अधिक किनारों वाले ग्राफ शामिल होने की संभावना अधिक होती जाती है और कम किनारों वाले ग्राफ को शामिल करने की संभावना कम होती जाती है। विशेष रूप से, मामला उस मामले से मेल खाता है जहां शीर्षों पर सभी ग्राफ समान संभावना के साथ चुने जाते हैं। यादृच्छिक आलेखों के व्यवहार का अध्ययन अक्सर उस मामले में किया जाता है जहां शीर्षों की संख्या अनंत हो जाती है। यद्यपि और इस मामले में तय किया जा सकता है, वे इसके आधार पर कार्य भी हो सकते हैं। उदाहरण के लिए, इस कथन का कि लगभग हर ग्राफ जुड़ा हुआ है, इसका मतलब है कि, जैसा कि अनंत की ओर जाता है, संभावना है कि किनारे की संभावना के साथ शीर्षों पर एक ग्राफ जुड़ा हुआ है। दो मॉडलों के बीच तुलना जी (एन, पी) में किनारों की अपेक्षित संख्या है, और बड़ी संख्या के नियम के अनुसार जी (एन, पी) में किसी भी ग्राफ में लगभग इतने किनारे होंगे (बशर्ते किनारों की अपेक्षित संख्या अनंत हो)। इसलिए, एक मोटा अनुमान यह है कि यदि pn2 → φ है, तो G (n, p) को G (n, M) के समान व्यवहार करना चाहिए जैसे जैसे n बढ़ता है। कई ग्राफ गुणों के लिए, यह मामला है। यदि पी कोई ग्राफ गुण है जो उपग्राफ क्रम के संबंध में मोनोटोन है (जिसका अर्थ है कि यदि ए बी का उपग्राफ है और बी पी को संतुष्ट करता है, तो ए पी को भी संतुष्ट करेगा), तो कथन "पी जी (एन, पी) में लगभग सभी ग्राफों के लिए धारण करता है" और "पी लगभग सभी ग्राफों के लिए धारण करता है" समतुल्य हैं (बशर्ते पीएन2 → φ)। उदाहरण के लिए, यह तब लागू होता है जब पी जुड़े होने का गुण है, या यदि पी हैमिल्टनियन चक्र को धारण करने का गुण है। हालाँकि, यह आवश्यक रूप से गैर-मोनोटोन गुणों के लिए लागू नहीं होगा (जैसे। किनारों की सम संख्या होने का गुण)। व्यवहार में, जी (एन, पी) मॉडल आज अधिक सामान्य रूप से उपयोग किया जाता है, आंशिक रूप से किनारों की स्वतंत्रता द्वारा अनुमत विश्लेषण की आसानी के कारण। जी (एन, पी) के गुण उपरोक्त संकेतन के साथ, जी (एन, पी) में एक ग्राफ के औसत किनारे होते हैं। किसी विशेष शीर्ष की डिग्री का वितरण द्विपद हैः जहाँ n ग्राफ में शीर्षों की कुल संख्या है। चूँकि यह वितरण बड़े n और np = स्थिरांक के लिए पॉइसन है। 1960 के एक शोधपत्र में, एर्दोस और रेनी ने पी के विभिन्न मूल्यों के लिए जी (एन, पी) के व्यवहार का बहुत सटीक रूप से वर्णन किया। उनके परिणामों में शामिल था किः यदि एनपी <1 है, तो जी (एन, पी) में एक ग्राफ में लगभग निश्चित रूप से ओ (लॉग (एन)) से बड़े आकार के कोई जुड़े हुए घटक नहीं होंगे। यदि np = 1 है, तो G (n, p) में एक ग्राफ में लगभग निश्चित रूप से एक सबसे बड़ा घटक होगा जिसका आकार n2/3 क्रम का होगा। यदि np → c> 1, जहाँ c एक स्थिरांक है, तो G (n, p) में एक ग्राफ में लगभग निश्चित रूप से एक अद्वितीय विशाल घटक होगा जिसमें शीर्षों का एक सकारात्मक अंश होगा। किसी अन्य घटक में ओ (लॉग (एन)) शीर्ष से अधिक नहीं होगा। यदि, तो जी (एन, पी) में एक ग्राफ में लगभग निश्चित रूप से अलग-अलग शीर्ष होंगे, और इस प्रकार डिस्कनेक्ट हो जाएंगे। यदि, तो जी (एन, पी) में एक ग्राफ लगभग निश्चित रूप से जुड़ा होगा। इस प्रकार जी (एन, पी) के जुड़ाव के लिए एक तेज सीमा है। ग्राफ के आगे के गुणों को लगभग सटीक रूप से वर्णित किया जा सकता है क्योंकि n अनंत की ओर जाता है। उदाहरण के लिए, एक k (n) (लगभग 2log2 (n) के बराबर) ऐसा है कि G (n, 0.5) में सबसे बड़े गुट का लगभग निश्चित रूप से आकार k (n) या k (n) + 1 है। इस प्रकार, भले ही एक ग्राफ में सबसे बड़े गुट का आकार खोजना एनपी-पूर्ण है, एक "विशिष्ट" ग्राफ में सबसे बड़े गुट का आकार (इस मॉडल के अनुसार) बहुत अच्छी तरह से समझा जाता है। एर्डोस-रेनी ग्राफ के किनारे-दोहरे ग्राफ लगभग समान डिग्री वितरण वाले ग्राफ हैं, लेकिन डिग्री सहसंबंध और काफी अधिक क्लस्टरिंग गुणांक के साथ। परकोलेशन से संबंध परकोलेशन सिद्धांत में एक सीमित या अनंत ग्राफ की जांच की जाती है और किनारों (या लिंक) को यादृच्छिक रूप से हटा दिया जाता है। इस प्रकार एर्दोस-रेनी प्रक्रिया वास्तव में पूरे ग्राफ पर भारित लिंक परकोलेशन नहीं है। (एक उस परकोलेशन को संदर्भित करता है जिसमें भारित परकोलेशन के रूप में विषम भार के साथ नोड्स और/या लिंक को हटा दिया जाता है)। चूंकि परकोलेशन सिद्धांत की जड़ें भौतिकी में हैं, इसलिए किए गए अधिकांश शोध यूक्लिडियन रिक्त स्थान में जाली पर थे। एन. पी. = 1 पर विशाल घटक से छोटे घटक में संक्रमण इन ग्राफों के लिए अनुरूप है, लेकिन जाली के लिए संक्रमण बिंदु निर्धारित करना मुश्किल है। भौतिक विज्ञानी अक्सर पूर्ण ग्राफ के अध्ययन को एक औसत क्षेत्र सिद्धांत के रूप में संदर्भित करते हैं। इस प्रकार एर्दोस-रेनी प्रक्रिया परकोलेशन का माध्य-क्षेत्र मामला है। यादृच्छिक ग्राफ पर परकोलेशन पर भी कुछ महत्वपूर्ण काम किया गया था। एक भौतिक विज्ञानी के दृष्टिकोण से यह अभी भी एक औसत-क्षेत्र मॉडल होगा, इसलिए अनुसंधान के औचित्य को अक्सर ग्राफ की मजबूती के संदर्भ में तैयार किया जाता है, जिसे एक संचार नेटवर्क के रूप में देखा जाता है। एक औसत डिग्री के साथ n′1 नोड्स का यादृच्छिक ग्राफ दिया गया है। यादृच्छिक रूप से नोड्स के एक अंश को हटा दें और नेटवर्क से केवल एक अंश छोड़ दें। एक महत्वपूर्ण परकोलेशन सीमा मौजूद है जिसके नीचे नेटवर्क खंडित हो जाता है जबकि ऊपर क्रम n का एक विशाल जुड़ा हुआ घटक मौजूद होता है। विशाल घटक का सापेक्ष आकार, पी, कैविट्स द्वारा दिया गया है जी (एन, पी) मॉडल की दो प्रमुख धारणाएँ (कि किनारे स्वतंत्र हैं और प्रत्येक किनारा समान रूप से संभावित है) कुछ वास्तविक जीवन की घटनाओं के मॉडलिंग के लिए अनुचित हो सकते हैं। एर्डोस-रेनी ग्राफ में कई सामाजिक नेटवर्कों के विपरीत, कम क्लस्टरिंग होती है। कुछ मॉडलिंग विकल्पों में बाराबासी-अल्बर्ट मॉडल और वाट्स और स्ट्रोगात्ज़ मॉडल शामिल हैं। ये वैकल्पिक मॉडल परकोलेशन प्रक्रियाएं नहीं हैं, बल्कि क्रमशः विकास और पुनः वायरिंग मॉडल का प्रतिनिधित्व करते हैं। यादृच्छिक ग्राफ मॉडल का एक अन्य वैकल्पिक परिवार, जो कई वास्तविक जीवन की घटनाओं को पुनः पेश करने में सक्षम है, घातीय यादृच्छिक ग्राफ मॉडल हैं। जी (एन, पी) मॉडल को पहली बार एडगर गिल्बर्ट द्वारा 1959 के एक पेपर में ऊपर उल्लिखित संपर्क सीमा का अध्ययन करते हुए पेश किया गया था। जी (एन, एम) मॉडल को एर्दोस और रेनी ने अपने 1959 के पेपर में पेश किया था। गिल्बर्ट के साथ, उनकी पहली जांच जी (एन, एम) के संपर्क के बारे में थी, जिसके बाद 1960 में अधिक विस्तृत विश्लेषण किया गया। महत्वपूर्ण जी (एन, पी) का निरंतरता सीमा प्रतिनिधित्व ग्राफ की एक निरंतरता सीमा तब प्राप्त की गई थी जब वह क्रम में हो। विशेष रूप से, ग्राफ के अनुक्रम पर विचार करें। सीमा वस्तु का निर्माण निम्नानुसार किया जा सकता हैः सबसे पहले, एक प्रसार उत्पन्न करें जहां एक मानक ब्राउनियन गति है। इस प्रक्रिया से हम प्रतिबिंबित प्रक्रिया को परिभाषित करते हैं। इस प्रक्रिया को कई क्रमिक भ्रमणों के रूप में देखा जा सकता है (ब्राउनियन भ्रमण नहीं, देखें)। क्योंकि के बहाव पर हावी है, ये भ्रमण छोटे और छोटे हो जाते हैं। विशेष रूप से, उन्हें घटती लंबाई के क्रम में क्रमबद्ध किया जा सकता हैः हम घटती लंबाई के अंतराल में विभाजित कर सकते हैं जैसे कि किसी के लिए ब्राउनियन भ्रमण तक सीमित है। अब, एक यात्रा पर विचार करें। एक यादृच्छिक ग्राफ निम्नानुसार बनाएँः एक वास्तविक वृक्ष का निर्माण करें (ब्राउनियन वृक्ष देखें)। इकाई तीव्रता के साथ एक पॉइसन बिंदु प्रक्रिया पर विचार करें। प्रत्येक बिंदु के लिए, एक अंतर्निहित आंतरिक नोड और पेड़ के एक पत्ते से मेल खाता है। दो शीर्षों की पहचान करते हुए, वृक्ष एक ग्राफ बन जाता है इस प्रक्रिया को लागू करते हुए, घटते आकार के यादृच्छिक अनंत ग्राफ का एक क्रम प्राप्त होता हैः प्रमेय में कहा गया है कि यह ग्राफ एक निश्चित अर्थ में सीमा वस्तु से मेल खाता है। यह भी देखें कि जी (एन, पी) मॉडल को ग्राफ तक विस्तारित करके बनाया गया ग्राफ जिसमें शिखरों की गिनती अनंत संख्या में है। परिमित मामले के विपरीत, इस अनंत प्रक्रिया का परिणाम (संभावना 1 के साथ) समरूपता तक एक ही ग्राफ है। यह उन तरीकों का वर्णन करता है जिनमें एर्डोस-रेनी मॉडल से जुड़े गुण प्रणालियों में क्रम के उद्भव में योगदान करते हैं। नेटवर्क सांख्यिकी के एक समूह और उनसे जुड़े विभिन्न मापदंडों को देखते हुए "एन" नोड्स पर ग्राफ के सामान्य संभाव्यता वितरण का वर्णन करें। , अव्यक्त सामुदायिक संरचना के साथ ग्राफ के लिए एर्दोस-रेनी मॉडल का एक सामान्यीकरण संदर्भ साहित्य वेबलिंक्स वीडियोः एर्दोस-रेनी यादृच्छिक ग्राफ यादृच्छिक ग्राफ रेनी मॉडल