संरचित रैन्डम ग्राफ़ में समुदायों की पुनर्प्राप्ति

रैन्डम ग्राफ़ में लगाए गए समुदाय संरचना को पुनः प्राप्त करने की समस्या ने स्टोकास्टिक ब्लॉक मॉडल पर साहित्य में बहुत ध्यान आकर्षित किया है, जहां इनपुट एक रैन्डम ग्राफ़ होता है जिसमें विभिन्न समुदायों के बीच पार करने वाले किनारे छोटे संभाव्यता के साथ प्रकट होते हैं, यह किनारों की तुलना में जो समुदायों द्वारा प्रेरित होते हैं। समुदाय अपने आप में अपेक्षित ग्राफ़ में शिखर-स्वतंत्र बिखरे हुए कट का एक संग्रह बनाते हैं, और इन्हें पुनर्प्राप्त किया जा सकता है, अक्सर सटीक रूप से, एक नमूने से जब तक इंट्रा- और अंतर-कम्युनिटी किनारे की संभावनाओं पर एक अलगाव की स्थिति संतुष्ट होती है। इस पेपर में, हम पूछते हैं कि क्या अपेक्षित ग्राफ़ में भारी मात्रा में ओवरलैपिंग बिखरे हुए कट की उपस्थिति अभी भी पुनर्प्राप्ति की अनुमति देती है। उदाहरण के लिए, d-आयामी हाइपरक्यूब ग्राफ़ d विशेष (संतुलित) बिखरे हुए कट की अनुमति देता है, हर श्रेणी के लिए एक। क्या इन कटों की पहचान की जा सकती है यदि हाइपरक्यूब के किनारों का एक रैन्डम नमूना दिया गया हो जहां प्रत्येक किनारा कुछ संभाव्यता p ∈ (0, 1) के साथ स्वतंत्र रूप से मौजूद है? हम दिखाते हैं कि ऐसा होता है, एक बहुत मजबूत अर्थ में: हाइपरक्यूब के एक नमूने में संतुलित बिखरा हुआ कट दर p = Clog d/d पर पर्याप्त बड़े स्थिरांक C के लिए 1/poly(d)-निकट होता है। यह असंप्रदायिक रूप से अनुकूल है और सभी d कटों की समानांतर पुनर्प्राप्ति की अनुमति देता है। इसके अलावा, हाइपरक्यूब-मॉडल ग्राफ़ का एक उपयुक्त नमूना बनाकर पुनर्प्राप्ति को सटीक बनाया जा सकता है। प्रमाण वास्तविकता यह है कि यह एक मजबूत हाइपरक्यूब कट संकुचन सीमा है जो फ्रॉइडगुट, कालाई और नॉर के एक प्रमेय को संयोजित करता है जो बूलियन कार्यों पर है जिनका फूरियर ट्रांसफ़ॉर्म पहले स्तर के फूरियर स्पेक्ट्रम पर केंद्रित होता है, केगर के कट गिनने के तर्क के साथ।