SimRank
सिमरैंक एक सामान्य समानता माप है, जो एक सरल और सहज ज्ञान युक्त ग्राफ-सैद्धांतिक मॉडल पर आधारित है। सिमरैंक ऑब्जेक्ट-टू-ऑब्जेक्ट संबंधों के साथ किसी भी क्षेत्र में लागू होता है, जो अन्य वस्तुओं के साथ उनके संबंधों के आधार पर संरचनात्मक संदर्भ की समानता को मापता है। प्रभावी रूप से, सिमरैंक एक माप है जो कहता है कि "दो वस्तुओं को समान माना जाता है यदि वे समान वस्तुओं द्वारा संदर्भित हैं"। हालाँकि सिमरैंक को व्यापक रूप से अपनाया जाता है, यह अनुचित समानता स्कोर का उत्पादन कर सकता है जो विभिन्न कारकों से प्रभावित होते हैं, और इसे कई तरीकों से हल किया जा सकता है, जैसे कि एक साक्ष्य वजन कारक पेश करना, अतिरिक्त शब्द सम्मिलित करना जो सिमरैंक द्वारा उपेक्षित हैं या पेजरैंक-आधारित विकल्पों का उपयोग करना। परिचय कई अनुप्रयोगों के लिए वस्तुओं के बीच "समानता" के माप की आवश्यकता होती है। एक स्पष्ट उदाहरण पारंपरिक टेक्स्ट कॉर्पोरा या वर्ल्ड वाइड वेब पर "फाइंड-सिमिलर-दस्तावेज़" प्रश्न है। अधिक आम तौर पर, एक समानता माप का उपयोग वस्तुओं को क्लस्टर करने के लिए किया जा सकता है, जैसे कि एक अनुशंसा प्रणाली में सहयोगी फ़िल्टरिंग के लिए, जिसमें "समान" उपयोगकर्ताओं और वस्तुओं को उपयोगकर्ताओं की प्राथमिकताओं के आधार पर समूहीकृत किया जाता है। वस्तुओं के विभिन्न पहलुओं का उपयोग समानता निर्धारित करने के लिए किया जा सकता है, जो आमतौर पर डोमेन और उस डोमेन के लिए समानता की उचित परिभाषा पर निर्भर करता है। दस्तावेज़ कोष में, मेल खाने वाले पाठ का उपयोग किया जा सकता है, और सहयोगी फ़िल्टरिंग के लिए, समान उपयोगकर्ताओं को सामान्य प्राथमिकताओं द्वारा पहचाना जा सकता है। सिमरैंक एक सामान्य दृष्टिकोण है जो रुचि के कई क्षेत्रों में पाए जाने वाले वस्तु-से-वस्तु संबंधों का फायदा उठाता है। उदाहरण के लिए, वेब पर, दो पृष्ठ संबंधित हैं यदि उनके बीच हाइपरलिंक हैं। इसी तरह का दृष्टिकोण वैज्ञानिक पत्रों और उनके उद्धरणों, या क्रॉस-संदर्भ जानकारी वाले किसी अन्य दस्तावेज़ कोष पर लागू किया जा सकता है। अनुशंसा प्रणाली के मामले में, किसी वस्तु के लिए उपयोगकर्ता की पसंद उपयोगकर्ता और वस्तु के बीच संबंध का गठन करती है। इस तरह के डोमेन को स्वाभाविक रूप से ग्राफ के रूप में मॉडल किया जाता है, जिसमें वस्तुओं का प्रतिनिधित्व करने वाले नोड्स और संबंधों का प्रतिनिधित्व करने वाले किनारे होते हैं। सिमरैंक एल्गोरिथम के पीछे अंतर्ज्ञान यह है कि, कई क्षेत्रों में, समान वस्तुओं को समान वस्तुओं द्वारा संदर्भित किया जाता है। अधिक सटीक रूप से, वस्तुओं और उन्हें समान माना जाता है यदि वे वस्तुओं से क्रमशः इंगित होते हैं और स्वयं समान होते हैं। आधार मामला यह है कि वस्तुएं अधिकतम रूप से अपने समान होती हैं। यह ध्यान रखना महत्वपूर्ण है कि सिमरैंक एक सामान्य एल्गोरिथ्म है जो केवल संरचनात्मक संदर्भ की समानता को निर्धारित करता है। सिमरैंक किसी भी क्षेत्र पर लागू होता है जहां संबंधों पर समानता की कम से कम कुछ धारणा को आधार बनाने के लिए वस्तुओं के बीच पर्याप्त प्रासंगिक संबंध हैं। जाहिर है, अन्य क्षेत्र-विशिष्ट पहलुओं की समानता भी महत्वपूर्ण है; इन्हें समग्र समानता माप के लिए संबंधपरक संरचनात्मक-संदर्भ समानता के साथ जोड़ा जा सकता है। उदाहरण के लिए, वेब पृष्ठों के लिए सिमरैंक को पारंपरिक पाठ्य समानता के साथ जोड़ा जा सकता है; यही विचार वैज्ञानिक पत्रों या अन्य दस्तावेज़ निगम पर लागू होता है। अनुशंसा प्रणालियों के लिए, वस्तुओं के बीच अंतर्निहित ज्ञात समानताएं हो सकती हैं (जैसे, दोनों कंप्यूटर, दोनों कपड़े, आदि)। ), साथ ही उपयोगकर्ताओं के बीच समानताएं (जैसे, समान लिंग, समान खर्च स्तर)। फिर से, इन समानताओं को समानता के अंकों के साथ जोड़ा जा सकता है जिनकी गणना वरीयता पैटर्न के आधार पर की जाती है, ताकि समग्र समानता माप का उत्पादन किया जा सके। मूल सिमरैंक समीकरण एक निर्देशित ग्राफ में एक नोड के लिए, हम क्रमशः इन-नेबर्स और आउट-नेबर्स के सेट को दर्शाते हैं। अलग-अलग पड़ोसियों को के रूप में, के लिए, और अलग-अलग बाहरी पड़ोसियों को के रूप में दर्शाया जाता है। आइए हम वस्तुओं और द्वारा के बीच समानता को दर्शाते हैं। पहले की प्रेरणा के बाद, एक पुनरावर्ती समीकरण के लिए लिखा जाता है। यदि तब परिभाषित किया जाता है। अन्यथा, और के बीच एक स्थिरांक कहाँ है। यहाँ एक छोटी सी तकनीकीता यह है कि या तो कोई पड़ोसी हो सकता है या नहीं भी। चूँकि और के बीच किसी भी समानता का अनुमान लगाने का कोई तरीका नहीं है और इस मामले में, समानता निर्धारित की गई है, इसलिए उपरोक्त समीकरण में योग को कब या के रूप में परिभाषित किया गया है। सिमरैंक का मैट्रिक्स प्रतिनिधित्व और के बीच एक मनमाना स्थिरांक दिए जाने पर, मान लीजिए समानता मैट्रिक्स हो जिसकी प्रविष्टि समानता स्कोर को दर्शाती है, और कॉलम सामान्यीकृत निकटता मैट्रिक्स हो जिसकी प्रविष्टि यदि से कोई किनारा है, और अन्यथा 0 है। फिर, मैट्रिक्स संकेतनों में, सिमरैंक को एक पहचान मैट्रिक्स के रूप में तैयार किया जा सकता है। सिम रैंक की गणना एक ग्राफ के लिए सिम रैंक समीकरणों का एक समाधान एक निश्चित बिंदु पर पुनरावृत्ति द्वारा प्राप्त किया जा सकता है। मान लीजिए कि इसमें नोड्स की संख्या है। प्रत्येक पुनरावृत्ति के लिए, हम प्रविष्टियाँ रख सकते हैं, जहाँ पुनरावृत्ति के बीच और उस पर अंक दिया जाता है। हम क्रमिक रूप से इसके आधार पर गणना करते हैं। हम शुरू करते हैं जहाँ प्रत्येक वास्तविक सिमरैंक स्कोर पर एक निचली सीमा हैः से गणना करने के लिए, हम मूल सिमरैंक समीकरण का उपयोग प्राप्त करने के लिए करते हैंः के लिए, और के लिए। अर्थात्, प्रत्येक पुनरावृत्ति पर, हम मूल सिमरैंक समीकरण के अनुसार पिछली पुनरावृत्ति से पड़ोसियों के समानता स्कोर का उपयोग करने की समानता को अद्यतन करते हैं। जैसे-जैसे मूल्य बढ़ रहे हैं वैसे-वैसे कम नहीं हो रहे हैं। यह दिखाया गया था कि मान मूल सिमरैंक समीकरण, सिमरैंक स्कोर, यानी सभी के लिए, को संतुष्ट करने वाली सीमाओं में अभिसरण करते हैं। मूल सिमरैंक प्रस्ताव ने प्रदर्शन करने के लिए क्षय कारक और एक निश्चित संख्या में पुनरावृत्तियों को चुनने का सुझाव दिया। हालांकि, हाल के शोध से पता चला है कि दिए गए मान और आम तौर पर पुनरावृत्त रूप से गणना किए गए सिमरैंक स्कोर की अपेक्षाकृत कम सटीकता का संकेत देते हैं। अधिक सटीक गणना परिणामों की गारंटी के लिए, बाद वाला पेपर या तो एक छोटे क्षय कारक (विशेष रूप से) का उपयोग करने या अधिक पुनरावृत्ति लेने का सुझाव देता है। CoSimRank CoSimRank सिम रैंक का एक प्रकार है जिसमें एक स्थानीय सूत्रीकरण होने का भी लाभ है, अर्थात। एकल नोड जोड़ी के लिए कोसिम रैंक की गणना की जा सकती है। माना समानता मैट्रिक्स जिसकी प्रविष्टि समानता स्कोर को दर्शाती है, और कॉलम सामान्यीकृत निकटता मैट्रिक्स हो। फिर, मैट्रिक्स संकेतनों में, CoSimRank को इस प्रकार तैयार किया जा सकता हैः जहां एक पहचान मैट्रिक्स है। केवल एक एकल नोड जोड़ी के समानता स्कोर की गणना करने के लिए, मान लीजिए, मानक आधार का वेक्टर होने के साथ, यानी-th प्रविष्टि 1 है और अन्य सभी प्रविष्टियाँ 0 हैं। फिर, कोसिमरैंक की गणना दो चरणों में की जा सकती हैः पहले चरण में व्यक्तिगत पेजरैंक का एक सरलीकृत संस्करण देखा जा सकता है। दूसरा चरण प्रत्येक पुनरावृत्ति की सदिश समानता का सारांश देता है। मैट्रिक्स और स्थानीय प्रतिनिधित्व दोनों, समान समानता अंक की गणना करते हैं। CoSimRank का उपयोग संशोधित करके नोड्स के सेट की समानता की गणना करने के लिए भी किया जा सकता है। सिमरैंक फोगारस और रेज़ पर आगे के शोध ने मोंटे कार्लो विधि का उपयोग करके संभावित गणना के माध्यम से सिमरैंक गणना को तेज करने का सुझाव दिया। एंटोनेलिस एट अल। विस्तारित सिमरैंक समीकरण (i) आपतित नोड्स के लिए साक्ष्य कारक और (ii) लिंक भार को ध्यान में रखते हुए। यू एट अल। विभिन्न आंशिक राशियों के बीच छोटे सामान्य भागों को साझा करने के लिए एक महीन-दाने वाले ज्ञापन विधि के माध्यम से सिमरैंक गणना में और सुधार किया गया। चेन और जाइल्स ने सिमरैंक की सीमाओं और उचित उपयोग के मामलों पर चर्चा की। आंशिक सारांश संस्मरण लिजोरकिन और अन्य। सिमरैंक की गणना को तेज करने के लिए प्रस्तावित तीन अनुकूलन तकनीकेंः आवश्यक नोड्स का चयन ए-प्रायोरी शून्य स्कोर वाले नोड जोड़े के एक अंश की गणना को समाप्त कर सकता है। आंशिक राशि ज्ञापन बाद में पुनः उपयोग के लिए समानता योग के हिस्से को कैशिंग करके विभिन्न नोड जोड़े के बीच समानता की बार-बार की गई गणना को प्रभावी ढंग से कम कर सकता है। समानता पर एक सीमा सेटिंग गणना किए जाने वाले नोड जोड़े की संख्या में और कमी लाने में सक्षम बनाती है। विशेष रूप से, आंशिक राशि ज्ञापन का दूसरा अवलोकन सिमरैंक की गणना को बहुत तेज करने में एक सर्वोपरि भूमिका निभाता है, जहां पुनरावृत्तियों की संख्या है, एक ग्राफ की औसत डिग्री है, और एक ग्राफ में नोड्स की संख्या है। आंशिक राशि संरूपण के केंद्रीय विचार में दो चरण होते हैंः पहले, आंशिक राशि को संरूपण के रूप में किया जाता है और फिर पुनरावृत्त रूप से इसकी गणना की जाती है। पेज रैंक उद्धरण स्रोत समूह विश्लेषण एल्गोरिदम समानता उपाय भी देखें।