דף הבית PR|גוגל| החיפוש של גוגל|אלגוריתם דירוג גוגל|דירוג גוגל|אינדקס גוגל|אלגוריתם ציון של גוגל
לדף הבית פרופיל החברה פטרונות לקוחות פורטפוליו צור קשר

אלגוריתם PageRank


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

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

כאשר:

  • PR(A) הוא PageRank לדף A,
  • PR(Ti) הוא PageRank לדפים Ti המקשרים לדף A,
  • C(Ti) הוא מספר הקישורים היוצאים בדף Ti, וכן
  • D הוא גורם הצמצום אותו ניתן להגדיר בין 0 ל-1.


  • אם כן, ראשית אנו רואים כי PageRank אינה מדרגת אתרי אינטרנט כיחידה כוללות, אלא שהדירוג נקבע לכל דף בנפרד. יתרה מכך, PageRank לדף A מוגדר באופן רקורסיבי על ידי ה-PageRank של הדפים המקשרים לדף A.
    ה-PageRank של דפי Ti המקשרים לדף A אינו משפיע באופן אחיד על ה-PageRank של דף A. במסגרת אלגוריתם PageRank, ה-PageRank של דף T משוקלל תמיד על ידי מספר הקישורים היוצאים C(T) בדף T. המשמעות היא ככל שיש יותר קישורים יוצאים בדף T, כך תהיה לדף A פחות תועלת מקישור אליו בדף T.
    לאחר מכן, מחברים את ה-PageRank המשוקלל של דפי Ti. התוצאה היא שקישור נכנס נוסף לדף A תמיד יגדיל את ה-PageRank של דף A.
    לבסוף, סכום ה-PageRanks המשוקללים לכל דפי Ti מוכפל בגורם צמצום d אותו ניתן להגדיר בין 0 ל-1. לכן, מידת התועלת לדף המקשר אליו מופחתת אף היא.

    מודל הגולש האקראי


    בפרסומיהם, לורנס פייג' וסרגיי ברין מציגים הצדקה פשוטה ואינטואיטיבית לאלגוריתם PageRank. הם רואים בו מודל להתנהגות משתמשים, כאשר גולשים מקליקים על קישורים באופן אקראי מבלי להתייחס לתוכן.
    הגולש האקראי מבקר בדף אינטרנט תוך סבירות מסוימת העולה מתוך ה -PageRank של הדף. הסבירות כי הגולשים האקראים יקליקו על קישור אחד מוצגת רק על ידי מספר הקישורים לאותו דף. זוהי הסיבה שה-PageRank של דף אחד אינו לחלוטין מועבר לדף אליו הוא מקשר, אלא שהוא מחולק במספר הקישורים שבאותו הדף.
    לכן, הסבירות כי גולש אקראי יגיע לדף מסוים הוא סכום ההסתברויות לגולש האקראי המגיע לדף זה באמצעות קישורים. כעת, הסתברות זו מופחתת בגורם צמצום d. ההצדקה במודל הגולש האקראי, אם הן, היא שהגולש אינו מקליק על אינסוף קישורים אלא לעיתים משתעמם ועובר לדף אחר באופן אקראי.
    ההסתברות שהגולש האקראי לא יעצור להקליק על קישורים, בא לידי ביטוי על פי גורם הצמצום d אשר, על פי מידת ההסתברות לכך, נקבע בין 0 ל-1. ככל שערך d גבוה יותר, כך גבוהה ההסתברות כי הגולש האקראי ימשיך להקליק על קישורים. היות והגולש עובר באופן אקראי לדף אחר לאחר שהפסיק להקליק על קישורים, ההסתברות לכך מבוטאת באלגוריתם בערך קבוע של (1-d). ללא קשר לקישורים נכנסים, ההסתברות שגולש אקראי יעבור לדף אחר היא תמיד (1-d), כך שתמיד יש PageRank מינימאלי לדף.

    הצגה אחרת של אלגוריתם PageRank


    לורנס פייג' וסרגיי ברין פרסמו שתי גרסאות שונות לאלגוריתם PageRank בשתי עבודות שונות. בגירסה השנייה, מוצג PageRank של עמוד A באופן הבא:

    PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

    כאשר N משקף את סך הכול מספר העמודים באתר. הגירסה השנייה של האלגוריתם בעצם אינה שונה באופן מהותי מהראשונה. בעניין מודל הגולש האקראי, ה-PageRank בגירסה השנייה הוא בעצם ההסתברות שגולש יגיע לאותו הדף לאחר הלחיצה על קישורים רבים. ה-PageRanks יוצרים פיזור הסתברותי על פני דפי האתר וכך סכום ה-PageRanks של כל הדפים יהיה אחד.
    לחלופין, בגירסה הראשונה, ההסתברות שגולש אקראי יגיע לדף מסוים משוקללת על ידי מספר דפי הרשת העולל. לכן, בגירסה זו, מהווה PageRank ערך צפוי שבו הגולש מבקר בדף, כאשר תהליך זה מתחיל בתדירות גבוהה כמו מספר הדפים באתר. אילו באתר היו 100 דפים ובדף אחד היה ערך PageRank של 2, יוכל הגולש האקראי להגיע לדף זה בממוצע של פעמיים אם הוא מתחיל מחדש 100 פעמים.
    כפי שהוזכר לעיל, שתי הגרסאות אינן שונות האחת מהשנייה באופן מהותי. יש להכפיל PageRank אשר חושב באמצעות הגרסה השנייה של האלגוריתם במספר דפי האתר הכולל על מנת להגיע ל-PageRank המקביל אשר היה מחושב באמצעות הגרסה הראשונה. אפילו פייג' וברין התבלבלו בין שתי הגרסאות בעבודתם המוכרת ביותר "האנטומיה של מנוע חיפוש היפרטקסט רחב היקף", שם הם טוענים כי הגרסה הראשונה של האלגוריתם יוצרת פיזור הסתברותי בדפי האתר כאשר סכום ה-PageRanks של כל הדפים שווה לאחד.
    בסעיף הבא, אנו נשתמש בגירסה הראשונה של האלגוריתם. הסיבה לכך היא כי קל יותר לחשב את חישובי PageRank באמצעות אלגוריתם זה, שכן ניתן להתעלם מהמספר הכולל של דפי רשת.

    מאפייני PageRank


    מאפייני PageRank יומחשו באמצעות דוגמה קטנה.
    ניקח אתר קטן המכיל שלושה דפים - A, V ו-C - שבו דף A מקשר לדפים B ו-C, דף B מקשר לדף C ודף V מקשר לדף A. לפי פייג' וברין, גורם השיכוך d מכוון בדרך כלל ל-085, אולם כדי להבטיח את פשטות החישוב, כיוונו את הגורם לרמה של 0.5. ברור כי לערך המדויק של גורם השיכוך d יש השפעה על PageRank, אולם הוא אינו משפיע על העקרונות הבסיסיים של PageRank. לכן, אנו מגיעים למשוואות הבאות לצורך חישוב PageRank:

    PR(A) = 0.5 + 0.5 PR(C)
    PR(B) = 0.5 + 0.5 (PR(A) / 2)
    PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

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

    PR(A) = 14/13 = 1.07692308
    PR(B) = 10/13 = 0.76923077
    PR(C) = 15/13 = 1.15384615

    ברור כי סכום כל ה-PageRanks שווה 3 ולכן שווה לסך הכול מספר דפי האתר. כפי שהוצג לעיל, אין זו תוצאה ספציפית עבור הדוגמה הפשוטה שלנו.
    קל לפתור את המשוואה בדוגמה שלנו על מנת לקבוע את ערכי PageRank. למעשה, הרשת מורכבת ממיליארדי מסמכים ואי אפשר למצוא פתרון פשוט על ידי בדיקה.

    החישוב האיטרטיבי של PageRank


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

    ניתן לראות, אם כן, שאנו מוצאים אומדן טוב לערכי PageRank האמיתיים לאחר מספר איטרציות בלבד. על פי הפרסומים של לורנס פייג' וסרגיי ברין, יש צורך בכ-100 איטרציות על מנת להגיע להערכה טובה של ערכי PageRank ברשת כולה.
    בנוסף, החישוב האיטרטיבי מביא לכך שסכום ה-PageRank של כל הדפים עדיין מסתכם בכלל מספר דפי הרשת. כך שה-PageRank הממוצע של דף רשת הוא 1. ערך PageRank המינימאלי לדף מבוטא על ידי (1-d). לכן, קיים PageRank מקסימאלי לדף המבוטא על ידיdN+(1-d), כאשר N הוא סך הכול מספר דפי הרשת. ניתן להגיע, באופן תיאורטי, לשיעור המקסימאלי הזה, אם כל דפי הרשת מקשרים אך ורק לדף אחד ואם דף זה גם מקשר אך ורק לעצמו.




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

    דף הבית | פרופיל חברה | פתרונות
    לקוחות | פורטפוליו | צור קשר