חיפוש ו־PageRank.

יותר מדי תשובות

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

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

קישורים כהצבעה

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

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

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

חזרה לניסוי ↑

הגולש האקראי

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

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

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

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

חזרה לניסוי ↑

למה הגולש קופץ לפעמים

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

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

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

חזרה לניסוי ↑

מחשבים את הדירוג

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

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

כאן $N$⁠ הוא מספר הדפים, $d$⁠ הוא מקדם השיכוך, והסכום עובר על כל דף $q$⁠ שמקשר אל $p$⁠, וכל אחד מהם מעביר הלאה את הדירוג שלו חלקי $L(q)$⁠, מספר הקישורים היוצאים ממנו. עובי כל קישור בסצנה הוא החלק הזה, $d \cdot \mathrm{PR}(q) / L(q)$⁠.

מתמרנים את הדירוגים

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

מה המודל הזה משאיר בחוץ

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

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