كیف یعمل محرك غوغل Google: سلاسل ماركوف Markov والقیم الذاتیة

الكاتبة الأصلية: كريستيان روسو Christiane Rousseau
ترجمة : أسماء تراوش

منذ أولى بداياته، كان غوغل Google محرك البحث الوحيد تقريبا. هذا راجع لسيطرة خوارزميته المعروفة باسم “ترتيب بيج Page” PageRank¹. بالفعل، فبهذا الكم الهائل من الصفحات على الشبكة العنكبوتية العالمية (World Wide Web، أي الإنترنت)، ستحصل العديد من البحوث على آلاف أو ملايين النتائج. وإذا كانت هذه النتائج سيئة الترتيب فستكون بدون جدوى لأن لا أحد يستطيع التعرف على ملايين المداخل.

كيف تشتغل خوارزمية PageRank ؟

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

http://www.mathunion.org/icmi/other-activities/klein-project/introduction/

بدلاً من

http://www.kleinproject.org/

العنوان الشبكاتي الأول هو عنوان صفحة، توجد في موقع الاتحاد العالمي للرياضيات IMU²: http://www.mathunion.org. نظرًا لأهمية هذا الاتحاد فسيظهر موقعه الرسمي أولاً عند إجراء بحث تحت عبارة “الاتحاد العالمي للرياضيات”. وفضلا عن ذلك فهو يمدّ بجزء من محتواه إلى جميع الصفحات المكوِنة له، ومنها :

http://www.mathunion.org/icmi/other-activities/klein-project/introduction/.

يمكن التنبؤ بأنه بعد أشهر أو سنوات قليلة فإن أول صفحة ستظهر عند البحث عن مشروع كلاين ستكون

http://www.kleinproject.org/.

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

مثال بسيط:

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

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

أين سنكون بعد $n$ خطوة؟

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

$P=\left(\begin{matrix} 0 & \frac12 & \frac13 & 1 & 0 \\ 1 & 0 & \frac13 & 0 & \frac13 \\ 0 & \frac12 & 0 & 0 & \frac13 \\ 0 & 0 & 0 & 0 & \frac13 \\ 0 & 0 & \frac13 & 0 & 0 \end{matrix}\right)$

بالنظر إلى المصفوفة $P$ نلاحظ أن مجموع عناصر كل عمود منها يساوي 1، وأن جميع مركباتها موجبة أو معدومة. إن المصفوفات التي تتمتع بهاتين الخاصيتين تعتبر من نوع خاص: فكل واحدة منها هي مصفوفة من سيرورة سلسلة ماركوف Markov chain process، وتدعى أيضا مصفوفة انتقال سلسلة ماركوف Markov transition matrix. في هذه المصفوفات يكون 1 دوما قيمة ذاتية لها فينتج عن ذلك وجود شعاع ذاتي قيمته الذاتية 1 ومركباته محصورة بين 0 و 1 ومجموعها يساوي 1. قبل التذكير بتعريف كل من القيم الذاتية والأشعة الذاتية، دعنا نكتشف سويًا الفائدة من التمثيل المصفوفي لمخطط بياني.

لنعتبر متغيرا عشوائيا $X_n$ يأخذ قيمه في مجموعة الصفحات {أ، ب، ج، د، ه} المُكوَنة من $N$ صفحة (هنا $N=5$ ). يمثل $X_n$ الصفحة التي نكون فيها بعد $n$ خطوة عشوائية. لنرمز بـ $P_{ij}$ للمركبة الواقعة في تقاطع السطر $i$ مع العمود $j$ من المصفوفة $P$ . يمثل $P_{ij}$ الاحتمال الشرطي أن نكون موجدين في الصفحة $i$ في المرحلة $n+1$ علما أننا كنا في الصفحة $j$ في المرحلة التي تسبقها:

$P_{ij}=\text{Prob}(X_{n+1}=i / X_n=j).$

نلاحظ أن هذا الاحتمال مستقل عن $n$ ! عندها نقول إن سلسلة ماركوف ليست لها ذكريات من الماضي. وهو ما يجعل من السهل التصور بأنه بعد مرحلتين ستُختصر الاحتمالات الممكنة في المصفوفة $P^2$ .

لنبرهن على ذلك (يمكنكم تجاوز البرهان إن شئتم). باستعمال المبرهنة العامة للاحتمالات يأتي

$\text{Prob}(X_{n+2}=i / X_n=j)=\sum_{k=1}^N \text{Prob}(X_{n+2}=i \wedge X_{n+1}=k / X_n=j).$

ومن تعريف الاحتمال الشرطي نستنتج

$\text{Prob}(X_{n+2}=i / X_n=j)=\sum_{k=1}^N \frac{\text{Prob}(X_{n+2}=i \wedge X_{n+1}=k \wedge X_n=j)}{\text{Prob}(X_n=j)}$

نستعمل الآن حيلة مألوفة: نضرب ونقسم على نفس الكمية:

$\text{Prob}(X_{n+2}=i / X_n=j)=\sum_{k=1}^N \frac{\text{Prob}(X_{n+2}=i \wedge X_{n+1}=k \wedge X_n=j)}{\text{Prob}(X_{n+1}=k \wedge X_n=j)} \, \frac{\text{Prob}(X_{n+1}=k \wedge X_n=j)}{\text{Prob}(X_n=j)}$

فيكون حاصل القسمة الأول يساوي

$\text{Prob}(X_{n+2}=i / X_{n+1}=k \wedge X_n=j)=\text{Prob}(X_{n+2}=i / X_{n+1}=k)$

لأن سيرورة سلسلة ماركوف لا تحمل ذكريات من الماضي. لذا

$<span class="ql-right-eqno"> </span><span class="ql-left-eqno"> </span><img src="https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-75b3f98bfb38fb3dcb17b9b46877bb21_l3.png" height="145" width="639" class="ql-img-displayed-equation " alt="\begin{align*}\text{Prob}(X_{n+2}=i / X_n=j) &= \sum_{k=1}^N \text{Prob}(X_{n+2}=i / X_{n+1}=k) \, \text{Prob}(X_{n+1}=k / X_n=j) \\ &= \sum_{k=1}^N p_{ik}p_{kj} \\ &= (P^2)_{ij}. \end{align*}" title="Rendered by QuickLaTeX.com"/>$

بالعودة لمثالنا، نجد

$P^2=\left(\begin{matrix} \frac12 & \frac16 & \frac16 & 0 & \frac{11}{18} \\ 0 & \frac23 & \frac49 & 1 & \frac19 \\ \frac12 & 0 & \frac{5}{18} & 0 & \frac16 \\ 0 & 0 & \frac19 & 0 & 0 \\ 0 & \frac16 & 0 & 0 & \frac19 \end{matrix}\right)$

من الواضح، أنه بتكرار العملية السابقة فإن العنصر $(P^m)_{ij}$ من المصفوفة $P^m$ هو الاحتمال $\text{Prob}(X_{n+m}=i / X_n=j)$ . فنجد مثلا أن

$P^{32}=\left(\begin{matrix} 0.293 & 0.293 & 0.293 & 0.293 & 0.293 \\ 0.390 & 0.390 & 0.390 & 0.390 & 0.390 \\ 0.220 & 0.220 & 0.220 & 0.220 & 0.220 \\ 0.024 & 0.024 & 0.024 & 0.024 & 0.024 \\ 0.073 & 0.073 & 0.073 & 0.073 & 0.073 \end{matrix}\right)$

بتدوير النتائج بدقة تقدر بجزء من الألف ستكون جميع أعمدة المصفوفة متطابقة. وينسحب هذا على أعمدة المصفوفة $P^n$ لما $n>32$ ، التي تتميز أيضا باستقرار نتائجها، لكن باختيار هذه المرة دقة أكبر. وهكذا من أجل $n$ خطوة، حيث $n$ كبير بقدر كاف، فإن احتمال أن تكون في صفحة معينة مستقل عن نقطة البداية !

علاوة على ذلك، إذا اعتبرنا الشعاع

$\pi^t=(0.293, 0.390, 0.220, 0.024, 0.073)$

( $\pi$ هو شعاع عمودي منقوله الشعاع الأفقي $\pi^t$ ) فمن السهل التأكد من أن $P\pi=\pi$ . إذا كانت المركبة ذات الرتبة $i$ من الشعاع $\pi^t$ هي احتمال أن تكون في صفحة $i$ في لحظة معينة $n$ ، يترتب عن ذلك أن $\pi^t$ هو قانون احتمال للصفحات في اللحظة $n$ ، وهو أيضا قانون الاحتمال في اللحظة $n+1$ . لهذا السبب، فالشعاع $\pi$ يسمى القانون الاستقراري. ذلك أنه يسمح بترتيب الصفحات. في مثالنا، تُرَتب الصفحات بالشكل التالي ب، أ، ج، ه، د، ونقول إن ب تمثل الصفحة الأكثر أهمية.

الحالة العامة

نعالج الحالة العامة تمامًا كما في المثال السابق. تُجسَد الشبكة بمخطط بياني تعبر فيه $N$ قمة عن $N$ صفحة، وتدل الأسهم على الروابط بين الصفحات. ثم نختصر المخطط في مصفوفة $P$ بُعدها $N\times N$ ، حيث العمود $j$ يمثل الصفحة رقم $j$ من صفحات الانطلاق والسطر $i$ الصفحة رقم $i$ من الوصول. في مثالنا السابق عثرنا على شعاع يحقق $P\pi=\pi$ . هذا الشعاع هو شعاع ذاتي للقيمة الذاتية 1. لنتذكر معًا تعريف كل من القيمة الذاتية والشعاع الذاتي.

تعريف. لتكن $P$ مصفوفة بعدها $N\times N$ . يكون $\lambda\in\mathbb{C}$ قيمة ذاتية لـ $P$ إذا وجد شعاع غير معدوم $X\in\mathbb{C}^N$ يحقق $PX=\lambda X$ . عندئذ نسمي $X$ شعاعا ذاتيا لـ $P$ المرفق بالقيمة الذاتية $\lambda$ .

لنتذكر أيضا طريقة إيجاد القيم الذاتية والأشعة الذاتية.

قضية. لتكن $P$ مصفوفة بُعدها $N\times N$ . القيم الذاتية لـ $P$ هي جذور كثير الحدود المميز $\det(\lambda I-P)=0$ ، حيث $I$ هي المصفوفة المطابقة $N\times N$ . الأشعة الذاتية للقيمة الذاتية $\lambda$ هي الجذور غير المعدومة للجملة الخطية المتجانسة $(\lambda I-P)X=0$ .

المبرهنة الموالية التي تنسب لـ بيرون Perron و فروبينيوس Frobenius، نتيجة عميقة تنص على أن المصفوفة المرفقة لمخطط بياني تقبل دوما حلا مستقرا.

مبرهنة (بيرون- فروبينيوس). نعتبر مصفوفة انتقال سلسلة ماركوف $P=(p_{ij})$ بُعدها $N\times N$ (أي $p_{ij}\in[0,1]$ مهما يكن $i$ و $j$ ، ومجموع مركبات كل عمود يساوي 1، بمعنى $\sum_{i=1}^N p_{ij}=1$ ). عندئذ

$\lambda=1$ قيمة ذاتية لـ $P$ .
كل قيمة ذاتية لـ $P$ تحقق $|\lambda|\leq 1$ .
يوجد شعاع ذاتي $\pi$ من أجل القيمة الذاتية 1، مركباته أكبر أو تساوي الصفر. وبدون أن نمس بعمومية المسألة يمكن افتراض أن مجموع هذه المركبات يساوي 1.

حان الوقت الآن للتأمل في قوة هذه المبرهنة. من أجل ذلك نفترض قصد الاختصار أن المصفوفة $P$ تقبل أساسا من الأشعة الذاتية $B=\{v_1,\dots,v_n\}$ حيث $v_1$ هو الشعاع $\pi$ الموجود في نظرية بيرون- فروبينيوس. عندئذ من أجل كل $v_i$ ، يوجد $\lambda_i$ يحقق $Pv_i=\lambda_iv_i$ ، ثم باختيار كيفي لشعاع غير معدوم $X$ منقوله $X^t=(x_1,\dots,x_n)$ بحيث $x_i\in[0,1]$ و $\sum_{i=1}^N x_i=1$ . نستطيع تفكيك $X$ في الأساس $B$ :

$X=\sum_{i=1}^N a_iv_i.$

يمكن إثبات أن $a_1=1$ لكن سنتخطى هذه المرحلة لنقوم بعدها بحساب

$PX=\sum_{i=1}^N a_iPv_i=\sum_{i=1}^N a_i\lambda_iv_i$

وذلك لأن $v_i$ شعاع ذاتي للقيمة الذاتية $\lambda_i$ . إذا أعدنا هذه العملية مرات عديدة نحصل على

$P^nX=\sum_{i=1}^N a_i\lambda_i^nv_i.$

من جهة أخرى، إذا كانت $|\lambda| < 1$ من أجل كل $\lambda_i$ حيث $i>1$ فإن

$\lim_{n\to\infty} P^nX=a_1v_1=\pi$

وهذا ما حدث بالضبط في المثال السابق!

نلاحظ رغم ذلك أن المبرهنة لا تضمن تمتع كل مصفوفة $P$ تحقق فرضية المبرهنة بالخاصية $\lim_{n\to\infty} P^nX=a_1v_1=\pi$ . دعنا نصف العلل الممكنة وطريقة علاجها.

العلل الممكنة

القيمة الذاتية 1 يمكن أن تكون جذرا مضاعفا لكثير الحدود المميز $\det(\lambda I-A)=0$ .
يمكن أن تكون للمصفوفة $P$ قيم ذاتية مختلفة عن 1، لكنها تحقق $|\lambda|=1$ .

فما العمل في هاتين الحالتين؟

عندما تكون مصفوفة انتقال ماركوف دون عِلة تسمى نظامية. بمعنى

تعريف. تكون مصفوفة سلسلة ماركوف نظامية إذا كانت

القيمة الذاتية 1 جذرا بسيطا لكثير الحدود المميز $\det(\lambda I-A)=0$ .
كل قيمة ذاتية لـ $P$ مختلفة عن 1 قيمتها المطلقة أقل تماما من 1.

نلاحظ أن أغلبية المصفوفات $P$ نظامية. إذا كان الأمر عكس ذلك، فالإستراتيجية المتبعة تقوم على تغيير تدريجي لهذه المصفوفات حتى تصبح نظامية.

العلاج

لتكن المصفوفة $Q=(q_{ij})$ ذات البعد $N\times N$ ، حيث $q_{ij}=\frac{1}{N}$ مهما يكن $i$ و $j$ . نستبدل المصفوفة $P$ من الشبكة بالمصفوفة التالية

$P_\beta=(1-\beta)P+\beta Q \qquad (1)$

من أجل $\beta$ صغير ينتمي للمجال $[0,1]$ (يستعمل غوغل قيمة لـ $\beta$ مساوية لـ 0.15). نلاحظ أن مركبات المصفوفة $P_\beta$ موجبة أو منعدمة وأن مجموعها في كل عمود يساوي 1، فهي بذلك مصفوفة سلسلة ماركوف. المبرهنة التالية تضمن لنا وجود $\beta$ صغير من أجله تختفي كل العلل.

مبرهنة. من أجل $P$ مصفوفة انتقال سلسلة ماركوف معطاة، يوجد دوما $\beta\geq 0$ ، صغير بالقدر الذي نريد، بحيث تكون المصفوفة $P_\beta$ نظامية.

ليكن $\pi$ الشعاع الذاتي لـ $P_\beta$ المرافق للقيمة الذاتية 1 الذي نُجَانسه بشكل يصبح فيه مجموع مركباته يساوي 1.

فيما يخص المصفوفة $P_\beta$ ، فمن أجل كل شعاع كيفي غير معدوم $X$ ، حيث $X^t=(p_1,\dots,p_N)$ مع $p_i\in[0,1]$ و $\sum_{i=1}^N p_i=1$ ، يكون

$\lim_{n\to\infty}(P_\beta)^nX=\pi \qquad (2)$

العلاقة مع مبرهنة النقطة الصامدة لبناخ

المبرهنة أسفله هي حالة خاصة من مبرهنة النقطة الصامدة لبناخ Banach التي عالجناها في مقالة قصيرة أخرى. يمكنك تجاوز هذا الجزء إن لم تتطلِع عليها بعد. لدينا

مبرهنة. لتكن $P$ مصفوفة انتقال سلسلة ماركوف. نعتبر $S=\left\{X / X^t=(p_1,\dots,p_N), p_i\in[0,1], \sum_{i=1}^N p_i=1\right\}$ ، بمسافة $d(X,Y)$ مناسبة بين النقاط (هذه المسافة تتعلق بـ $P$ ). نعرف على $S$ التطبيق الخطي $L:S\to S$ بالشكل التالي $L(X)=PX$ . إن $L$ تقلص على $S$ ، أي : يوجد $c\in[0,1[$ بحيث من أجل كل $X,Y\in S$ يكون

$d(L(X),L(Y))\leq c\,d(X,Y).$

وبالتالي يوجد شعاع وحيد $\pi\in S$ يحقق $L(\pi)=\pi$ .

وفضلا عن هذا، فمهما يكن $X_0\in S$ ، نستطيع أن نعرف المتتالية $\{X_n\}$ بالعلاقة التراجعية $X_{n+1}=L(X_n)$ . ومنه، $\lim_{n\to\infty} X_n=\pi$ .

تعريف المسافة $d$ . تعريف المسافة $d$ يتضمن بعض التعقيد ويمكن تجاوزه. ندرجه فقط قصد الإلمام بجميع جوانب الموضوع ووجهناه للقراء الراغبين في الاستزادة. فيما سيأتي، سنتقيد بالحالة التي يمكن فيها ردّ المصفوفة إلى مصفوفة قطرية. ليكن $B=\{v_1=\pi, v_2,\dots,v_N\}$ أساسا من الأشعة الذاتية. عندئذ يمكن كتابة الشعاعين $X,Y\in S$ وفق الأساس $B$ :

$X=\sum_{i=1}^N a_iv_i, \quad Y=\sum_{i=1}^N b_iv_i$

حيث $a_i,b_i\in\mathbb{C}$ . نعرّف بعد ذلك المسافة $d$

$d(X,Y)=\sum_{i=1}^n |a_i-b_i|.$

عند تزويد $S$ بهذه المسافة يصبح فضاءً متريا تاما، أي أن جميع متتالياته الكوشية متقاربة.

هذه المبرهنة لا تضمن فقط وجود $\pi$ ، بل تضمن أكثر من ذلك، فهي تمدنا بطريقة إنشائه، باعتباره نهاية للمتتالية $\{X_n\}$ . لقد أوضحنا هذا التقارب من خلال مثالنا السابق. العمود $j$ من $P^n$ هو الشعاع $P^ne_j$ حيث $e_j^t=(0,\dots,0,1,0,\dots,0)$ هو الشعاع ذو الرتبة $j$ من الأساس القانوني. بالتأكيد، كان بالإمكان أن نجد مباشرة الشعاع $\pi$ عن طريق حل الجملة $(I-P)X=0$ المرفقة للمصفوفة

$I-P=\left(\begin{matrix} 1 & -\frac12 & -\frac13 & -1 & 0 \\ -1 & 1 & -\frac13 & 0 & -\frac13 \\ 0 & -\frac12 & 1 & 0 & -\frac13 \\ 0 & 0 & 0 & 1 & -\frac13 \\ 0 & 0 & -\frac13 & 0 & 1 \end{matrix}\right)$

وعندئذ يمكن التوصل إلى أن جميع الحلول تكتب من الشكل $\left(4s, \frac{16}{3}s, 3s, \frac{1}{3}s, s\right)^t$ حيث $s\in\mathbb{R}$ .

أما الحل الذي يكون مجموع مركباته يساوي 1 فهو $\pi$ ، حيث

$\pi^t=\left(\frac{12}{41}, \frac{16}{41}, \frac{9}{41}, \frac{1}{41}, \frac{3}{41}\right).$

حساب عملي للقانون الاستقراري

لقد قدمنا الفكرة البسيطة التي تقف وراء الخوارزمية. ومع ذلك، فإن إيجاد القانون الاستقراري $\pi$ ، أي إيجاد الشعاع الذاتي للقيمة الذاتية 1 للمصفوفة $P_\beta$ الموضحة في (1) ليس مهمة سهلة عندما تكون للمصفوفة ملايين الأسطر والأعمدة: فالوقت اللازم لإجراء الحسابات وكذا سعة الذاكرة الضرورية لهذا الغرض يشكلان تحديا حقيقيا. مما يجعل استعمال طريقة حذف غوص Gauss أمرا غير مجد في هذه الحالة، بسبب حجم الحسابات، وحاجة الطريقة إلى التقسيم على معاملات صغيرة. توجد طريقة أكثر فعالية تستعمل الخاصية (2) (أنظر [LM] في المراجع). ومن ثَمّ تتجلى العلاقة مع المقالة القصيرة حول مبرهنة النقطة الصامدة لبناخ Banach التي تبيّن أن برهانها يزودنا بخوارزمية تسمح بإنشاء النقطة الصامدة.

بالفعل، فنحن ننطلق من $X_0$ حيث

$X_0^t=\left(\frac{1}{N}, \frac{1}{N}, \dots, \frac{1}{N}\right)$

وعلينا حساب $\lim_{n\to\infty}(P_\beta)^nX_0$ . عادة ما يعطينا $(P_\beta)^nX_0$ تقريبا جيدا لـ $\pi$ ، وهذا من أجل عدد $n$ محصور بين 50 و 100. استقراءً، نقوم بحساب $X_{n+1}=P_\beta X_n$ علمًا أن هذا النوع من الحسابات يستغرق وقتا طويلا. ذلك أنه استنادا إلى طريقة إنشائها فلن تكون للمصفوفة $P_\beta$ الواردة في (1) أية مركبة معدومة. ومن جهة أخرى، فمعظم مركبات المصفوفة $P$ منعدمة. لذا وجب علينا تفكيك الحساب للاستفادة من هذه الخاصية فنكتب :

$X_{n+1}=(1-\beta)PX_n+\beta QX_n.$

بفضل الشكل الخاص لـ $Q$ ، فمن السهل التحقق من أنه إذا كان $X$ شعاعا مجموع مركباته يساوي 1 فإن $QX=X_0$ . وبالتالي يكفي حساب المتتالية

$X_{n+1}=(1-\beta)PX_n+\beta X_0.$

خلاصة

لقد قدمنا الجزء العام من خوارزمية “ترتيب بيج” PageRank لـمحرك غوغل. ومن هنا يمكنكم تجربتها على شبكات بسيطة، وإيجاد الحيل السامحة بتحسين رتبة صفحتكم الشخصية، وذلك عن طريق إضافةٍ مثاليةٍ لروابط داخلية وخارجية. هناك أجزاء خاصة أخرى أكثر تعقيدا يتم تطويرها باستمرار، منها تلك التي تقوم على تعويض المصفوفة ‘المحايدة” $Q$ الواردة في (1) بمصفوفات تعكس ذوق المتصفح للشبكة. وهناك مساعٍ أخرى ترمي إلى جعل الترتيب غير مرتبط كثيرا بالجهود التي يقوم بها أولئك الذين يحاولون تحسين ترتيب صفحاتهم.

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

المراجع

[E] M. Eisermann, Comment Google classe les pages webb, http://images.math.cnrs.fr/Comment-Google-classe-les-pages.html , 2009.

[LM] A. N. Langville et C. D. Meyer, A Survey of Eigenvector Methods for Web Information Retrieval, SIAM Review, Volume 47, Issue 1, (2005), pp. 135–161.

[RS] C. Rousseau et Y. Saint-Aubin, Mathématiques etTechnologie, SUMAT Series, Springer-Verlag, 2008.

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

² International Mathematical Union جمعية دولية ظهرت لأول مرة سنة 1919، ثم أعيد إنشاؤها سنة 1945. تجمع 65 جمعية عالمية ووطنية، وتنظم مؤتمرا كل أربع سنوات.

PDF

كیف یعمل محرك غوغل Google: سلاسل ماركوف Markov والقیم الذاتیة

Related

اترك ردّاًإلغاء الرد

شارك هذا الموضوع:

Related

اترك ردّاًإلغاء الرد