मैं कुछ चीजों के साथ खेल रहा हूं और Kevin Bacon संख्याओं को समझने का प्रयास करने का विचार सोचा। मेरे पास एक साइट के लिए डेटा है कि इस उद्देश्य के लिए हम एक सोशल नेटवर्क पर विचार कर सकते हैं। आइए दिखाएं कि यह फेसबुक है (चर्चा के सरलीकरण के लिए)। मेरे पास लोग हैं और मेरे पास उनके दोस्तों की एक सूची है, इसलिए मेरे बीच कनेक्शन हैं। मैं एक व्यक्ति से दूसरी दूरी की दूरी की गणना कैसे कर सकता हूं (मूल रूप से, केविन बेकन संख्या)?"केविन बेकन" संख्याओं की गणना
मेरा सबसे अच्छा विचार Bidirectional search है, गहराई सीमा (कम्प्यूटेशनल जटिलता को सीमित करने और उन लोगों की समस्या से बचने के लिए जो ग्राफ में कनेक्ट नहीं हो सकते हैं), लेकिन मुझे एहसास है कि यह बल्कि बलवान बल है।
क्या छोटे उप-ग्राफ (फेसबुक पर समूहों के बराबर कुछ कहने के लिए) बेहतर हो सकता है, उनके बीच की छोटी दूरी (शायद समय से पहले) की गणना करें और फिर लिंक खोजने के लिए उनका उपयोग करने का प्रयास करें? हालांकि इसे पूर्व-गणना की आवश्यकता है, यह कई कम नोड्स को खोजना संभव कर सकता है (नोड्स व्यक्तियों के बजाय समूह हो सकते हैं, जिससे ग्राफ बहुत छोटा हो सकता है)। हालांकि यह अभी भी एक द्विपक्षीय खोज होगी।
मैं "लोकप्रिय" लोगों के लिए नोड्स की खोज करने वाले लोगों की संख्या की पूर्व-गणना भी कर सकता हूं क्योंकि उन्हें दिए गए गंतव्य व्यक्ति से जुड़ने का सबसे अच्छा मौका मिल सकता है। मुझे एहसास है कि यह संभवतः सबसे कम पथ के लिए गति का व्यापार-बंद होगा। मुझे लगता है कि मैं चौड़ाई की पहली खोज के बजाय गहराई से पहली खोज का उपयोग करना चाहता हूं, जिसे मैं अन्य मामलों में उपयोग करने की योजना बनाउंगा।
क्या कोई ऐसा करने का एक सरल/तेज़ तरीका सोच सकता है? मैं दो लोगों के बीच सबसे छोटी लंबाई खोजने में सक्षम होना चाहता हूं, इसलिए यह हमेशा एक ही अंत बिंदु (जैसे केविन बेकन समस्या में) के रूप में आसान नहीं है।
मुझे एहसास है कि ऐसी समस्याएं हैं जैसे मुझे 200 लोगों की श्रृंखला मिल सकती है, लेकिन यह मुझे हल करने के लिए तैयार की गई गहराई तक सीमित हो सकती है।
बीटीडब्ल्यू, चूंकि यह फिल्मों के बारे में नहीं है, इसलिए इसे अधिक परिचित (कुछ ;-)) Erdős संख्या के बजाय केविन बेकन नंबर पर कॉल करने के लिए कोई अनिवार्य कारण नहीं है: http://en.wikipedia.org/wiki/Erdos_number – ShreevatsaR
मैंने कुछ शोध करते समय उस शब्द को देखा, लेकिन इसे केविन बेकन नंबर पर कॉल करके हर कोई तुरंत जानता है कि मैं किस बारे में बात कर रहा हूं। मुझे लगा कि व्याख्या करने पर कटौती होगी। – MBCook
"अलगाव की डिग्री" भी समझ में आएगी –