الانتقال إلى المحتوى
العودة إلى نتائج البحث

مركزية بيج رانك

قدّمه
Page, Brin, Motwani & Winograd
السنة
1999
النوع
Iterative link-based centrality algorithm
العائلة
Centrality

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

بيج رانك هو خوارزمية مركزية تعتمد على الروابط تقوم بتعيين درجة أهمية لكل عقدة في رسم بياني موجه عن طريق قياس عدد العقد عالية الجودة التي تشير إليها. قدمها لاري بيج وسيرجي برين وراجيف موتواني وتيري وينوغراد في جامعة ستانفورد عام 1999، وأصبحت الأساس الرياضي لمحرك بحث جوجل ولا تزال واحدة من أكثر الخوارزميات تأثيراً في علم الشبكات واسترجاع المعلومات.

الفكرة الحدسية وراء الطريقة

تخيل متصفح ويب عشوائي ينقر على الروابط بشكل عشوائي، ويقفز أحيانًا إلى صفحة عشوائية تمامًا بدلاً من اتباع رابط. نسبة الوقت الذي يقضيه هذا المتصفح على كل صفحة، بعد عدد لا نهائي من النقرات، هي بيج رانك لتلك الصفحة. الصفحة التي تتم زيارتها كثيرًا - لأن العديد من الصفحات الشائعة ترتبط بها - تحصل على درجة عالية. عامل التخميد (عادة 0.85) ينمذج احتمالية الاستمرار في النقر بدلاً من القفز.

التاريخ

تم تطوير بيج رانك في جامعة ستانفورد بواسطة لاري بيج وسيرجي برين كآلية ترتيب أساسية لمشروع البحث الخاص بهما BackRub، والذي أصبح جوجل في عام 1998. تم نشر التقرير الفني الأساسي، بالاشتراك مع راجيف موتواني وتيري وينوغراد، في عام 1999. أدت الخوارزمية إلى تعميم استخدام المركزية القائمة على المتجهات الذاتية في الشبكات الموجهة واسعة النطاق وألهمت بشكل مباشر خوارزميات تحليل الروابط اللاحقة بما في ذلك HITS و TrustRank.

متى تُستخدم

بيج رانك مناسب عندما تحتاج إلى ترتيب العقد في رسم بياني موجه حسب الأهمية الهيكلية العالمية، خاصة عندما يمثل اتجاه الحافة المصادقة أو التأثير (الروابط التشعبية، الاستشهادات، المتابعات الاجتماعية). يفترض أن الرسم البياني يمكن نمذجته كسلسلة ماركوف ويتطلب مكونًا متصلاً أو متصلاً بقوة للتقارب النظيف. إنه أقل ملاءمة للشبكات غير الموجهة حيث قد يُفضل HITS أو مركزية البينية، ويمكن أن يكون حساسًا لبريد الروابط أو زيادة درجة الدخول بشكل مصطنع.

الحدود والاعتبارات

  • يتطلب رسمًا بيانيًا موجهًا؛ تطبيق على الشبكات غير الموجهة يحتاج إلى خيارات اتفاقية
  • تعتمد سرعة التقارب على الفجوة الطيفية لمصفوفة الانتقال ويمكن أن تكون بطيئة للرسوم البيانية ضعيفة الاتصال
  • حساس لاختيار عامل التخميد d؛ يمكن أن تؤدي القيم المختلفة إلى تغيير التصنيفات بشكل كبير
  • عرضة للتلاعب بمزارع الروابط والروابط الواردة المبنية بشكل مصطنع

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • أساس احتمالي مبدئي عبر نموذج سلسلة ماركوف للمتصفح العشوائي
  • يتوسع إلى رسوم بيانية كبيرة جدًا من خلال ضربات المصفوفة المتفرقة والتكرار القوي
  • يلتقط طوبولوجيا الرسم البياني العالمية، ويكافئ العقد التي صادقت عليها العقد الأخرى ذات الدرجات العالية
  • تم التحقق منه على نطاق واسع عبر مجالات الويب، والاستشهادات، والشبكات البيولوجية، والاجتماعية

التطبيقات

  • ترتيب محرك البحث على الويب: ترتيب نتائج البحث حسب السلطة العالمية لصفحات الويب
  • تحليل الاستشهادات الأكاديمية: تحديد الأوراق أو المجلات المؤثرة في شبكات الأدبيات العلمية
  • قياس التأثير في الشبكات الاجتماعية: ترتيب المستخدمين حسب هيبة متابعيهم
  • تحليل الشبكات البيولوجية: العثور على البروتينات أو الجينات المحورية في شبكات تفاعل البروتين وتنظيم الجينات
  • أنظمة التوصية: نشر إشارات التفضيل عبر الرسوم البيانية الثنائية للمستخدم والعنصر

كيف يعمل

كيف يعمل

1

تبدأ كل عقدة في الرسم البياني بدرجة بيج رانك متساوية تبلغ 1/N، حيث N هو العدد الإجمالي للعقد. يضمن هذا التهيئة الموحدة عدم حصول أي عقدة على بداية مصطنعة ويوفر توزيع احتمالية صالح عبر الشبكة قبل التكرار الأول.

الصيغة
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

يتم بناء مصفوفة انتقال عمودية تجميعية M من بنية التجاور للرسم البياني. كل مدخل M_ij يساوي 1 مقسومًا على درجة الخروج للعقدة j إذا كان هناك حافة من j إلى i، وصفر بخلاف ذلك. عادةً ما يتم التعامل مع العقد المتدلية (بدون حواف صادرة) عن طريق إعادة توزيع درجتها بشكل موحد على جميع العقد.

الصيغة
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

يتم تحديث متجه بيج رانك بشكل تكراري باستخدام صيغة المتصفح العشوائي. مع عامل التخميد d (الافتراضي 0.85)، تتلقى كل عقدة احتمال انتقال أساسي (1-d)/N بالإضافة إلى d مضروبًا في المجموع الموزون للدرجات المساهمة من جميع العقد التي ترتبط بها. يتم تكرار هذه الخطوة حتى تستقر الدرجات.

الصيغة
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

بعد كل تكرار، تتم مقارنة معيار L1 للتغيير في متجه الدرجات مع تسامح صغير epsilon (على سبيل المثال، 1e-6). عندما يقع التغيير أقل من هذا الحد، تكون الخوارزمية قد تقاربت ويتم إرجاع متجه الدرجات الحالي كتوزيع بيج رانك النهائي.

الصيغة
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

الأخطاء الشائعة

  • تجاهل العقد المتدلية (العقد التي لا تحتوي على حواف صادرة) يمكن أن يكسر الخاصية التجميعية لمصفوفة الانتقال ويسبب درجات غير صحيحة
  • استخدام بيج رانك على الرسوم البيانية غير الموجهة دون تحويلها إلى نموذج انتقال متماثل قد ينتج تقديرات مركزية مضللة
  • ضبط التسامح بشكل فضفاض جدًا يؤدي إلى تقارب مبكر؛ ضيق جدًا يزيد الحساب دون تغييرات درجات ذات مغزى
  • تفسير بيج رانك كمقياس أهمية مطلق بدلاً من ترتيب نسبي في سياق رسم بياني معين

الأسئلة الشائعة

ماذا يمثل عامل التخميد d وكيف ينبغي اختياره؟

عامل التخميد d (عادة 0.85) هو احتمالية أن يتبع المتصفح العشوائي رابطًا بدلاً من الانتقال إلى عقدة عشوائية. القيم القريبة من 1 تجعل الخوارزمية أكثر حساسية لهيكل الرسم البياني ولكنها أبطأ في التقارب وأكثر عرضة لمصارف الترتيب؛ القيم القريبة من 0 تقترب من الترتيب الموحد. تم التحقق من القيمة 0.85 تجريبياً بواسطة بيج وبرين لرسم الويب وهي القيمة الافتراضية القياسية.

كيف يختلف بيج رانك عن مركزية الدرجة؟

تقوم مركزية الدرجة بحساب العدد المباشر للروابط الواردة إلى عقدة فقط، وتعامل جميع المصادر بالتساوي. يقوم بيج رانك بوزن كل رابط وارد بدرجة العقدة المرتبطة، لذا فإن المصادقة من عقدة ذات ترتيب عالٍ تساهم أكثر من عقدة ذات ترتيب منخفض. هذا التعريف التكراري يلتقط هيكل الرسم البياني العالمي بدلاً من مجرد الاتصال المحلي.

هل يمكن تطبيق بيج رانك على الرسوم البيانية غير الموجهة؟

نعم، ولكن مع محاذير. يجب تحويل الرسم البياني غير الموجه إلى تمثيل موجه عن طريق استبدال كل حافة غير موجهة بحافتين موجهتين. ثم تصبح درجات بيج رانك الناتجة دالة لدرجة العقدة، مما يقلل الخوارزمية إلى مركزية درجة موزونة. بالنسبة للشبكات غير الموجهة، غالبًا ما تكون مقاييس المركزية البديلة مثل المركزية المتجهة أو المركزية البينية أكثر إفادة.

طرق ذات صلة

المصادر

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    افتح مرجع المنشور
    تم النسخ.