आव्रजन करने वाले शीर्षकों के साथ एक यादृच्छिक ग्राफ: विशाल घटक का उद्भव

एक यादृच्छिक रूप से विकसित होने वाले ग्राफ का अध्ययन किया गया है, जिसमें शीर्षकों का आव्रजन दर n पर और प्रत्येक संभावित किनारे का उभरना दर 1/n पर होता है। O(n2/3) शीर्षों के साथ विशाल घटकों के उद्भव की विस्तृत तस्वीर प्रदर्शित की गई है, जो प्रारंभ में शीर्षों की संख्या n निर्धारित होने के साथ Erdős–Rényi ग्राफ प्रक्रिया में समान है। एक महत्वपूर्ण अंतर यह है कि अब संक्रमण लगभग समय t=π/2 पर होता है, बजाय t=1 के। प्रमाण में तीन तत्व होते हैं। उप-आकर्षित चरण में सबसे बड़े घटक का आकार एक विशेष बहु-प्रकार शाखा प्रक्रिया के साथ तुलना द्वारा सीमित है। इस सीमा को ध्यान में रखते हुए, घटक आकारों के वर्गों का योग और घन का विकास, मार्टिंगेल विधियों के माध्यम से, Smoluchowsky-प्रकार समीकरणों का समाधान निकटता से पालन करना प्रकट किया गया है। यह समीकरण हमें Aldous ब्राउनियन एक्सकर्शन, गंभीर यादृच्छिक ग्राफ और गुणनात्मक कोलसेंट, Ann Probab 25 (1997), 812–854 के परिणामों को लागू करने की अनुमति देता है, जो गुणनात्मक कोलसेंट में विशाल घटकों के उद्भव के लिए है, अर्थात्, एक गैर-समरूप यादृच्छिक ग्राफ प्रक्रिया। © 2000 जॉन वेली एंड संस, इंक। यादृच्छिक संरचना। एल्गोरिदम, 17: 79–102, 2000.