छह हैंडशेक का सिद्धांत: एक और पुष्टि

ठंड के मौसम में एक बार, मैं एक उल्लेख में आया था कि फेसबुक पर कोई व्यक्ति छह हैंडशेक के सिद्धांत की पुष्टि करने की कोशिश कर रहा था। जो लोग नहीं जानते हैं, उनके लिए यह सिद्धांत है कि पृथ्वी के सभी निवासी औसतन पांच दोस्तों (यानी छह हैंडशेक) की एक श्रृंखला के माध्यम से एक-दूसरे से परिचित हैं। आप इस सिद्धांत के इतिहास के बारे में विकिपीडिया पर अधिक पढ़ सकते हैं, जहाँ आप यह भी जान सकते हैं कि Microsoft ने कई वर्ष पहले एमएस मैसेंजर की संपर्क सूचियों के आंकड़ों के आधार पर इस सिद्धांत की पुष्टि करने की कोशिश की थी - परिणामस्वरूप, उन्हें 6.6 हैंडशेक मिले, जो उनके साथ अच्छे थे सिद्धांत।

मैं वास्तव में इस सिद्धांत की पुष्टि स्वयं करना चाहता था, जो कि हाथ में डेटा का उपयोग कर रहा है - VKontakte। मेरे अजीब विचार को जीवन में अनुवाद करने के लिए, समस्याओं की एक पूरी श्रृंखला को हल करना आवश्यक था:

1. भरोसा करने के लिए यह कौन सा डेटा है।
2. यह डेटा कहां से मिलेगा।
3. इस डेटा को कैसे बचाया जाए।
4. गणना के लिए क्या एल्गोरिदम का उपयोग करें।

आधुनिक जीवन में सामाजिक नेटवर्क के प्रभुत्व के साथ, सामाजिक कनेक्शन पर डेटा प्राप्त करने का सवाल इतना मुश्किल नहीं है। बेशक, फेसबुक से दोस्तों के बारे में डेटा लेना अच्छा होगा, क्योंकि यह पूरी दुनिया को कवर करता है, और वहां बहुत सारे लोग हैं। लेकिन मैं सार्वजनिक API के माध्यम से किसी भी व्यक्ति के लिए एक मित्र सूची नहीं बना सकता हूं, और एक पृष्ठ को पार्स करना सबसे प्रभावी विकल्प नहीं है, क्योंकि फेसबुक dhtml के रूप में एक मित्र सूची को बाहर निकालता है, प्रति मित्र 1kb डेटा, कुल 400 मिलियन लोग * औसतन * 130 मित्र * 130 मित्र। = 52 टीबी यातायात। ट्रैफ़िक की इतनी कम मात्रा शून्य करने के लिए शोध बजट में फिट नहीं थी, और फेसबुक विकल्प वापस फेंक दिया गया था।

वीके पर मेरी निगाह टिकी हुई थी। हां, यह केवल रूस और सीआईएस को कवर करता है (और असमान रूप से - सहपाठियों में, उदाहरण के लिए, एक पुराने दर्शक)। हां, बड़ी संख्या में बॉट हैं। VKontakte सही नहीं है, लेकिन यह al_friends.php के लिए अनुरोध के माध्यम से json प्रारूप में दोस्तों की सूची वितरित कर सकता है।

लेकिन इस डेटा को कैसे स्टोर और प्रोसेस करना है?

1. आप हेड-ऑन कर सकते हैं और सीधे MySQL पर लिख सकते हैं: एक मकड़ी प्रति सेकंड 100 उपयोगकर्ताओं को थूकती है, प्रत्येक के 130 दोस्त हैं, कुल 13,000 डेटाबेस आवेषण प्रति सेकंड है। आंकड़ा निषेधात्मक नहीं है, लेकिन इस तथ्य को देखते हुए कि मकड़ी एक कमजोर सर्वर (पुराने सिंगल-कोर एटलॉन) पर काम कर रही थी, यह पूरी तरह से गुलाबी नहीं है।
2. आप डिस्क पर एक पाठ डंप लिख सकते हैं, और फिर इसे डेटाबेस में चूस सकते हैं। इस स्थिति में, आधार का वजन लगभग (4 बाइट्स (user_id फ़ील्ड का आकार) + 4 बाइट्स (friend_id फ़ील्ड का आकार) + 8 बाइट्स ओवरहेड और इंडेक्स के लिए होगा) * VKontakte के 80M उपयोगकर्ता / 130 मित्र = 166GB। यह बहुत ज्यादा होगा। इसके अलावा, सभी उपयोगकर्ता के दोस्तों के ऐसे डेटाबेस से चयन एक सुपर-कुशल क्वेरी की तरह नहीं दिखेगा।
3. आप MySQL में हथौड़ा मार सकते हैं और कुछ हैश-मूल्य भंडारण का उपयोग कर सकते हैं। इसमें "user_id array (friend_id friend_id ...)" की एक जोड़ी लिखने के लिए, आधार को ऐसे मैक्रो के साथ चार बार उड़ाया जाएगा और सभी दोस्तों को डिस्क पर एक एक्सेस के साथ चुना जाएगा। क्योटो मंत्रिमंडल को मूल रूप से भंडारण के रूप में चुना गया था, लेकिन एक बड़े आधार पर कुछ अजीब प्रदर्शन विसंगतियों के कारण, हम Google LevelDB में चले गए।

तीन दिनों और एक आधा टेराबाइट्स के बाद, एक मित्र डेटाबेस प्राप्त हुआ (वैसे, केवल 22 जीबी)। और यहां सबसे दिलचस्प सवाल उठता है: उपयोगकर्ताओं के बीच की दूरी की गणना कैसे करें?

1. फ़्लॉइड-वारशॉल एल्गोरिथ्म हमें सभी उपयोगकर्ताओं से सभी की दूरी की गणना करने की अनुमति देगा। एक अद्भुत एल्गोरिथ्म, लेकिन इसकी एक अप्रिय स्मृति आवश्यकता है - यह वर्ग मैट्रिक्स user_id / user_id को संग्रहीत करने के लिए आवश्यक है, जो 1 बाइट * 80M उपयोगकर्ता * 80M उपयोगकर्ता = 6400 Tb पर कब्जा करेगा। बहुत ज्यादा।
2. डीजकस्ट्रा के एल्गोरिथ्म में एक बार में एक उपयोगकर्ता से अन्य सभी के लिए दूरी खोजने की अनुमति होगी। इसके काफी प्रभावी कार्यान्वयन हैं, जिनमें से एक का उपयोग प्रयोग के लिए किया गया था। एल्गोरिदम ने पूरे बेस के 1% सिंथेटिक नमूने पर आश्चर्यजनक रूप से काम किया, लेकिन 10% की औसत से शुरू होने पर, बेस का नमूना एक अप्रत्याशित स्थान पर गंभीर रूप से ब्रेक करना शुरू कर दिया - दोस्तों के एक बड़े पेड़ को दरकिनार करते हुए लगातार स्मृति के यादृच्छिक स्थानों में चढ़ गए और पहले से ही कमजोर प्रोसेसर के लगभग 100% CACHE_MISS को पकड़ लिया। । मानवीय शब्दों में, डेटा प्रोसेसर कैश में फिट नहीं हुआ, और करामाती ब्रेक शुरू हुआ।
3. अप्रत्यक्ष खोज । हां, दुनिया में सबसे सुरुचिपूर्ण एल्गोरिदम नहीं है, लेकिन गुणा तालिका के रूप में सरल है। आपको दो उपयोगकर्ताओं के बीच कम से कम दूरी खोजने की अनुमति देता है। इसके कार्यान्वयन को बिट फ़ील्ड्स का उपयोग करते हुए लिखा गया था, जो कि प्रोसेसर कैश में सुरुचिपूर्ण ढंग से चमकते थे, परिणामस्वरूप, एल्गोरिथ्म ने आधे मिनट में दो लोगों के बीच की दूरी कहीं और पाई।

संसाधन-गहन कार्यों को हल करते समय, मैं ऐसे कार्यान्वयन करना पसंद करता हूं जो मेरे मामूली नेटबुक पर भी ठीक काम करेंगे, और फिर भारी तोपखाने शामिल होंगे। भारी तोपखाने के रूप में, दो छह-कोर X5650 xeon और 32GB मेमोरी वाले एक मामूली सर्वर का उपयोग किया गया था। उस पर, दूरी पहले से ही प्रति सेकंड 10 सेकंड में माना जाता था। समानांतर में खाते में, 144 उपयोगकर्ता जोड़े के बीच की दूरी की गणना प्रति मिनट की गई।

फिर आंकड़ों के साथ विचित्रता शुरू हुई। गैर-शून्य संख्या वाले सभी उपयोगकर्ताओं में से लगभग 50% उपयोगकर्ता पूरी तरह से स्वतंत्र समूहों से संबंधित थे, जिसमें कोई बाहरी लिंक नहीं हैं (या ऐसे लिंक, पूरे क्लस्टर के लिए डेढ़ टुकड़े)। मोटे तौर पर, 50 लोगों ने एक-दूसरे को फंसाया और किसी ने नहीं। बहुत अजीब व्यवहार, है ना? हां, शायद यह संप्रदायों और धर्म ने उन्हें संप्रदाय के गैर-सदस्य VKontakte मित्र को मना किया है। लेकिन शायद ही, सबसे अधिक संभावना ये बॉट हैं।

एक समान अप्रत्याशित तरीके से पकड़े गए बॉट्स को फेंकने पर, 6773 उपयोगकर्ता जोड़े का विश्लेषण किया गया और एक बहुत ही रोचक परिणाम प्राप्त किया गया:

एक्स अक्ष के साथ हिस्टोग्राम पर दोस्तों की सबसे छोटी श्रृंखला की लंबाई है, और वाई अक्ष के साथ इसे प्रतिशत में खोजने की संभावना है।

इस प्रकार, दो यादृच्छिक VKontakte उपयोगकर्ताओं के बीच औसतन 5.65 दोस्त (यानी 6.65 हैंडशेक) हैं। यह आंकड़ा शुरू में परीक्षण किए गए सिद्धांत के साथ अच्छी तरह से फिट बैठता है, इसके अलावा, यह बिल्कुल माइक्रोसॉफ्ट में प्राप्त परिणाम से मेल खाता है (उन्हें 6.6 मिला)। इसलिए परिणाम को छह हैंडशेक के सिद्धांत की एक और पुष्टि माना जा सकता है।