خوارزمية PageRank الموزونة
- قدّمه
- Xing, W. & Ghorbani, A.
- السنة
- 2004
- النوع
- Centrality measure / ranking algorithm
- العائلة
- Network science
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تُوسِّع خوارزمية PageRank الموزونة خوارزمية PageRank الكلاسيكية للشبكات التي تحمل فيها الحواف أوزانًا أو ترددات مختلفة، وتوزع الأهمية بما يتناسب مع أوزان الحواف الواردة والصادرة على حد سواء بدلاً من معاملة جميع الروابط بالتساوي. هذا يجعلها أكثر إفادة بشكل كبير من PageRank الثنائية في أي شبكة تكون فيها قوة الاتصال مهمة.
الفكرة الحدسية وراء الطريقة
تعامل خوارزمية PageRank الكلاسيكية كل رابط تشعبي أو رابط بنفس الطريقة: يكتسب العقدة نفس المكانة من اتصال ضعيف كما من اتصال قوي. تُصحح خوارزمية PageRank الموزونة هذا عن طريق قياس كل تصويت حسب الوزن النسبي للحافة. العقدة التي تتلقى العديد من الروابط الواردة ذات الوزن الثقيل من عقد مهمة بالفعل ترتفع أعلى في الترتيب، بينما تظل العقدة ذات الاتصالات العديدة ولكن الضعيفة متواضعة. هذا يعكس كيف تتراكم التأثيرات فعليًا في معظم الشبكات الواقعية، حيث تشير ترددات التفاعل أو حجم المعاملات إلى الأهمية الحقيقية.
التاريخ
تم تقديم PageRank بواسطة Brin و Page في عام 1998 كأساس لمحرك بحث Google، مع معاملة جميع الروابط التشعبية كأصوات متساوية. تم إضفاء الطابع الرسمي على PageRank الموزونة بواسطة Xing و Ghorbani في عام 2004، مما وسع الخوارزمية لتخصيص توزيع الترتيب بما يتناسب مع أوزان الحواف، بالاعتماد على كسور الوزن الوارد والصادر. منذ ذلك الحين تم تطبيقها عبر تحليل الاستشهادات، والمعلوماتية الحيوية، وتحليل الشبكات الاجتماعية، وأنظمة التوصية حيثما كانت قوة الرابط مؤشرًا ذا مغزى للتأثير.
متى تُستخدم
استخدام خوارزمية PageRank الموزونة عندما تحتوي شبكتك على أوزان حواف ذات مغزى وتحتاج إلى ترتيب أهمية عالمي للعقد يراعي التدفق. إنها مثالية لشبكات الاستشهاد مع عدد الاستشهادات المشتركة، ورسومات الويب مع حجم حركة المرور، وشبكات التفاعل البيولوجي مع مستويات التعبير، والشبكات الاجتماعية مع ترددات التفاعل، وشبكات المعاملات المالية. يُفضل استخدام PageRank الموزونة على PageRank الثنائية كلما كان تجاهل قوة الحافة سيشوه تدفق التأثير. تجنبها عندما تكون أوزان الحواف غير موثوقة أو تم تعيينها بشكل عشوائي، وعندما تكون الشبكة متفرقة جدًا والأوزان ثنائية في الغالب (يكفي استخدام PageRank العادية)، أو عندما تحتاج إلى مقياس مركزية محلي بحت مثل الدرجة الموزونة. إنها غير مناسبة للشبكات غير الموجهة حيث يكون اتجاه التدفق غير ذي معنى من الناحية المفاهيمية.
الحدود والاعتبارات
- تتطلب أن تكون أوزان الحواف ذات مغزى ويتم قياسها بشكل موثوق؛ الأوزان المشوشة أو العشوائية تقلل من جودة الترتيب.
- عامل التخميد (d) هو معلمة حرة؛ قد لا يكون 0.85 التقليدي مثاليًا للشبكات غير الويب.
- حساسة لمخطط تسوية الوزن المختار؛ يمكن أن تختلف النتائج إذا تم دمج الأوزان الواردة والصادرة بشكل مختلف.
- لا تميز بين أنواع مختلفة من الحواف؛ قد يؤدي نموذج الوزن الواحد إلى انهيار اختلافات هيكلية مهمة.
- يمكن أن يكون التقارب بطيئًا على الشبكات الكبيرة جدًا والكثيفة بدون تطبيقات فعالة للمصفوفات المتفرقة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تدمج قوة الحافة مباشرة في انتشار الأهمية، مما يعطي ترتيبات أكثر واقعية من PageRank الثنائية في الشبكات الموزونة.
- تلتقط المكانة العالمية على مستوى الشبكة بأكملها بدلاً من مجرد الاتصال المحلي.
- تحافظ على آلية الانتقال العشوائي لـ PageRank، مما يجعلها قوية ضد العقد المتدلية والمكونات المنفصلة عند تصحيحها.
- تتوسع لتشمل الشبكات الكبيرة من خلال الحساب التكراري الفعال؛ عمليات المصفوفات المتفرقة تحافظ على قابلية الذاكرة للإدارة.
- قابلة للتفسير بسهولة: درجة عالية تعني أن العقدة تتلقى تأييدًا قويًا وموزونًا من عقد أخرى ذات درجات عالية.
التطبيقات
- تحديد الأوراق البحثية أو المؤلفين المؤثرين في شبكات الاستشهاد والاستشهاد المشترك الموزونة.
- ترتيب صفحات الويب أو المستندات عندما تتوفر أحجام حركة مرور الروابط التشعبية أو معدلات النقر.
- اكتشاف البروتينات أو الجينات الرئيسية في شبكات التفاعل البيولوجي الموزونة.
- ترتيب العقد في شبكات المعاملات المالية حسب تدفق حجم المعاملات.
- ترتيب المستخدمين أو المحتوى في الرسوم البيانية للتفاعل في وسائل التواصل الاجتماعي الموزونة.
- بناء أنظمة توصية حيث تعمل ترددات تكرار العناصر كأوزان للحواف.
كيف يعمل
كيف يعمل
تمثيل الشبكة كرسم بياني حيث تحمل كل حافة وزنًا رقميًا يعكس قوة الرابط - مثل تردد التفاعل، حجم المعاملات، عدد المشاركات في التأليف، أو درجة التشابه. تتطلب الخوارزمية أن تكون هذه الأوزان غير سالبة؛ يجب تحويل الأوزان السالبة قبل التحليل.
لكل حافة موجهة من العقدة v إلى العقدة u، يتم حساب عاملين وزنين: عامل وزن وارد يُطَبِّع وزن الحافة بقسمته على إجمالي الوزن الوارد للعقدة u، وعامل وزن صادر يُطَبِّع وزن الحافة بقسمته على إجمالي الوزن الصادر للعقدة v. تحدد هذه الكسور مقدار الترتيب الذي توزعه العقدة v على العقدة u عبر هذه الحافة المحددة.
الصيغة
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}تطبيق صيغة PageRank الموزونة بشكل تكراري: يساوي ترتيب كل عقدة حد انتقال أساسي (1 ناقص عامل التخميد d، عادةً 0.85) زائد d مضروبًا في مجموع ترتيب جميع الجيران الواردين مضروبًا في العاملين الوزنين. هذا يوزع الترتيب بما يتناسب مع قوة الحافة بدلاً من توزيعه بشكل موحد.
الصيغة
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)تكرار تحديث الترتيب حتى ينخفض التغيير في درجة كل عقدة عن قيمة تسامح صغيرة (عادةً 1e-6). يضمن التقارب للرسوم البيانية المتصلة بقوة؛ بالنسبة للرسوم البيانية التي تحتوي على عقد متدلية أو مكونات معزولة، يتم تطبيق تصحيح العقد المتدلية القياسي قبل التكرار.
بمجرد تقارب الدرجات، يتم فرز جميع العقد حسب درجة PageRank الموزونة بترتيب تنازلي. تعكس هذه الرتب الأهمية الهيكلية العالمية لكل عقدة مع مراعاة كل من طوبولوجيا الشبكة وقوة الحافة.
الأخطاء الشائعة
- استخدام أوزان الحواف الخام وغير المطبعة دون التحقق من مقياسها - خلط الأعداد في العشرات مع القيم بالملايين يشوه انتشار الترتيب.
- نسيان معالجة العقد المتدلية (العقد التي لا تحتوي على حواف صادرة)، والتي يمكن أن تستنزف الترتيب من الشبكة بأكملها إذا لم يتم تصحيحها.
- افتراض أن عامل التخميد الافتراضي 0.85 مناسب عالميًا؛ في شبكات الاستشهاد أو الشبكات البيولوجية، قد يعكس قيمة مختلفة المجال بشكل أفضل.
- تفسير درجات PageRank الموزونة على أنها احتمالات مطلقة بدلاً من ترتيبات نسبية - فقط ترتيبها مستقر عبر تشغيلات مختلفة.
- مقارنة درجات PageRank الموزونة عبر شبكات ذات أحجام مختلفة بدون تسوية.
الأسئلة الشائعة
كيف تختلف خوارزمية PageRank الموزونة عن خوارزمية PageRank القياسية؟
توزع خوارزمية PageRank القياسية ترتيب العقدة بالتساوي على جميع جيرانها الصادرين بغض النظر عن قوة الحافة. تقوم خوارزمية PageRank الموزونة بقياس هذا التوزيع حسب الوزن الوارد والصادر النسبي لكل حافة، لذلك تحمل الاتصالات الأقوى ترتيبًا متناسبًا.
ما هو عامل التخميد الذي يجب أن أستخدمه؟
القيمة التقليدية هي 0.85، مستمدة من افتراضات الرسم البياني للويب حول التصفح العشوائي. بالنسبة للشبكات الاجتماعية أو البيولوجية أو شبكات الاستشهاد، يتم استكشاف القيم بين 0.5 و 0.9 في الأدبيات. يوصى بتحليل الحساسية عبر نطاق من قيم التخميد.
هل يمكن تطبيق خوارزمية PageRank الموزونة على الشبكات غير الموجهة؟
نعم، عن طريق تمثيل كل حافة غير موجهة كزوج من الحواف الموجهة بنفس الوزن. ثم تنتج الخوارزمية عوامل وزن وارد وصادر متناظرة، مما يبسط إلى صيغة لا تزال تحترم قوة الحافة.
كيف أتعامل مع الحواف ذات الوزن الصفري؟
الحواف ذات الوزن الصفري لا تساهم في انتشار الترتيب، لذلك يمكن إزالتها قبل التحليل. إذا كانت الأوزان الصفرية ذات مغزى هيكلي (غياب مقابل بيانات مفقودة)، قم بتوثيق التمييز بوضوح قبل إزالتها.
هل خوارزمية PageRank الموزونة أفضل من مركزية الدرجة الموزونة؟
يعتمد على سؤال البحث. تلتقط مركزية الدرجة الموزونة الاتصالات المباشرة فقط، بينما تلتقط PageRank الموزونة المكانة العالمية المنتشرة عبر الشبكة بأكملها. استخدم الدرجة الموزونة للتأثير المحلي و PageRank الموزونة للأهمية على مستوى الشبكة.
طرق ذات صلة
المصادر
Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.
افتح مرجع DOIتم النسخ.PageRank. Wikipedia.
افتح مرجع المنشورتم النسخ.