حساب Pageranks للحصول على رسم بياني موجه متناثر بنسبة عالية من الروابط المميتة

Question

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

بواسطة deadlinks أعني العقد التي لها صفر. في بعض الأحيان ، في رسم بياني مع الكثير من الروابط المميتة ، قد تحدث مصائد العنكبوت. على أي حال ، فإن المشكلة التي أهتم بها هي اكتشاف Pageranks في هذا السيناريو.

وأنا أستخدم Jung (Java Universal Graph Network) لحساب Pageranks.

عندما أستخدم الإجراء العادي ،

Graph<String, String> jungGraph = new DirectedSparseGraph<String, String>();
PageRank<String, String> pagerank = new PageRank<String,String>(jungGraph, 0.2);
pagerank.setMaxIterations(20);
pagerank.setTolerance(0.000001);
pagerank.evaluate();

أحصل على نفس قيم Pagerank نفسها لجميع العقد ، عندما أعرف بوضوح أنه لا ينبغي أن يكون كذلك. نظرًا لأن بعض العقد في الرسم البياني لديها عدد كبير من العقد الصادرة وترتبط بقوة.

ما هو النهج المقترح في هذه الحالة. أعلم أن هناك هذا الطبقة pagerankwithPriors. هل يجب علي أولاً استخراج الشبكة بدون ارتباطات deadlinks ، وحساب Pageranks لهم ، ثم نشر رتبتها إلى الروابط المميتة حتى تتلاقى. في الحالة الأخيرة ، سيكون لجميع العقد في الشبكة المخفضة (OuteGree! = 0) مجموعة Priors الخاصة بهم ، في حين أن الروابط المميتة لن.

هل أفتقد أي شيء هنا؟

Answer 1

لا أعتقد PageRankWithPriors هو ما تريد.

أي نسخة من PageRank هل تستخدم؟ الفصل edu.uci.ics.jung.algorithms.importance.PageRank أو edu.uci.ics.jung.algorithms.scoring.PageRank؟ تم إهمال السابق لصالح الأخير في بيتا Jung 2.0.

يبدو أنهم يعاملون العقد الخارجة عن العقد بشكل مختلف ، والتي قد تكون مشكلتك. تقول المواصفات السابقة:

احتمال الانتقال من العقدة U إلى العقدة V يساوي (1-alpha)1/Offegree (u)] + ألفا(1/| V |)

إذا لم يكن لديك حواف خارجية في الرسم البياني الأصلي ، فسيتم استخدام 0 بدلاً من 1/Outsegree (V).

يبدو هذا خطأً ، لأنه يؤدي إلى فقدان الاحتمال (يجب أن يساوي الاحتمال الكلي لتركك بطريقة ما 1 ، ولا يفعل ذلك). هذا الأخير يفعل ذلك بشكل مختلف:

إذا لم يكن لدى قمة الرأس حواف صادرة ، فإن احتمال أخذ قفزة عشوائية من تلك القمة (بشكل افتراضي) فعليًا 1

يجب أن يحافظ على الاحتمال وهو ما تريده.