बड़े नेटवर्क में समुदायों की पहचान करने के लिए एल्गोरिदम

हाल ही में, लाखों नोड्स से सामाजिक नेटवर्क में समुदायों की पहचान करने के लिए एक प्रभावी एल्गोरिदम विकसित करने के लिए कई प्रयास किए गए हैं जिन्हें व्यक्तिगत नोड्स के स्तर पर कल्पना या विश्लेषण नहीं किया जा सकता है।



बेल्जियम के डेवलपर्स ने एक नया एल्गोरिदम पेश किया है जो कम्प्यूटेशनल गति में सभी मौजूदा समकक्षों को पार करता है। नतीजतन, इसका उपयोग अभूतपूर्व आकार के ठिकानों पर किया जा सकता है: 2 मिलियन नोड्स के एक विशिष्ट नेटवर्क के विश्लेषण में 2 मिनट लगते हैं। इसे लौवेन विधि कहा जाता है, क्योंकि यह उस समय बनाया गया था जब सभी डेवलपर्स लौवेन (बेल्जियम) में काम करते थे।



लुवेन्स्की विधि ने एक ज्ञात सामुदायिक संरचना के साथ नेटवर्क पर परीक्षण करते समय अपनी सटीकता साबित की, जहां परिणाम को सत्यापित किया जा सकता है। इसकी पदानुक्रमित संरचना के कारण, यह विभिन्न पैमानों पर समुदायों के विश्लेषण के लिए उपयुक्त है। विशेष रूप से, यह बेल्जियम मोबाइल ऑपरेटर (2.6 मिलियन ग्राहकों) के नेटवर्क पर और क्रॉलर स्टैनफोर्ड वेबबेस (118 मिलियन नोड्स और 1 बिलियन से अधिक लिंक) द्वारा एकत्र किए गए वेब पृष्ठों के आधार पर समुदायों के लिए भी परीक्षण किया गया था।





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



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







इस प्रकार, प्रत्येक चरण के बाद, कार्यक्रम बड़े पैमाने के समुदायों को प्रदर्शित करता है।



अधिक जानकारी के लिए बड़े नेटवर्क में समुदायों का तेजी से खुलासा देखें। उदाहरण के लिए, इसमें एल्गोरिदम क्लॉज़ेट / न्यूमैन / मूर, पॉन्स / लैटी थेरेपी और वेकिता / त्सुरुमी की तुलना में एल्गोरिथ्म की गुणवत्ता और गति की एक तालिका है। प्रत्येक कार्य के लिए, 24 जीबी रैम (डैश, यदि समय 24 घंटे से अधिक है) के साथ ओपेरटन 2.2 गीगाहर्ट्ज मशीन पर मापांक और रनटाइम का स्तर इंगित किया गया है। परिणामों को देखते हुए, लौवेन पद्धति का शाब्दिक अर्थ नहीं के बराबर है।







C ++ और matlab में कार्यक्रम मुफ्त है।