דירוג דפים.

שלב 1 מתוך 6

הגולש האקראי

ברשת שמונה דפים, וכל חץ הוא קישור מדף לדף. כשמחפשים משהו, מנוע חיפוש מוצא מיליוני דפים מתאימים, ועליו להחליט מי ראשון. הרעיון של PageRank, שעליו נבנה גוגל, הוא להסתכל על הקישורים כגרף מכוון ולדמיין גולש אקראי: בכל צעד הוא לוחץ על אחד הקישורים של הדף שבו הוא נמצא, באקראי, או, לפעמים, קופץ לדף אקראי כלשהו. ה־PageRank של דף הוא החלק מהזמן שהגולש מבלה בו בטווח הארוך. גובה הבסיס של כל דף הוא הדירוג שלו.

עכשיו הסיכוי ללחוץ על קישור הוא 0%: הגולש רק קופץ. נבאו מה יקרה כשהוא יתחיל ללחוץ.

שלב 2 מתוך 6

קישורים שקטים

אף דף לא מקשר לדף שלכם, ולכן הגולש מגיע אליו רק בקפיצות. כמה ירוויח הדף מקישורים?

שלב 3 מתוך 6

קישור מהפורטל

כל דף מחלק את הדירוג שלו בין הקישורים שהוא נותן. לכן מה שקובע הוא לא כמה קישורים מגיעים לדף, אלא מאיפה: הנוסחה היא

$PR(p) = \frac{1 - d}{N} + d \sum_{q \to p} \frac{PR(q)}{L(q)}$$PR(p) =$$\frac{1 - d}{N} + d \sum_{q \to p} \frac{PR(q)}{L(q)}$⁠

כש־$d$⁠ הוא הסיכוי ללחוץ על קישור, $N = 8$⁠ מספר הדפים, ו־$L(q)$⁠ מספר הקישורים שדף $q$⁠ נותן. הדירוג של דף תלוי בדירוגים של הדפים שמקשרים אליו, שתלויים בדירוגים של הדפים שמקשרים אליהם, וכן הלאה.

שלב 4 מתוך 6

לטפס

הקישורים לדף שלכם נוספים בסדר קבוע: שלושה דפים שקטים, אחר כך הפורטל, ואחר כך אתר החדשות. טפסו בדירוג.

שלב 5 מתוך 6

מה קישור מעביר

הנוסחה נקראת מימין לשמאל: דף $q$⁠ מעביר דרך כל קישור שלו את החלק $\dfrac{d \cdot PR(q)}{L(q)}$⁠. ה־$\dfrac{1-d}{N}$⁠ שבהתחלה הוא הקפיצות האקראיות, שנותנות לכל דף מעט, גם לדף שאיש לא מקשר אליו.

שלב 6 מתוך 6

הגולש מתייצב

איך מחשבים את הדירוגים, אם כל אחד תלוי באחרים? אפשר פשוט לתת לגולש ללכת, ולספור. מבט פנימה מכניס את הגולש, ולצד כל בסיס עמודה של החלק מהביקורים שנחתו בדף. עד עכשיו הוא עשה רק כמה עשרות קליקים.