خوارزميات PageRank و HITS
خوارزميتا PageRank و HITS هما خوارزميات تحليل الروابط التي تقدر أهمية أو سلطة صفحات الويب من بنية الرسم البياني للروابط التشعبية بدلاً من محتوى الصفحة وحده.
Definition
تُسند PageRank لكل صفحة درجة أهمية مستقلة عن الاستعلام تساوي احتمالها الثابت في ظل متصفح عشوائي يتبع الروابط الصادرة باحتمالية تخميد وينتقل آنياً بخلاف ذلك، بينما تحسب HITS، لمخطط فرعي يعتمد على الاستعلام، درجات سلطة للصفحات ذات المحتوى القيم ودرجات محور للصفحات التي ترتبط بسلطات جيدة، حيث يعزز كل منهما الآخر.
Scope
يغطي هذا الموضوع خوارزميتي تحليل الروابط الأساسيتين: PageRank، وهو مقياس لأهمية الصفحة مستقل عن الاستعلام ويعتمد على نموذج المتصفح العشوائي مع الانتقال الآني، و HITS، وهو مخطط يعتمد على الاستعلام ويحسب درجات المحور والسلطة التي تعزز بعضها البعض. ويتناول الموضوع الصياغات الأساسية للمشي العشوائي والمتجهات الذاتية، ودور التخميد والانتقال الآني، والتقارب، والمتغيرات الحساسة للموضوع. ويستبعد كيفية دمج هذه الدرجات مع الميزات النصية في ترتيب نهائي، والذي ينتمي إلى ترتيب البحث على الويب.
Core questions
- كيف يحدد نموذج المتصفح العشوائي PageRank كتوزيع ثابت؟
- لماذا يلزم عامل تخميد أو انتقال آني لكي يكون PageRank معرفاً جيداً؟
- كيف تعزز درجات المحور والسلطة في HITS بعضها البعض؟
- كيف تُحسب هذه الدرجات تكرارياً، ومتى تتقارب؟
- كيف يختلف PageRank و HITS في كونهما مستقلين عن الاستعلام مقابل اعتمادهما على الاستعلام؟
Key concepts
- PageRank
- نموذج المتصفح العشوائي
- عامل التخميد والانتقال الآني
- التوزيع الثابت / المتجه الذاتي الرئيسي
- HITS
- المحاور والسلطات
- التسجيل المستقل عن الاستعلام مقابل التسجيل المعتمد على الاستعلام
- تكرار القوة والتقارب
Key theories
- نموذج المتصفح العشوائي PageRank
- نمذجة متصفح يتبع الروابط باحتمالية تساوي عامل التخميد ويقفز بخلاف ذلك إلى صفحة عشوائية ينتج عنها سلسلة ماركوف يكون توزيعها الثابت الفريد يسجل الصفحات حسب الزيارات طويلة الأمد، مما يوفر مقياساً مستقراً لأهمية الصفحة ومستقلاً عن الاستعلام.
- محاور وسلطات HITS
- ضمن مخطط فرعي يركز على الاستعلام، تُسند HITS لكل صفحة درجة سلطة تتناسب مع درجات المحور للصفحات التي ترتبط بها ودرجة محور تتناسب مع درجات السلطة للصفحات التي ترتبط بها، ويتم حساب ذلك عن طريق تكرار هذه العلاقات المتآزرة حتى التقارب.
Clinical relevance
كان PageRank محورياً في صعود البحث على الويب على نطاق واسع ولا يزال نقطة مرجعية مفاهيمية للأهمية والسلطة على الرسوم البيانية. وتتجاوز أفكار تحليل الروابط الويب لتشمل شبكات الاستشهاد، وتأثير الشبكات الاجتماعية، واكتشاف الاحتيال، والتوصيات، أينما تحمل الروابط الشبيهة بالتأييد معلومات.
History
في عامي 1998 و 1999، أظهر اقتراحان متزامنان تقريباً أن الروابط التشعبية تُشفّر السلطة: HITS لكلاينبرغ و PageRank لبيج وبرين. وقد أثبتت درجات PageRank المستقلة عن الاستعلام والمحسوبة عالمياً أنها مناسبة تماماً للخدمة على نطاق الويب وأسست لمحرك بحث رائد، بينما أثرت HITS في استخلاص الموضوعات وأبحاث ترتيب الرسوم البيانية اللاحقة.
Key figures
- Larry Page
- Sergey Brin
- Jon Kleinberg
- Rajeev Motwani
Related topics
Seminal works
- page1999
- kleinberg1999
- brin1998
Frequently asked questions
- ما الفرق بين PageRank و HITS؟
- يحسب PageRank درجة أهمية واحدة مستقلة عن الاستعلام لكل صفحة من الرسم البياني الكامل للويب مقدماً، بينما تحسب HITS درجات محور وسلطة تعتمد على الاستعلام على مخطط فرعي صغير مبني حول الاستعلام وقت الاسترجاع. يتوسع PageRank بسهولة أكبر لخدمة الويب.
- لماذا يحتاج PageRank إلى عامل تخميد؟
- بدونه، يمكن أن يعلق المتصفح العشوائي في صفحات لا تحتوي على روابط صادرة أو في دورات، وقد لا يكون التوزيع الثابت فريداً أو معرفاً جيداً. تتيح احتمالية التخميد (الانتقال الآني) للمتصفح القفز أحياناً إلى صفحة عشوائية، مما يضمن درجة فريدة وجيدة السلوك.