हम संभाव्य डेटा संरचनाओं का उपयोग करके बड़े ग्राफ़ के वितरित प्रसंस्करण में तेजी लाते हैं और न केवल

किसी भी सामाजिक नेटवर्क के सबसे मूल्यवान संसाधनों में से एक "दोस्ती का ग्राफ" है - इस कॉलम में कनेक्शन के माध्यम से जानकारी प्रसारित की जाती है, उपयोगकर्ताओं को दिलचस्प सामग्री भेजी जाती है, और रचनात्मक प्रतिक्रिया सामग्री लेखकों को भेजी जाती है। इसी समय, ग्राफ़ भी जानकारी का एक महत्वपूर्ण स्रोत है जो आपको उपयोगकर्ता को बेहतर ढंग से समझने और लगातार सेवा में सुधार करने की अनुमति देता है। हालांकि, उन मामलों में जब ग्राफ बढ़ता है, तो तकनीकी रूप से अधिक से अधिक मुश्किल होता है कि वह इससे जानकारी निकाल सके। इस लेख में हम OK.ru में बड़े रेखांकन को संसाधित करने के लिए उपयोग किए जाने वाले कुछ ट्रिक्स के बारे में बात करेंगे।

शुरू करने के लिए, वास्तविक दुनिया से एक सरल कार्य पर विचार करें: उपयोगकर्ता की आयु निर्धारित करें। उम्र को जानने से सामाजिक नेटवर्क को अधिक प्रासंगिक सामग्री का चयन करने और व्यक्ति को बेहतर अनुकूलन करने की अनुमति मिलती है। ऐसा लगता है कि सामाजिक नेटवर्क पर एक पेज बनाते समय पहले से ही संकेत दिया गया है, लेकिन वास्तव में, अक्सर, उपयोगकर्ता चालाक होते हैं और वास्तविक से अलग एक उम्र का संकेत देते हैं। एक सामाजिक ग्राफ स्थिति को सुधारने में मदद कर सकता है :)।

उदाहरण के लिए, बॉब (लेख के सभी पात्र काल्पनिक हैं, वास्तविकता के साथ कोई भी संयोग एक यादृच्छिक घर की रचनात्मकता का परिणाम है):

एक तरफ, बॉब के आधे दोस्त किशोर हैं, यह सुझाव देते हुए कि बॉब भी एक किशोर है। लेकिन उसके पुराने दोस्त भी हैं, इसलिए जवाब में आत्मविश्वास कम है। सामाजिक ग्राफ से अतिरिक्त जानकारी उत्तर को स्पष्ट करने में मदद कर सकती है:

इस बात को ध्यान में रखते हुए कि न केवल उन आर्कों में, जिनमें बॉब सीधे तौर पर शामिल है, बल्कि उनके दोस्तों के बीच भी आर्क हैं, हम देख सकते हैं कि बॉब किशोरों की एक घनी बिरादरी का हिस्सा है, जो हमें अधिक उम्र के विश्वास के साथ उनकी उम्र के बारे में एक निष्कर्ष निकालने की अनुमति देता है।

इस तरह की डेटा संरचना को एक अहंकार नेटवर्क या एक अहंकार उपसमूह के रूप में जाना जाता है; इसका उपयोग लंबे समय से किया गया है और सफलतापूर्वक कई समस्याओं को हल करने में उपयोग किया जाता है: समुदायों की खोज, बॉट्स और स्पैम की पहचान करना, दोस्तों और सामग्री की सिफारिश करना, आदि। हालांकि, सैकड़ों लाखों नोड्स और अरबों आर्क के सैकड़ों के साथ एक ग्राफ में सभी उपयोगकर्ताओं के लिए एक सबग्राफ के अहंकार की गणना "छोटी तकनीकी कठिनाइयों" की संख्या के साथ होती है :)।

मुख्य समस्या यह है कि जब ग्राफ में "दूसरे चरण" के बारे में जानकारी पर विचार किया जाता है, तो कनेक्शन की संख्या का एक द्विघात विस्फोट होता है। उदाहरण के लिए, 150 प्रत्यक्ष अहंकार लिंक वाले उपयोगकर्ता के लिए, एक सबग्राफ तक शामिल हो सकता है $$$150 + 150 * 149/2 = $ 11,32$ लिंक, और 5,000 दोस्तों के साथ एक सक्रिय उपयोगकर्ता के लिए, अहंकार सबग्राफ 12,000,000 से अधिक लिंक तक बढ़ सकता है।

एक अतिरिक्त जटिलता यह तथ्य है कि ग्राफ़ को वितरित वातावरण में संग्रहीत किया जाता है, और किसी भी नोड में मेमोरी में ग्राफ की पूरी छवि नहीं होती है। अकादमी और उद्योग दोनों में संतुलित ग्राफ़ विभाजन पर काम किया जाता है, लेकिन अहंकार सबग्राफ इकट्ठा करते समय भी सबसे शीर्ष परिणाम "सभी के साथ" संचार के लिए होते हैं: उपयोगकर्ता के दोस्तों के बारे में जानकारी प्राप्त करने के लिए, आपको सभी "विभाजनों" पर जाना होगा। ज्यादातर मामलों में।

इस मामले में काम करने वाले विकल्पों में से एक को डेटा दोहराव के लिए मजबूर किया जाएगा (उदाहरण के लिए, Google से एक लेख में एल्गोरिदम 3), लेकिन यह दोहराव भी मुक्त नहीं है। आइए जानने की कोशिश करते हैं कि इस प्रक्रिया में क्या सुधार किया जा सकता है।

Naive एल्गोरिथ्म

शुरू करने के लिए, अहंकार सबग्राफ बनाने के लिए "भोले" एल्गोरिथ्म पर विचार करें:

एल्गोरिथ्म मानता है कि मूल ग्राफ एक आसन्न सूची के रूप में संग्रहीत है, अर्थात्। उपयोगकर्ता के सभी दोस्तों के बारे में जानकारी कुंजी में उपयोगकर्ता आईडी और मूल्य में दोस्तों की सूची के साथ एकल रिकॉर्ड में संग्रहीत की जाती है। दूसरा कदम उठाने के लिए और उन दोस्तों के बारे में जानकारी प्राप्त करें जिनकी आपको आवश्यकता है:

1. एक ग्राफ को किनारों की सूची में परिवर्तित करें, जहां प्रत्येक किनारे एक अलग प्रविष्टि है।
2. किनारों की सूची को अपने आप से जोड़ दें, जो लंबाई 2 के ग्राफ में सभी पथ देगा।
3. पथ की शुरुआत करके समूह।

प्रत्येक उपयोगकर्ता के लिए आउटपुट पर, हमें प्रत्येक उपयोगकर्ता के लिए लंबाई 2 के रास्तों की सूची मिलती है। यहां यह ध्यान दिया जाना चाहिए कि परिणामी संरचना वास्तव में उपयोगकर्ता का दो-चरण वाला पड़ोस है , जबकि अहंकार सबग्राफ इसका सबसेट है। इसलिए, प्रक्रिया को पूरा करने के लिए, हमें उन सभी आर्कों को फ़िल्टर करना होगा जो तत्काल दोस्तों के बाहर जाते हैं।

यह एल्गोरिथ्म अच्छा है क्योंकि यह अपाचे स्पार्क के तहत स्काला पर दो लाइनों में लागू किया गया है। लेकिन लाभ वहाँ समाप्त होते हैं: औद्योगिक आकार के ग्राफ के लिए, नेटवर्क संचार की मात्रा सीमा से परे है और ऑपरेटिंग समय दिनों में मापा जाता है। मुख्य कठिनाई दो फेरबदल कार्यों द्वारा बनाई जाती है जो तब होती है जब हम जुड़ते हैं और समूह बनाते हैं। क्या भेजे गए डेटा की मात्रा को कम करना संभव है?

एक फेरबदल में एगो सबग्राफ

यह देखते हुए कि हमारी दोस्ती का ग्राफ सममित है, आप टॉमस शैंक द्वारा प्रस्तावित अनुकूलन का उपयोग कर सकते हैं:

1. आप बिना शामिल हुए लंबाई 2 के सभी रास्ते प्राप्त कर सकते हैं - यदि बॉब के मित्र एलिस और हैरी हैं, तो एलिस-बॉब-हैरी और हैरी-बॉब-एलिस पथ हैं।
2. समूहन करते समय, प्रवेश द्वार पर दो रास्ते एक ही नए किनारे के अनुरूप होते हैं। पथ बॉब-एलिस-डेव और बॉब-डेव-एलिस में बॉब के लिए एक ही जानकारी शामिल है, जिसका अर्थ है कि आप केवल हर दूसरे पथ को भेज सकते हैं, उपयोगकर्ताओं को उनकी आईडी द्वारा सॉर्ट कर सकते हैं।

अनुकूलन लागू करने के बाद, कार्य योजना इस तरह दिखाई देगी:

1. पीढ़ी के पहले चरण में, हमें ऑर्डर आईडी के एक फिल्टर के साथ लंबाई 2 के रास्तों की एक सूची मिलती है।
2. दूसरे पर, हम रास्ते में पहले उपयोगकर्ता द्वारा समूह बनाते हैं।

इस सेटिंग में, एल्गोरिथ्म एक फेरबदल ऑपरेशन को पूरा करता है, और नेटवर्क पर प्रसारित डेटा का आकार आधा हो जाता है। :)

स्मृति में अहंकार उपगुप्त बाहर रखना

एक महत्वपूर्ण मुद्दा जिसे हमने अभी तक नहीं माना है कि डेटा को स्मृति में एक सबग्राफ के अहंकार में कैसे विघटित किया जाए। ग्राफ को संपूर्ण रूप में संग्रहीत करने के लिए, हमने एक आसन्न सूची का उपयोग किया। यह संरचना उन कार्यों के लिए सुविधाजनक है जहां एक पूरे के रूप में समाप्त ग्राफ से गुजरना आवश्यक है, लेकिन यह महंगा है अगर हम टुकड़ों से एक ग्राफ बनाना चाहते हैं और अधिक सूक्ष्म विश्लेषण करना चाहते हैं। हमारे कार्य के लिए आदर्श संरचना को निम्नलिखित कार्यों को प्रभावी ढंग से करना चाहिए:

1. अलग-अलग विभाजनों से प्राप्त दो रेखांकन का मिलन।
2. सभी मानव मित्रों को प्राप्त करना।
3. यह जाँचना कि क्या दो लोग जुड़े हुए हैं।
4. ओवरहेड बॉक्सिंग के बिना मेमोरी में भंडारण।

इन आवश्यकताओं के लिए सबसे उपयुक्त स्वरूपों में से एक विरल CSR मैट्रिक्स का एनालॉग है:

इस मामले में ग्राफ तीन सरणियों के रूप में संग्रहीत है:

1. उपयोगकर्ता - ग्राफ़ में भाग लेने वाले सभी उपयोगकर्ताओं की आईडी के साथ एक क्रमबद्ध सरणी।
2. सूचकांक - उपयोगकर्ताओं के समान आकार का एक सरणी, जहां प्रत्येक उपयोगकर्ता के लिए तीसरे सरणी में उपयोगकर्ता संबंधों के बारे में जानकारी की शुरुआत के लिए एक सूचकांक-सूचक संग्रहीत किया जाता है।
3. दोस्तों - ग्राफ़ में किनारों की संख्या के बराबर आकार का एक सरणी, जहां संबंधित उपयोगकर्ताओं की आईडी क्रमिक रूप से उपयोगकर्ताओं से संबंधित आईडी के लिए दिखाई जाती है। किसी एकल उपयोगकर्ता के लिंक के बारे में जानकारी के भीतर प्रसंस्करण गति के लिए सरणी को क्रमबद्ध किया जाता है।

इस प्रारूप में, दो ग्राफ़ को मिलाने का कार्य रैखिक समय में किया जाता है, और किसी विशिष्ट उपयोगकर्ता पर जानकारी प्राप्त करने का संचालन या कोने की संख्या के प्रति लॉगरिदम के उपयोगकर्ताओं की एक जोड़ी पर। इस मामले में, मेमोरी में ओवरहेड ग्राफ़ के आकार पर निर्भर नहीं करता है, क्योंकि निश्चित संख्या में सरणियों का उपयोग किया जाता है। दोस्तों के आकार के बराबर चौथे डेटा सरणी को जोड़कर, आप ग्राफ़ में रिश्तों से जुड़ी अतिरिक्त जानकारी को सहेज सकते हैं।

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

फेरबदल कम करें

हालांकि, ऊपर उल्लिखित सभी अनुकूलन को लागू करने के बाद भी, सभी अहंकार सबग्राफ के निर्माण का कार्य अभी भी बहुत लंबा काम करता है। हमारे मामले में, क्लस्टर के उच्च उपयोग के साथ लगभग 6 घंटे। करीब से पता चलता है कि जटिलता का मुख्य स्रोत अभी भी फेरबदल ऑपरेशन है, जबकि फेरबदल में शामिल डेटा का एक महत्वपूर्ण हिस्सा निम्नलिखित चरणों में बाहर फेंक दिया जाता है। तथ्य यह है कि वर्णित दृष्टिकोण प्रत्येक उपयोगकर्ता के लिए एक पूर्ण दो-चरण पड़ोस बनाता है, जबकि अहंकार सबग्राफ केवल आंतरिक चाप वाले इस पड़ोस का एक अपेक्षाकृत छोटा उपसमूह है।

उदाहरण के लिए, अगर, बॉब के प्रत्यक्ष पड़ोसियों - हैरी और फ्रैंक को संसाधित करके - हमें पता था कि वे एक दूसरे के दोस्त नहीं हैं, तो पहले से ही पहले कदम पर हम ऐसे बाहरी रास्तों को फ़िल्टर कर सकते हैं। लेकिन सभी गैरी और फ्रेनकोव के लिए यह पता लगाने के लिए कि क्या वे दोस्त हैं, आपको दोस्ती के ग्राफ को सभी कंप्यूटिंग नोड्स में मेमोरी में खींचना होगा या प्रत्येक रिकॉर्ड को संसाधित करते समय रिमोट कॉल करना होगा, जो कि कार्य की शर्तों के अनुसार असंभव है।

फिर भी, एक समाधान है यदि हम अपने आप को अनुमति देते हैं, तो कुछ प्रतिशत मामलों में, गलती करने के लिए जब हम मित्रता पाते हैं जहां यह वास्तव में मौजूद नहीं है। संभावित डेटा संरचनाओं का एक पूरा परिवार है जो एक निश्चित मात्रा में त्रुटि की अनुमति देते हुए, परिमाण के आदेशों द्वारा डेटा भंडारण के दौरान मेमोरी की खपत को कम करना संभव बनाता है। इस तरह की सबसे प्रसिद्ध संरचना ब्लूम फ़िल्टर है , जो कई वर्षों से औद्योगिक डेटाबेस में "लंबी पूंछ" कैश में मिसाइलों की क्षतिपूर्ति के लिए सफलतापूर्वक उपयोग की जाती है।

ब्लूम फ़िल्टर का मुख्य कार्य प्रश्न का उत्तर देना है "क्या यह तत्व कई पहले देखे गए तत्वों में शामिल है?" इसके अलावा, यदि फ़िल्टर "नहीं" का उत्तर देता है, तो तत्व संभवतः सेट में शामिल नहीं है, लेकिन यदि यह "हां" का उत्तर देता है - तो एक छोटी संभावना है कि तत्व अभी भी नहीं है।

हमारे मामले में, "तत्व" उपयोगकर्ताओं की एक जोड़ी होगी, और "सेट" ग्राफ के सभी किनारों पर होगा। फिर फेरबदल के आकार को कम करने के लिए ब्लूम फ़िल्टर को सफलतापूर्वक लागू किया जा सकता है:

ग्राफ के बारे में जानकारी के साथ अग्रिम में ब्लूम फ़िल्टर तैयार करने के बाद, हम हैरी के दोस्तों के माध्यम से यह पता लगा सकते हैं कि बॉब और इलोना दोस्त नहीं हैं, जिसका अर्थ है कि हमें गैरी और इलोना के बीच के संबंध के बारे में बॉब की जानकारी भेजने की आवश्यकता नहीं है। हालांकि, हैरी और बॉब अपने आप में दोस्त हैं, यह जानकारी अभी भी भेजनी होगी, ताकि बॉब समूहन के बाद दोस्ती के अपने ग्राफ को पूरी तरह से बहाल कर सके।

फेरबदल निकालें

फ़िल्टर को लागू करने के बाद, भेजे गए डेटा की मात्रा लगभग 80% कम हो जाती है, और कार्य एक मध्यम क्लस्टर लोड के साथ 1 घंटे में पूरा होता है, जिससे आप समानांतर में अन्य कार्यों को स्वतंत्र रूप से कर सकते हैं। इस मोड में, इसे पहले से ही "ऑपरेशन में" लिया जा सकता है और दैनिक आधार पर रखा जा सकता है, लेकिन अभी भी अनुकूलन की संभावना है।

विरोधाभास के रूप में यह लग सकता है, समस्या को हल करने के लिए बिना हल किया जा सकता है, अगर आप अपने आप को त्रुटियों का एक निश्चित प्रतिशत की अनुमति देते हैं। और ब्लूम फ़िल्टर हमें इसमें मदद कर सकता है:

यदि फ़िल्टर का उपयोग करके बॉब की मित्र सूची को देखा जाए, तो हमें पता चलता है कि ऐलिस और चार्ली लगभग निश्चित रूप से दोस्त हैं, हम तुरंत बॉब के अहं उपसमूह में संबंधित चाप जोड़ सकते हैं। इस मामले में पूरी प्रक्रिया में 15 मिनट से कम समय लगेगा और नेटवर्क पर डेटा ट्रांसफर की आवश्यकता नहीं होगी, हालांकि, फ़िल्टर सेटिंग्स के आधार पर, आर्क का एक निश्चित प्रतिशत वास्तविकता में अनुपस्थित हो सकता है।

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

लेकिन कुछ कार्यों में, अतिरिक्त आर्क्स परिणाम की गुणवत्ता में एक घातक गिरावट का कारण बनते हैं: उदाहरण के लिए, जब एक दूरस्थ अहंकार (उपयोगकर्ता के शीर्ष के बिना) के साथ अहंकार सबग्राफ में जुड़े घटकों की खोज , घटकों के बीच "प्रेत पुल" की संभावना उनके आकार के सापेक्ष चतुराई से बढ़ती है, जो कि लगभग हर जगह हमें एक बड़ा घटक मिलता है।

एक मध्यवर्ती क्षेत्र है जहां अतिरिक्त आर्क्स के नकारात्मक प्रभाव का प्रयोगात्मक रूप से मूल्यांकन करने की आवश्यकता है: उदाहरण के लिए, कुछ समुदाय खोज एल्गोरिदम काफी कम शोर के साथ सफलतापूर्वक सामना कर सकते हैं, लगभग समान सामुदायिक संरचना को लौटाते हैं।

एक निष्कर्ष के बजाय

अहंकार उपयोगकर्ता सबग्राफ सूचनाओं का एक महत्वपूर्ण स्रोत है जो अनुशंसाओं की गुणवत्ता में सुधार, जनसांख्यिकी को परिष्कृत करने और स्पैम से निपटने के लिए ओके में सक्रिय रूप से उपयोग किया जाता है, लेकिन उनकी गणना कई कठिनाइयों के साथ होती है।

लेख में, हमने एक सामाजिक नेटवर्क के सभी उपयोगकर्ताओं के लिए अहंकार सबग्राफ के निर्माण के कार्य के दृष्टिकोण के विकास की जांच की और शुरुआती 20 घंटे से 1 घंटे तक काम के समय में सुधार करने में सक्षम थे, और त्रुटियों के एक छोटे प्रतिशत के मामले में, 10-15 मिनट तक।

तीन "स्तंभ" जिस पर अंतिम निर्णय आधारित है:

1. ग्राफ समरूपता संपत्ति और टॉमस शंख एल्गोरिदम का उपयोग करना।
2. एक विरल CSR मैट्रिक्स का उपयोग करके अहंकार सबग्राफ को कुशलतापूर्वक स्टोर करें।
3. नेटवर्क पर डेटा स्थानांतरण को कम करने के लिए ब्लूम फ़िल्टर का उपयोग करें।

एल्गोरिथ्म कोड कैसे विकसित हुआ है, इसके उदाहरण ज़ेपेलिन नोटबुक में पाए जा सकते हैं।