पेजरैंक और एचआईटीएस एल्गोरिदम

पेजरैंक (PageRank) और एचआईटीएस (HITS) लिंक-विश्लेषण एल्गोरिदम हैं जो केवल पृष्ठ सामग्री के बजाय हाइपरलिंक ग्राफ़ की संरचना से वेब पृष्ठों के महत्व या अधिकार का अनुमान लगाते हैं।

Definition

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

Scope

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

Core questions

• रैंडम-सर्फर मॉडल पेजरैंक को एक स्थिर वितरण के रूप में कैसे परिभाषित करता है?
• पेजरैंक को अच्छी तरह से परिभाषित होने के लिए डैम्पिंग या टेलीपोर्टेशन कारक की आवश्यकता क्यों है?
• एचआईटीएस में हब और अथॉरिटी स्कोर एक दूसरे को कैसे सुदृढ़ करते हैं?
• इन स्कोरों की पुनरावृत्ति (iteratively) कैसे गणना की जाती है, और वे कब अभिसरण करते हैं?
• क्वेरी-स्वतंत्र बनाम क्वेरी-निर्भर स्कोरिंग में पेजरैंक और एचआईटीएस कैसे भिन्न हैं?

Key concepts

• पेजरैंक
• रैंडम-सर्फर मॉडल
• डैम्पिंग फैक्टर और टेलीपोर्टेशन
• स्थिर वितरण / प्रमुख आइगेनवैल्यू
• एचआईटीएस
• हब और अथॉरिटी
• क्वेरी-स्वतंत्र बनाम क्वेरी-निर्भर स्कोरिंग
• पावर इटिरेशन और अभिसरण

Key theories

पेजरैंक रैंडम-सर्फर मॉडल

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

एचआईटीएस हब और अथॉरिटी

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

Clinical relevance

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

History

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

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

पेजरैंक और एचआईटीएस में क्या अंतर है?

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

पेजरैंक को डैम्पिंग फैक्टर की आवश्यकता क्यों है?

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