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

المبادئ الأساسية

عندما نكون على صفحة ويب، تشير الروابط في تلك الصفحة إلى صفحاتٍ أخرى ذات صلةٍ بمحتوى الصفحة التي نتصفحها في الوقت الحالي. ووجود ذلك الرابط في حد ذاته يدل على أهمية صفحة الويب الموجودة في نهاية الرابط، وإلا لما أضاف مؤلِّف صفحة الويب رابطها من البداية. انظر مثال المخطَّط البياني التالي الذي يمثِّل مجموعة صغيرة من صفحات الويب يرتبط بعضها ببعض:

في مخطَّط بياني كهذا، نسمي الروابط التي تشير إلى صفحة ويب «الروابط الخلفية»؛ وبالتبعية، سنسمي الصفحات التي تشير إلى صفحة ويب أيضًا «الروابط الخلفية». وبذلك تكون الروابط الخلفية لصفحة الويب رقم ٣ هي الحواف التي تشير إليها — الحواف المتجهة إليها — وهي كذلك العُقَد التي تبرز منها وهي صفحات الويب رقم ٢ و٤ و٥. في هذا الفصل، سنهتم بالمخططات البيانية التي تتكوَّن من صفحات الويب؛ ومِن ثَم سنستخدم المصطلحين «عقدة» و«صفحة» بالتبادل.

لنفترض أننا نريد إيجاد درجة أهمية الصفحة رقم ٣. رأينا أن الروابط الخلفية لها هي الصفحات ٢ و٤ و٥. نأخذ كل صفحة منها تِباعًا، ونفترض أننا نعرف ثِقلها. الصفحة ٢ تقسم أهميتها على الصفحتين ٣ و٥، وعليه سنعطي نصف أهميتها للصفحة رقم ٣. الصفحة ٤ أيضًا تقسم أهميتها على الصفحتين ٣ و١، وعليه سنعطي نصف أهميتها للصفحة رقم ٣. وأخيرًا، الصفحة ٥ تقسم أهميتها على الصفحات ٢ و٣ و٤، وعليه سنعطي ثلث أهميتها للصفحة رقم ٣. توفيرًا للكتابة، لنعبِّر بالرموز ، حيث تعبِّر عن أهمية الصفحة، بينما يرمز الحرف إلى ترتيب الصفحة. إذن، قيمة أهمية الصفحة ٣ سوف تساوي:

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

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

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

قد يبدو هذا أشبه باحتيالٍ شرعي؛ لأنه في الواقع يخبرنا بأنه لا بد أن نجد أهمية الروابط الخلفية لصفحة ويب ما من أجل إيجاد أهميتها. إذا اتبعنا أسلوب الاستدلال نفسه لإيجاد أهمية كل رابط من الروابط الخلفية الخاصة بتلك الصفحة، فلا بد أن نوجد درجة أهمية الروابط الخلفية لذلك الرابط الخلفي. عندئذٍ تبدو العملية تتراجع أكثر وأكثر — من روابط خلفية إلى روابط خلفية — وفي النهاية نُترك دون معرفة كيفية حساب أهمية صفحة الويب من المكان الذي بدأنا من عنده. الأسوأ من ذلك أننا قد نجد أنفسنا ندور في دوائر. في المثال الذي بين أيدينا، كي نحسب أهمية الصفحة رقم ٣، نحتاج إلى معرفة درجة أهمية الصفحات ٢ و٤ و٥. ولحساب أهمية الصفحة ٢، نحتاج إلى أهمية الصفحة ١ (والصفحة ٥، ولكن لننحي هذا جانبًا الآن). ولحساب أهمية الصفحة ١، نحتاج إلى أهمية الصفحة ٤، ولإيجاد أهميتها، نحتاج إلى معرفة أهمية الصفحة ٣. لقد عُدنا إلى حيث بدأنا.

مثال

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

ترسل الصفحة ١ صوتها إلى الصفحة ٢، وهي الصفحة الوحيدة المرتبطة بها. تقسم الصفحة ٢ صوتها إلى جزأين، وترسل النصف إلى الصفحة ٣، والنصف الآخر إلى الصفحة ٥. تقسم الصفحة ٣ صوتها إلى ثلاثة أجزاء، وترسل ثلثًا واحدًا إلى كلٍّ من الصفحات ١ و٤ و٥. وتصوِّت الصفحتان ٤ و٥ بالطريقة نفسها.

بمجرد انتهاء التصويت، ستحسب كل صفحة الإجمالي من مجموع الأصوات — أو كسور الأصوات — التي تلقتها من روابطها الخلفية. على سبيل المثال، بما أن الصفحة رقم ١ تلقت أصواتًا من الصفحتين ٣ و٤، فستكون درجة أهميتها ١ / ٢ + ١ / ٣ = ٥ / ٦ من الأصوات، وبما أن الصفحة ٣ تلقت أصواتًا من الصفحات ٢ و٤ و٥، فستحصل على ١ / ٢ + ١ / ٢ + ١ / ٣ = ٤ / ٣ من الأصوات. من ذلك نرى أن الصفحة رقم ١ قلَّلت حصتها من الأصوات مقارنةً بما بدأت به، بينما زادت الصفحة رقم ٣ من حصتها.

الآن، لنغير الإعداد قليلًا. بدلًا من إعطاء كل صفحة صوتًا واحدًا قبل بدء التصويت، سنعطي كل صفحة ١ / ٥ صوت بحيث يصبح مجموع الأصوات واحدًا. وبوجه عام، إذا كان لدينا العدد من الصفحات، فسنعطي من الأصوات لكل صفحة منها. أما باقي العملية فسيظل كما هو بالضبط. إجمالي قيمة الأهمية لجميع صفحات الويب يساوي واحدًا، ومرة أخرى تُقسَّم الأهمية بالتساوي بين جميع صفحات الويب.

بعد انتهاء التصويت، ستكون درجة أهمية كل صفحة ويب قد تغيَّرت. فبدلًا من أن تساوي أهمية كل الصفحات ١ / ٥ = ٠٫٢، سنجد، بإجراء الحسابات، أنها تساوي ٠٫١٧ و٠٫٢٧ و٠٫٢٧ و٠٫١٣ و٠٫١٧ لكل صفحة تباعًا. صفحتا الويب ٢ و٣ زادت قيمة أهميتهما، ولكن الصفحات ١ و٤ و٥ قلَّت قيمة أهميتها. حاصل جمع الأهمية الإجمالية لصفحات الويب يساوي واحدًا.

يمكننا الآن البدء في جولة تصويت جديدة باستخدام القواعد نفسها بحذافيرها. ستوزِّع الصفحات الأصوات التي جمعتها على الصفحات المرتبطة بها. وفي نهاية هذه الجولة الثانية، ستحصي كل صفحة أصواتها لتحديد موقفها من حيث درجات الأهمية المجمَّعة. بعد إجراء العمليات الحسابية، ستكون قيم الأهمية الجديدة كما يلي: ٠٫١٦ و٠٫٢٢ و٠٫٢٦ و٠٫١٤ و٠٫٢٢.

سنعيد العملية مرة أخرى بحذافيرها. في الحقيقة، سنعيد عملية التصويت مرارًا وتكرارًا. وإذا فعلنا ذلك، فستتطور الأصوات — أو الأهمية المعينة لكل صفحة — كما هو مبيَّن في الجدول التالي، الذي يُظهر القيم الأولية والنتائج بعد كل جولة تصويت:

إذا شرعنا في إجراء جولة تصويت سابعة، فسنكتشف أن الموقف لن يتغيَّر مقارنة بجولة التصويت السادسة. فستظل الأصوات كما هي دون تغيير؛ ومِن ثَم لن تتغيَّر أهمية صفحات الويب. وعندئذٍ نستخلص النتيجة النهائية. فيكون ترتيب صفحات الويب بأن الصفحة رقم ٣ هي الأهم، يتبعها الصفحة رقم ٢ ثم الصفحة رقم ٥ ثم الصفحة رقم ١ وأخيرًا الصفحة رقم ٤.

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

السؤال هنا بالطبع هو ما إذا كان النهج الذي وصفناه لتونا يصلح بوجه عام وليس فقط في هذا المثال أم لا. إضافة إلى ذلك، هل يخرج لنا بنتائج منطقية؟

مصفوفة الارتباطات التشعُّبية وطريقة الأس

طريقة حساب أهمية صفحة ما بناءً على أهمية روابطها الخلفية لها صيغة ممتازة. نبدأ من المخطَّط البياني الذي يصف الروابط بين صفحات الويب. يمكننا التعبير عن المخطَّط البياني باستخدام «مصفوفة» أعداد نطلق عليها «مصفوفة التجاور» للمخطَّط البياني. بنية المصفوفة بسيطة وواضحة. ننشئ مصفوفة تحتوي على صفوف وأعمدة بعدد العُقَد في الرسم البياني. ثم نضع العدد واحد لكل تقاطع يتطابق مع رابطٍ ما والعدد صفر لكل التقاطعات الأخرى. فيما يلي مصفوفة التجاور لمثالنا:

يمكننا أيضًا التعبير عن أهمية صفحات الويب باستخدام صف أو «متجه» واحد:

أمَا وقد دخلنا في الجوانب العملية لخوارزمية بيج رانك، سنبدأ في استخدام مصطلح ترتيب الصفحات للإشارة إلى أهمية صفحةٍ ما. سترى أن المصطلح سيكون له ما يبرِّره؛ إذ سنتمكَّن من اشتقاق ترتيب لكل الصفحات على الشبكة العنكبوتية بناءً على الأهمية. وبما أن الصف يحتوي على كل ترتيبات الصفحات، سنسميه «متجه ترتيب الصفحات» للمخطَّط البياني.

تُقسَّم أهمية صفحة الويب على الصفحات المرتبطة بها. وبما أن لدينا الآن مصفوفة التجاور، يمكننا تنفيذ تلك المهمة عن طريق الاتجاه إلى كل صف، وتقسيم كل قيمة في الصف على عدد القيم الموجودة في ذلك الصف. تلك الطريقة تعادل تقسيم صوت كل صفحة على عدد الروابط الخارجية التي تذكر تلك الصفحة. وإذا فعلنا ذلك، فسنحصل على المصفوفة التالية:

نطلِق على تلك المصفوفة اسم «مصفوفة الارتباطات التشعُّبية».

إذا أمعنا النظر في مصفوفة الارتباطات التشعُّبية، فسنجد كل عمود يوضِّح كيفية اشتقاق أهمية الصفحة من الصفحات المرتبطة بها. لنأخذ العمود الأول المتعلِّق بأهمية الصفحة رقم ١. تستمد هذه الصفحة أهميتها من الصفحتين رقم ٣ و٤. الصفحة رقم ٣ تعطي ثلثَ أهميتها الصفحةَ رقم ١ لأنها ترتبط بثلاث صفحات، والصفحة رقم ٤ تعطي نصف أهميتها الصفحةَ ١ لأنها ترتبط بصفحتين. لا تتلقى الصفحة رقم ١ أهمية من الصفحات الأخرى في التمثيل البياني لأن تلك الصفحات لا ترتبط بها. يمكننا التعبير عن ذلك بالمعادلة التالية:

ولكن هذا بالضبط هو تعريف ، وهو ترتيب الصفحة رقم ١. نحن نحصل على ترتيب الصفحة بجمع حواصل ضرب العناصر لمتجه ترتيب الصفحات ذي العناصر المتطابقة في العمود الأول من متجه الارتباطات التشعُّبية.

لنرَ ما يحدث إذا أخذنا متجهَ ترتيب الصفحات وجمعنا حواصل ضرب عناصره مع العناصر المقابلة له في العمود الثاني من مصفوفة الارتباطات التشعُّبية:

هذا بالضبط هو تعريف ، وهو ترتيب الصفحة رقم ٢. بالمثل، جمع حواصل ضرب العناصر لمتجه ترتيب الصفحات في محتويات العمود الثالث من مصفوفة الارتباطات التشعُّبية سيعطينا ، وهو ترتيب الصفحة رقم ٣:

يمكنك التحقُّق من أن استخدام العمودين الرابع والخامس في مصفوفة الارتباطات التشعُّبية سيعطيك و على التوالي. وهذه العملية — جمع حواصل ضرب العناصر في متجه ترتيب الصفحات مع محتويات كل عمود في مصفوفة الارتباطات التشعُّبية — هي في الحقيقة حاصل ضرب متجه ترتيب الصفحات في مصفوفة الارتباطات التشعُّبية.

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

لنفترض أننا نُعدُّ مخبوزات بيجل وكرواسون تُباع مقابل ٢٠٠ و١٥٠ دولارًا على التوالي. لدينا متجران؛ يبيع الأول ١٠ قطع بيجل و٢٠ قطعة كرواسون، ويبيع الثاني ١٥ قطعة بيجل و١٠ قطع كرواسون. كيف نوجد إجمالي المبيعات لكل متجر؟

لإيجاد إجمالي المبيعات من المتجر الأول، سنضرب سعر البيجل في عدد القطع المبيعة في ذلك المتجر، ونضرب سعر الكرواسون في عدد القطع المبيعة ثم نجمع الناتجين:

ونقوم بالعملية نفسها لإيجاد إجمالي مبيعات المتجر الثاني:

للتعبير عن هذه المعادلة بصورةٍ أكثرَ إيجازًا، نكتب أسعار البيجل والكرواسون في صورة متجه:

نكتب أيضًا المبيعات اليومية في صورة مصفوفة. ستحتوي المصفوفة على عمودين، عمود لكل متجر، وصفين، أحدهما للبيجل والآخر للكرواسون:

لإيجاد إجمالي المبيعات لكل متجر، نضرب عناصر المتجه في كل عمود من مصفوفة المبيعات ثم نجمع حواصل الضرب. تلك العملية تحدِّد حاصل ضرب المتجه في المصفوفة:

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

نعود إلى ترتيب الصفحات؛ في كل جولة، تعبِّر العملية الحسابية لمتجه ترتيب الصفحات في الحقيقة عن حاصل ضرب قيمة متجه ترتيب الصفحات في الجولة السابقة في مصفوفة الارتباطات التشعُّبية. ومع خوض الجولات، نحصل على تقديرات متعاقبة لترتيبات الصفحات؛ أي تقديرات تعاقبية لمتجه ترتيب الصفحات الذي يتكوَّن من تلك القيم. للحصول على تلك التقديرات المتعاقبة في متجه ترتيب الصفحات، لا نحتاج إلَّا إلى ضرب المتجه في كل جولة في مصفوفة الارتباطات التشعُّبية، ومِن ثَم نحصل على المتجه للجولة التالية.

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

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

في جولة التصويت الثالثة، نحصل على متجه ترتيب الصفحات الرابع:

وكما هو الحال في كل عملية تكرار، نضرب ناتج عملية التكرار السابقة في مصفوفة الارتباطات التشعُّبية، ونحصل في النهاية على سلسلة من حواصل ضرب التقديرات المتعاقبة لمتجه ترتيب الصفحات في مصفوفة الارتباطات التشعُّبية. وكما نرى، تلك العملية تكافئ ضرب متجه ترتيب الصفحات الأول في أسس متزايدة لمصفوفة الارتباطات التشعُّبية. يطلَق على عملية حساب التقديرات المتعاقبة هذه اسم «طريقة الأس». لذا نرى أن حساب ترتيبات الصفحات لمجموعة من صفحات الويب عبارة عن تطبيقٍ لطريقة الأس على متجه ترتيب الصفحات ومصفوفة الارتباطات التشعُّبية إلى أن يتوقَّف متجه ترتيب الصفحات الناتج عن التغيُّر، أو كما نقول، إلى أن «يتلاقى» مع قيمة ثابتة وهي المصفوفات النهائية لترتيبات الصفحات.

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

نموذج العُقَد المتدلية والتصفُّح العشوائي

ننتقل الآن إلى مثالٍ لتمثيل بياني أبسط حيث يتكوَّن من ثلاث عُقَد فقط:

نريد إيجاد ترتيبات الصفحات لهذه العُقَد الثلاث. نتَّبع الخوارزمية نفسها. نضع القيمة الأولية لمتجه ترتيب الصفحات ١ / ٣، بحيث تتساوى ترتيبات الصفحات بين كل العُقَد. ثم نضرب متجه ترتيب الصفحات في مصفوفة الارتباطات التشعُّبية كما يلي:

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

لا شك أن هذه مشكلة. فليس من المتوقَّع أن تكون أهمية جميع الصفحات هنا صفرًا. ففي النهاية، الصفحة رقم ٣ لها رابطان خلفيان، والصفحة رقم ٢ لها رابط خلفي واحد؛ ولذا توقَّعنا أن يظهر هذا بطريقةٍ ما في النتائج، فضلًا عن حقيقة أننا نريد أيضًا أن يساوي مجموع ترتيبات الصفحات واحدًا. أما هنا فلم نتوصَّل إلى وجود أهميةٍ لأي صفحة من الصفحات.

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

يُطلق على مثل هذه العُقَد «العُقَد المتدلية»؛ لأنها تتدلَّى من النهايات (المغلقة) للتمثيل البياني. لا شيء يمنع وجود مثل تلك الصفحات على الشبكة العنكبوتية. وعلى الرغم من أن صفحات الويب تحتوي عادةً على روابطَ واردة وصادرة، فقد تظهر صفحة ليس لها روابط صادرة وتعيث فسادًا مع طريقة الأُس التي ذكرناها لتونا.

للتغلُّب على المشكلة، نستعين باستعارة. نتخيَّل أن لدينا شخصًا يتصفَّح الشبكة العنكبوتية ويقفز من صفحة إلى أخرى. للانتقال من صفحة إلى أخرى، عادةً ما يتَّبع الزائر رابطًا ما. ولكن بعد ذلك يصل المتصفح إلى عقدة متدلية؛ أي صفحة ليس لها روابط إلى أي صفحة أخرى. لا نريد للمتصفِّح أن يبقى حبيسًا في تلك الصفحة ومِن ثَم نعطيه إمكانية القفز إلى أي صفحة أخرى، إلى أي مكانٍ على الشبكة العنكبوتية. الأمر أشبه بتصفح الشبكة العنكبوتية من صفحة إلى أخرى إلى أن نصل إلى طريق مسدود. وعندما يحدث ذلك، لا نستسلم ونتوقف. يمكننا دائمًا كتابة عنوان آخر في متصفح الويب وننتقل إلى أي صفحة ويب أخرى، حتى إن لم توجد لها روابط في الصفحة المتدلية. هذا ما نريد من المتصفِّح أن يفعله. عندما يضل وجهته، سيختار المتصفِّح صفحة — أي صفحة — على الشبكة العنكبوتية ويذهب إليها كي يستمر في التصفُّح. وهكذا يصبح المتصفِّح «متصفِّحًا عشوائيًّا» مزودًا بجهاز انتقال آنيٍّ يمكن أن يأخذه على الفور إلى أي مكان على شبكة الإنترنت.

لإسقاط تلك الاستعارة مرةً أخرى على ترتيب الصفحات، نفسِّر مصفوفة الارتباطات التشعُّبية بأنها تعطينا الاحتمالات بأن متصفِّحًا ما سيتَّبع رابطًا للانتقال إلى صفحةٍ بعينها. في مثال العُقَد الثلاث، يوضِّح الصف الأول من مصفوفة الارتباطات التشعُّبية أنه عندما يكون المتصفِّح في الصفحة رقم ١، ستتساوى احتمالات اختياره تصفُّح الصفحة رقم ٢ أو الصفحة رقم ٣. ويوضِّح الصف الثاني أنه عندما يكون المتصفِّح في الصفحة رقم ٢، فسيختار دومًا زيارة الصفحة رقم ٣. لنعُدْ إلى المثال الأول برهةً، إذا استقر المتصفِّح في الصفحة رقم ٥، فمن المحتمل أن ينتقل إلى الصفحة رقم ٢ أو ٣ أو ٤ لتكون احتمالية الزيارة ١ / ٣ لكلٍّ من تلك النتائج.

تعلن عقدة متدلية عن نفسها عندما يكون هناك صفٌّ مليء بالأصفار. عندئذٍ، لا توجد احتمالية أن ينتقل المتصفِّح إلى أي صفحة. وهنا يبرز تأثير المتصفِّح العشوائي. وكما ذكرنا، سيقفز ذلك المتصفح إلى أي صفحة في التمثيل البياني. وهذا يعني أننا في الواقع نغيِّر مصفوفة الارتباطات التشعُّبية بحيث لا تتبقى بها صفوف تحتوي على أصفار. وبما أننا نريد من المتصفِّح أن يقفز إلى أي صفحة ويب باحتمالية متساوية، سنكتب في الصف أو ١ / ٣ كما في المثال الذي معنا، بدلًا من الأصفار. وبذلك ستصبح المصفوفة بالشكل التالي:

الآن، يمكن للمتصفِّح الذي يستقر في الصفحة رقم ٣ الانتقال إلى أي صفحة في التمثيل البياني باحتمالية متساوية. بل يمكن أن يبقى المتصفِّح في الصفحة نفسها مؤقتًا، ولكن هذا لا يهم؛ لأن الزائر يمكن أن يعيد المحاولة مرارًا، وفي وقتٍ ما سيتم اختيار صفحة أخرى عشوائيًّا. نطلِق على تلك المصفوفة مصفوفة الارتباطات التشعُّبية المعدَّلة، حيث يمكننا تغيير صفوف الأصفار إلى قيمٍ تساوي ، في المصفوفة . إذا طبَّقنا طريقة الأُس باستخدام المصفوفة ، فستتطور ترتيبات الصفحات على النحو التالي:

في هذه المرة، تتلاقى الخوارزمية عند قيمٍ غير صفرية؛ ومِن ثَم لا يحدث أيُّ سحب للأهمية. كذلك تصبح النتائج منطقية. أعلى ترتيب صفحات حقَّقته الصفحة رقم ٣، برابطين خلفيين؛ ثم الصفحة رقم ٢ برابط خلفي واحد، ثم الصفحة رقم ١ التي لا يوجد لها أي روابط خلفية على الإطلاق.

مصفوفة جوجل

يبدو أننا حلَلنا الإشكالية، ولكن ثمَّة مشكلة مشابهة تطل برأسها في مواقفَ أعقد. لا يحتوي التمثيل البياني التالي على عُقَد متدلية:

إذا طبَّقنا الخوارزمية، فسنجد أن هناك عقدتين — الصفحة رقم ١ والصفحة رقم ٤ — تنتهيان بترتيب يساوي صفرًا:

ما حدث أنه على الرغم من عدم وجود عقدة متدلية، توجد مجموعة عُقَد تعمل بمثابة بالوعة لباقي التمثيل البياني. إذا دقَّقت النظر في التمثيل البياني، فسترى أن العُقَد ٢ و٣ و٥ و٦، باعتبارها مجموعةً واحدة، لا تحتوي إلا على روابط واردة. يمكن الانتقال من العقدة ١ أو العقدة ٤ إلى هذه المجموعة، ولكن بمجرد الدخول إلى المجموعة، لا يمكننا سوى التنقُّل بداخلها. فلا يمكننا الخروج منها. وهكذا سيصبح المتصفح العشوائي أسيرًا، ليس داخل صفحة ويب واحدة هذه المرة، بل داخل مجموعة صفحات لا ترتبط إلا معًا.

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

في الوقت الحالي، عندما يستقر المتصفح عند عقدةٍ ما، تكون التحركات المحتملة هي المشار إليها في المصفوفة . في المثال الأخير، المصفوفة هي نفسها مصفوفة الارتباطات التشعُّبية نظرًا لعدم وجود صفوف صفرية:

إذا استقر المتصفِّح العشوائي في الصفحة ٥، فستكون التحركات المحتملة إلى الصفحات ٢ أو ٣ أو ٦، باحتمالية تساوي ١ / ٣ لجميع الصفحات كما تشير المصفوفة . سنجعل المتصفح العشوائي أكثر نشاطًا بحيث يتمكَّن من التحرُّك تبعًا للمصفوفة ، «ليس دائمًا»، ولكن باحتمالية قدرها سنختارها؛ ومِن ثَم بالنسبة إلى الاحتمالية ، سيقفز المتصفِّح العشوائي إلى أي صفحة في التمثيل البياني من دون التقيد بالمصفوفة .

القدرة على التنقُّل من أي مكان إلى أي مكان في التمثيل البياني تعني أنه لا يمكن أن توجد قيم صفرية في المصفوفة على الإطلاق؛ لأن وجود مدخل صفري يشير إلى حركة لم تتم. ولتحقيق ما نريد، سنحتاج إلى «زيادة» المدخلات الصفرية في صف بقيمة ما و«تقليل» المدخلات غير الصفرية بحيث يكون مجموع الصف كاملًا هو العدد واحد دومًا. يمكن حساب القيم النهائية في المصفوفة عن طريق الجبر الخطي بناءً على المصفوفة والاحتمالية . وتسمَّى المصفوفة الجديدة التي سنخرج بها «مصفوفة جوجل»، ونستخدم الرمز للتعبير عنها. إذا تحدَّد سلوك المتصفِّح العشوائي وفقًا لمصفوفة جوجل، فسنخرج بالنتيجة التي نريدها: سيبدو المتصفِّح العشوائي كأنه يتبع المصفوفة باحتمالية قيمتها وينتقل بحرية بالاحتمالية . في المثال الذي معنا، تصبح مصفوفة جوجل بالشكل التالي:

قارن تلك المصفوفة بالمصفوفة . لاحظ أنه في الصف الأول، كان لدينا مدخلان بقيمة ١ / ٢ وباقي المدخلات صفر. أما في مصفوفة جوجل، فتحوَّل المدخلان ١ / ٢ إلى ٥٤ / ١٢٠، وتحوَّلت باقي المدخلات من ٠ إلى ٣ / ١٢٠. وحدثت تغيُّرات مشابهة في الصفوف الأخرى. إذن، إذا استقر الزائر العشوائي في الصفحة رقم ١، تصبح التحرُّكات الممكنة إلى الصفحتين رقم ٢ و٥ باحتمالية ٥٤ / ١٢٠ لأي منهما، أو إلى أي صفحة أخرى باحتمالية ٣ / ١٢٠ لكل صفحة منها.

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

إنها طريقة رائعة؛ إذ لم يَعُد لدينا ترتيبات صفحات صفرية.

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

تطبيق خوارزمية بيج رانك عمليًّا

بعد إثبات أن لدينا طريقة لإيجاد ترتيب الصفحات في أي تمثيل بياني، يظل السؤال عمَّا إذا كانت النتائج في النهاية ستكون منطقية أم لا قائمًا.

يعتبر متجه ترتيب الصفحات — حسب التعريف الذي وضعناه له — متجهًا خاصًّا بالنسبة إلى مصفوفة جوجل. عندما تنهي طريقة الأس عملها، لا يتغير متجه ترتيب الصفحات بعد ذلك. ولذلك إذا ضربنا مصفوفة جوجل في متجه ترتيب الصفحات، فسنحصل ببساطة على متجه ترتيب الصفحات نفسه. في الجبر الخطي، يسمَّى هذا المتجه «المتجه الذاتي الأول» لمصفوفة جوجل. من دون التعمُّق في الرياضيات، تدعم النظرية الأساسية التي تشكِّل هذا المتجه فكرة أنه يحظى بأهمية خاصة بالنسبة إلى المصفوفة.

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

ثمَّة ميزة أخرى لخوارزمية بيج رانك وهي فاعلية تنفيذها. إن مصفوفة جوجل ضخمة؛ ونحن نريد صفًّا واحدًا وعمودًا واحدًا لكل صفحة على الشبكة العنكبوتية. ولكن مصفوفة جوجل، كما رأينا، مشتقة من المصفوفة المشتقة بدورها من مصفوفة الارتباطات التشعُّبية. نحن لا نحتاج حقًّا إلى إنشاء مصفوفة جوجل نفسها وتخزينها؛ فبوسعنا إنشاؤها ديناميكيًّا باستخدام العمليات المصفوفية في مصفوفة الارتباطات التشعُّبية. وهذا أمر مريح وفي المتناول. وعلى النقيض من مصفوفة جوجل التي لا تحتوي على أي أصفار في أي مكان، تحتوي مصفوفة الارتباطات التشعُّبية على العديد والعديد من الأصفار. قد تتضمَّن الشبكة العنكبوتية مليارات الصفحات، ولكن كل صفحة لا ترتبط إلا بعدد محدود من صفحات الويب الأخرى. مصفوفة الارتباطات التشعُّبية هي ما نطلق عليه «مصفوفة متفرقة»؛ أي مصفوفة شبه مليئة بالأصفار ولا تحتوي إلا على عدد محدود من المدخلات غير الصفرية، وهي قيم أسية أقل من المدخلات الصفرية. ومِن ثَم يمكننا تخزين المصفوفة باستخدام أساليب ذكية بحيث لا تخزن سوى المواضع التي تظهر فيها المدخلات غير الصفرية بدلًا من الاحتياج إلى شريحة كبيرة من الذاكرة لملء معظمها بالأصفار وملء قدْر قليل منها بالمدخلات غير الصفرية. وبدلًا من تخزين مصفوفة الارتباطات التشعُّبية بأكملها، لا نحتاج إلا إلى تخزين إحداثيات المدخلات غير الصفرية التي لن تتطلب سوى جزء صغير جدًّا من مساحة التخزين. وهذا يمنحنا ميزة كبيرة في التطبيقات العملية لخوارزمية بيج رانك.

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