इंटरनेट का नक्शा

सभी को नमस्कार!

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



उदाहरण के लिए, यदि आप खोज में habrahabr.ru दर्ज करते हैं, तो आप देख सकते हैं कि गंदे.ru और leprosorium.ru एक ही "नक्षत्र" में हैं, और livejournal.ru भी बहुत दूर है। इससे पता चलता है कि जो व्यक्ति इस पाठ को पढ़ रहा है, उसे इन साइटों पर जाने की भी संभावना है (औसत रनर उपयोगकर्ता के बारे में)।

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

जो लोग एक संक्षिप्त तकनीकी विवरण में रुचि रखते हैं - कटौती करने के लिए आपका स्वागत है

इंजीनियरिंग भाग

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



प्रारंभिक डेटा एलेक्सा से लिया गया था, वे उपयोगकर्ताओं की उपस्थिति, अपस्ट्रीम और डाउनस्ट्रीम संक्रमणों के रिकॉर्ड हैं (अपस्ट्रीम - जहां वे आए थे, डाउनस्ट्रीम - जहां वे गए थे)। सामान्य होने के बाद, हमें 350 हजार चक्कर और 2 मिलियन से अधिक किनारों के साथ एक भारित अप्रत्यक्ष ग्राफ मिलता है।

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

इसे सीधे शब्दों में कहें, एल्गोरिथ्म उन पर कार्य करने वाली ताकतों के अनुसार नक्शे पर साइटों के चरण-दर-चरण आंदोलन में काम करता है। कई उपयोगकर्ता संक्रमण - एक मजबूत बल साइटों को एक साथ करीब लाने की कोशिश करता है; यदि साइटें बहुत पास हैं, तो प्रतिकारक बल काम करना शुरू कर देता है, आदि। इस कार्य रिपोर्ट में अधिक विवरण पाए जा सकते हैं-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf

मुख्य समस्या इस तरह के एक एल्गोरिथ्म की विशाल कम्प्यूटेशनल जटिलता थी। दरअसल, समस्या को "हेड-ऑन" हल करते समय, प्रत्येक चरण में प्रत्येक साइट के लिए बलों के सुपरपोजिशन की गणना करना आवश्यक है, अर्थात। साइटों की प्रत्येक जोड़ी के लिए ताकत की गणना करें, और लगभग 122 बिलियन ऐसे जोड़े हैं (एक कदम के लिए बुरा नहीं है, सही?)। इसलिए, एल्गोरिथ्म का कठोर अनुकूलन और गणनाओं का पूर्ण समानांतरकरण किया गया था। सौभाग्य से, .नेट मंच इस तरह के मज़े के लिए आश्चर्यजनक रूप से अच्छा निकला।

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

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

अंतिम चरण होस्टिंग और रिलीज़ का विकल्प है। यहाँ भी, रोमांच के बिना नहीं था। अब सब कुछ अमेज़ॅन क्लाउड में घूम रहा है और यह जितना मैंने सोचा था उससे कहीं अधिक सरल और सस्ता निकला।

सामान्य तौर पर, मुझे कुछ अनुभव प्राप्त हुआ है, और मुझे एक सम्मानित समुदाय के साथ इसे साझा करने में खुशी होगी। बेशक, सामान्य तौर पर, कुछ खास नहीं है, वास्तव में दिलचस्प परियोजनाएं और हब्रे पर गैर-तुच्छ समाधान हैं, लेकिन फिर भी, मुझे लगता है, कई लोग इसमें रुचि ले सकते हैं।

मैं किसी भी विचार, प्रतिक्रिया, आलोचना - किसी भी प्रतिक्रिया से खुश रहूंगा!

अपनी तरह के शब्दों के लिए आप सभी का धन्यवाद! मेरे लिए पेशेवर समुदाय से समर्थन प्राप्त करना बहुत महत्वपूर्ण था, उन लोगों से, जो न केवल परिणाम देखते हैं, बल्कि यह समझते हैं कि इसे प्राप्त करने के लिए कितना काम किया गया है। इसके अलावा हेब्र के लिए धन्यवाद कि RuNet में हम सभी को एकजुट करने वाला एक मंच है!

निरंतरता: वेब आर्किटेक्चर इंटरनेट मैप्स