🎛️ احسب بايج رانك لشبكة ويب مصغرة من 6 صفحات
في كل تكرار، تعيد كل صفحة توزيع نقطتها على جاراتها. بعد بضعة تكرارات، تستقر النقط: هذا هو بايج رانك.
التكرار
0
الصفحة الأكثر أهمية
C (0.167)
مجموع النقط
1.000
التكرار 0: تبدأ كل النقط عند 1/6 ≈ 0.167. انقر «تكرار +1» لرؤية النقط تتطور.
🌐 1998: طالبا دكتوراه تخطر لهما فكرة غريبة
في عام 1998، كان محرك البحث المهيمن يسمى AltaVista. كان يصنف صفحات الويب حسب تواتر الكلمات المفتاحية. من أراد الظهور في أعلى القائمة كان يحشو صفحته بالكلمات الشائعة. كانت النتائج كارثية.
طالبا دكتوراه من جامعة ستانفورد، لاري بايج وسيرغي برين، اقترحا فكرة مختلفة جذريا: عدم النظر إلى محتوى الصفحة، بل إلى من يشير إليها. إذا استشهدت بك كثير من الصفحات المهمة، فأنت مهمة. هذا كل شيء.
الفكرة المركزية لبايج رانك
نقطة الصفحة = مجموع نقط الصفحات التي تشير إليها، مقسوما على
عدد روابطها الصادرة.
لكن هذا التعريف دائري: لمعرفة نقطة A، يجب معرفة نقطة B. لكن لمعرفة نقطة B، يجب معرفة نقطة A…
⚡ المعادلة السحرية: نظمة خطية
لنصغها صياغة رسمية. لنرمز بـ N لعدد الصفحات، وبـ Pi لنقطة الصفحة i. لكل صفحة:
Pi = ∑j → i Pj / L(j)
حيث L(j) = عدد الروابط الصادرة من الصفحة j
تصف هذه المعادلة كل صفحة بدلالة الأخريات. إنها نظمة خطية ذات N معادلة وN مجهولا. بالكتابة المصفوفية:
P = M · P
حيث P هو متجهة النقط وM هي مصفوفة الانتقال لمبيان الويب. إذن فبايج رانك هو متجهة ذاتية للمصفوفة M مرتبطة بالقيمة الذاتية 1.
🎯 كيف نحسبه عمليا؟
قلب مصفوفة N × N عندما يكون N = 10 مليار (حجم الويب)، أمر مستحيل مباشرة. الحيلة: التكرار.
- هيّئ كل النقط عند 1/N (صفحات متكافئة مبدئيا).
- طبّق M · P: كل صفحة تعيد توزيع نقطتها على جاراتها.
- أعد الكرة بمتجهة النقط الجديدة P.
- بعد حوالي عشرين تكرارا، تتقارب P نحو بايج رانك.
إنها طريقة القوى في الجبر الخطي. تتقارب لأن المصفوفة M لها بنية خاصة (مصفوفة عشوائية: مجموع أعمدتها يساوي 1) تضمن وجود متجهة ذاتية مهيمنة.
🎲 التأويل الاحتمالي: «المتصفح العشوائي»
يوجد تأويل رائع لبايج رانك. تخيل متصفح إنترنت يتصفح عشوائيا:
- ينطلق من صفحة كيفما كانت.
- في كل نقرة، يختار رابطا صادرا عشوائيا باحتمال 1/L(الصفحة).
- يستمر إلى ما لا نهاية.
على المدى الطويل، فإن نسبة الوقت المقضي على كل صفحة تساوي بالضبط بايج رانك الخاص بها. نقطة الصفحة = احتمال التواجد عليها في لحظة معينة إذا تصفحنا عشوائيا. إذن فبايج رانك هو توزيع مستقر لسلسلة ماركوف.
🛡️ عامل التخميد: تجنب الفخاخ
مشكلة: إذا لم يكن لصفحة أي رابط صادر («طريق مسدود»)، يبقى المتصفح عالقا. وإذا كانت مجموعة من الصفحات تشير إلى نفسها في حلقة مغلقة، يدور المتصفح في حلقة مفرغة.
حل بايج وبرين: في كل نقرة، باحتمال 1 − d ≈ 15%، يقوم المتصفح بالانتقال الآني عشوائيا إلى أي صفحة في الويب. يسمى العامل d عامل التخميد (عادة d = 0.85). تصبح الصيغة:
Pi = 1 − dN + d · ∑j → i Pj / L(j)
يضمن هذا التعديل التقارب ويمنع «تلاعبات» بايج رانك من طرف مديري المواقع الخبثاء الذين قد ينشئون مزارع روابط.
📐 كيف يندرج هذا في برنامجك؟
لن ترى بايج رانك في بكالوريا العلوم الرياضية، لكن المادة الكامنة وراءه موجودة في برنامجك:
- المصفوفات والمحددات (الثانية بكالوريا علوم رياضية): بايج رانك حساب مصفوفي.
- المتجهات الذاتية والقيم الذاتية (ما بعد البكالوريا، الأقسام التحضيرية): بايج رانك هو المتجهة الذاتية لمصفوفة الانتقال للقيمة الذاتية 1.
- سلاسل ماركوف (جامعي): مشية المتصفح العشوائي هي سلسلة ماركوف، وبايج رانك الخاص بها هو القياس المستقر.
- الاحتمالات الشرطية: احتمال الانتقال من الصفحة A إلى الصفحة B علما أننا في A يساوي 1/L(A).
🎓 الإرث: بايج رانك ألهم عشرات الخوارزميات
- HITS (كلاينبرغ، 1999): ابن عم لبايج رانك بنقطتين لكل صفحة (محور وسلطة).
- SimRank: قياس التشابه بين صفحتين مبني على بايج رانك.
- Personalized PageRank: نوع يفضل فيه المتصفح صفحات معينة حسب المستخدم. يُستعمل للتوصيات.
- EigenTrust: امتداد لبايج رانك لحساب السمعة في شبكات الند للند (P2P).
- مركزية المتجهة الذاتية في نظرية المبيانات: التعميم الأكاديمي لبايج رانك، يُستعمل في تحليل الشبكات الاجتماعية، والمعلوماتية الحيوية، وعلوم الأعصاب.