مثال على تطبيق في GraphLab

  • 5 دقائق

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

PageRank له تطبيقات مختلفة ولكن يمكن أن تكون فكرته موضّحة مع المعادلة التالية:

$$R[i] = 0.15 + \sum_{j \in Nbr(i)}{w_{ji}} \times R[j]$$

يمثل $R[i]$ قيمة PageRank لدى الصفحة $i$. $Nbr(i)$ هو مجموعة الصفحات التي تشير إلى الصفحة $i$. و$w_{ji}$ هو الوزن المرتبط بهذا الرابط، والذي يتم تعريفه عادةً على أنه معكوس عدد حواف الصفحة $j$ الموجهة للخارج.

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

لتنفيذ هذه الخوارزمية باستخدام GraphLab، نقوم أولاً بتعيين المشكلة إلى تجريد يستند إلى الرسم البياني. بالنسبة إلى PageRank، يجب أن يكون هذا الأمر بديهيًا؛ وينبغي أن تتوافق ذروات الرسم البياني مع الصفحات والحواف مع روابط الصفحات. نضيف أيضًا معلمة لكل ذروة، وتصنيف الصفحة، ويشار إليها على أنها $R[i]$. الآن بعد أن يتم تمثيل البيانات في GraphLab، فإننا نحلل العملية التي تم التعبير عنها في معادلة PageRank إلى خطوات الجمع والتطبيق والمبعثر في تجريد GraphLab:

الخوارزمية 3

خوارزمية PageRank لـ $(i)$ على GraphLab، مع التنفيذ على الصفحة $i$

  • جمع دالة $(j, i)$ :
    • العودة $w_ {ji} \times R [j] $
  • الدالة Sum $(a, b)$ :
    • إرجاع $ (أ + ب) $
  • تطبيق دالة $(i, \Sigma)$ :
    • $R[i] = 0.15 + \ سيجما $
  • دالة مبعثرة $(i, j)$ :
    • إذا تغير $R[i]$، فقم بتشغيل $j$ لتتم إعادة حسابها (أن تكون نشطة)

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