मेरे पास उन लोगों के बीच 20 मिलियन उपयोगकर्ता और कनेक्शन का डेटाबेस है। प्रोग्रामिंग में सबसे प्रभावी तरीके में "छः डिग्री पृथक्करण" अवधारणा की अवधारणा को मैं कैसे साबित कर सकता हूं?मैं प्रोग्रामिंग के "छः डिग्री पृथक्करण" अवधारणा को कैसे साबित कर सकता हूं?
link to the article about Six degrees of separation
तुम बस diameter of the graph. को मापने के लिए यह वास्तव में एक ग्राफ में सबसे ज्यादा दूर से जुड़े नोड्स के बीच जुदाई पता लगाने के लिए मीट्रिक है चाहता हूँ।
Google पर बहुत सारे एल्गोरिदम, Boost graph भी।
आप शायद स्मृति में ग्राफ को फिट कर सकते हैं (प्रतिनिधित्व में कि प्रत्येक चरम अपने पड़ोसियों की सूची जानता है)।
फिर, प्रत्येक vertex n से, आप 6 की गहराई तक एक चौड़ाई वाली पहली खोज (कतार का उपयोग करके) चला सकते हैं और देखे गए शिखरों की संख्या गिन सकते हैं। यदि सभी शीर्षकों का दौरा नहीं किया जाता है, तो आपने प्रमेय को अस्वीकार कर दिया है। दूसरे मामले में, अगले vertex n के साथ जारी रखें।
यह ओ (एन * (एन + #edges)) = एन * (एन + एन * 100) = 100 एन^2 है, यदि उपयोगकर्ता औसत पर 100 कनेक्शन हैं, जो एन = 20 मिलियन के लिए आदर्श नहीं है। मुझे आश्चर्य है कि उल्लिखित पुस्तकालय बेहतर समय जटिलता में व्यास की गणना कर सकते हैं (सामान्य एल्गोरिदम ओ (एन^3) है)।
व्यक्तिगत शिखर के लिए गणना स्वतंत्र हैं, इसलिए वे समानांतर में किए जा सकते हैं।
थोड़ा ह्युरिस्टिक: उन शीर्षकों से शुरू करें जिनमें सबसे कम डिग्री (प्रमेय को अस्वीकार करने का बेहतर मौका) है।
मुझे लगता है कि यह ओ (एन^2) से काफी खराब है। यह भी मानते हुए कि प्रत्येक नोड केवल 3 अन्य नोड्स से जुड़ा हुआ है, गहराई 6 का एक स्टैक ट्रेस 3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5। घातीय वृद्धि – patros
प्रत्येक कशेरुक के लिए आप प्रत्येक चरम पर सबसे अधिक बार जाते हैं, इसलिए एक चरम के लिए दौड़ ओ (एन) लेता है। –
आह, सच है, यह उस पर एक सीमा है। मुझे लगता है कि यह अभी भी ओ (एन^3) है, है ना? वर्टेक्स ए से वर्टेक्स बी से पथ ढूंढना ओ (एन) है, और आपको यह ओ (एन^2) बार करना होगा। – patros
मुझे लगता है कि सबसे प्रभावी तरीका (सबसे खराब मामला) लगभग एन^3 है। एक आसन्न मैट्रिक्स बनाएं, और उसके बाद उस मैट्रिक्स^2,^3,^4,^5 और^6 लें। ग्राफिक्स में किसी भी प्रविष्टि की तलाश करें जो मैट्रिक्स^6 के माध्यम से मैट्रिक्स के लिए 0 हैं।
ह्यूरिस्टिक रूप से आप उपग्राफों को बाहर करने की कोशिश कर सकते हैं (उन लोगों के बड़े समूह जो अपेक्षाकृत छोटी संख्या में "पुल" नोड्स द्वारा अन्य क्लंप से जुड़े हुए हैं) लेकिन बिल्कुल कोई गारंटी नहीं है कि आपके पास कोई भी होगा।
आप मेमोरी में आकार 20x20 मिलियन के आसन्न मैट्रिक्स का निर्माण नहीं कर सकते हैं। इसके अलावा, गुणा ओ (एन^3) होगा, जहां एन 20 मिलियन है। –
यह स्ट्रैसेन के एल्गोरिदम के साथ लगभग n^2.8 है, क्योंकि वे वर्ग matrices हैं। आपको पूरे मैटिक्स को स्मृति में रखने की आवश्यकता नहीं है, केवल वे हिस्सों जिन्हें आप सक्रिय रूप से गुणा कर रहे हैं। बाकी डिस्क पर पृष्ठ। – patros
हालांकि बहुत सी डिस्क की आवश्यकता है ... एक निष्क्रिय दृष्टिकोण के लिए 400 टीबी। यद्यपि संपीड़न के लिए बहुत सारे कमरे। – patros
अच्छी तरह से एक बेहतर उत्तर दिया जा चुका है, लेकिन मेरे सिर के ऊपर से मैं Floyd-Warshall सभी जोड़े सबसे कम पथ एल्गोरिदम के साथ चला गया होगा, जो ओ (एन^3) है। मैं ग्राफ व्यास एल्गोरिदम की जटिलता से अनिश्चित हूं, लेकिन यह "लगता है" जैसे ओ (एन^3) भी होगा। अगर कोई जानता है तो मुझे इस पर स्पष्टीकरण चाहिए।
एक तरफ नोट पर, क्या आपके पास वास्तव में ऐसा डेटाबेस है? डरावना।
छः डिग्री औसत या औसत है? मैंने जो वास्तविक विश्लेषण पढ़ा है, वह अधिकतम औसत का उपयोग करता है। –
"छः डिग्री अलगाव" की सामान्य धारणा यह है कि यह अधिकतम है। बेशक, यह वास्तव में सच में सच नहीं है। यह कहने के लिए और अधिक प्रभावशाली है कि इस तरह से और counterexamples खोजने के लिए मुश्किल है। –