אלגוריתם רשויות ורכזים

רשויות ורכזים
Hubs and Authorities /
Hyperlink-Induced Topic Search

מבנה נתונים	גרף מכוון
ממציא	ג'ון קליינברג

אלגוריתם רשויות ורכזים (Hubs and Authorities; בשמו הרשמי Hyperlink-Induced Topic Search, בראשי תיבות: HITS) הוא אלגוריתם לניתוח קישורים אשר נועד לדרג דפי אינטרנט, ופותח על ידי ג'ון קליינברג (Jon Kleinberg). הרעיון מאחורי HITS נבע מתוך הצורך בהבנה מעמיקה של יצירת דפי האינטרנט וחיפושם בזמן המצאת האינטרנט. דף אינטרנט נקרא "רכז" אם הוא מצביע על הרבה דפי אינטרנט אחרים. דף "רשות" טוב הוא דף אשר הרבה רכזים מצביעים עליו.

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

רקע

האלגוריתם נוצר על ידי ג'ון קלינברג בשנת 1997 בעת שעבד ב-IBM ונועד לדרג אתרים, מבחינת דיוק נחשב למדויק ביותר מבין האלגוריתם אבל מבחינת יעילות נחשב למוצלח פחות. בשל היותו פחות יעיל מאלגוריתם אחרים אין כמעט מנועי חיפוש שמשתמשים בו.

חברות החיפוש מעדיפות להשתמש ב-PageRank של גוגל אשר מבחינת יעילות נחשב לטוב ביותר, אחד ממנועי החיפוש הגדולים אשר עדיין משתמשים באלגוריתם HITS הוא ask.com אשר מטרתו לתת למשתמש את התשובה הטובה ביותר לכל שאלה.

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

שימוש בכתבי עת

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

שימוש באינטרנט

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

האלגוריתם

Expanding the root set into a base set

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

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

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

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

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

האלגוריתם רץ מספר מחזורים, אשר מבצעים בכל מחזור שני שלבים בסיסים:

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

האלגוריתם לחישוב הרכז והרשות מחושב כך:

1. בתחילה כל צומת (דף) מקבל ציון 1 לרשות ולרכז.
2. עדכון:
   1. מעדכנים את ערכה של כל רשות.
   2. מעדכנים את ערכו של כל רכז.
   3. מנרמלים את הערכים על ידי חילוק כל ציון רכז בסכום כל ציוני הרכזים בריבוע, וכן חילוק כל ציון רשות בסכום כל ציוני הרשויות בריבוע.
3. חזרה על שלב העדכון, אם נדרש.

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

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

• הוא מבוסס שאילתה, זאת אומרת, ציוני הרשות והרכז הנובעים מניתוח הקישור מושפעים ממונחי החיפוש.
• מבוסס שאילתה ולא אינדקס, בשל כך זמן החיפוש הוא ארוך יותר.
• לא נפוץ בקרב מנועי חיפוש (אחד ממנועי החיפוש היחידים אשר משתמשים באלגוריתם דומה לו הוא Ask.com).
• לעומת אלגוריתמים אחרים שמחשבים תוצאה אחת, HITS מחשב שתי תוצאות (רכז ורשות).
• הוא מנתח מספר קטן של דפים רלוונטיים("קבוצת הבסיס"), לא כמו PageRank שמנתח את הדפים.

פירוט האלגוריתם

על מנת להתחיל את הדירוג, דרגת כל רשות ורכז ייקבעו ל-1. $\forall (p),\mathrm {auth} (p)=1,\mathrm {hub} (p)=1$

אנו מתכוונים לבצע שני עדכונים: עדכון ערכי רשויות, ועדכון ערכי רכזים.

כלל עדכון הרשויות – לכל רשות p נבצע עדכון של ערכה –

$\mathrm {auth} (p)={\frac {\sum _{i=1}^{n}\mathrm {hub} (p)}{n}}$

כאשר n מייצגת את מספר הרכזים אשר מפנים אל רשות זו.

כלל עדכון הרכזים – לכל רכז p נבצע עדכון של ערכו –

$\mathrm {hub} (p)={\frac {\sum _{i=1}^{n}\mathrm {auth} (p)}{m}}$

כאשר m מייצגת את מספר הרשויות אשר רכז זה מצביע עליהן.

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

פסאודו-קוד

G = set of pages
for page in G do
    page.auth = 1 // page.auth is the authority score of the page p
    page.hub = 1  // page.hub is the hub score of 'page
   
function HubsAndAuthorities(G)
    for step in (1 to k) do // run the algorithm for k steps
        norm = 0
        for page in G do      // update all authority values first
        page.auth = 0
            for inNeighbor in page.incomingNeighbors do // page.incomingNeighbors is the set of pages that link to 'page'
                page.auth += inNeighbor.hub
        norm += square(page.auth) // calculate the sum of the squared auth values to normalise
    norm = sqrt(norm)
    for page in G do  // update the auth scores 
        page.auth = page.auth / norm  // normalise the auth values
    norm = 0
    for page in G do  // then update all hub values
        page.hub = 0
        for outNeighbor in page.outgoingNeighbors do // page.outgoingNeighbors is the set of pages that 'page' links to
            p.hub += outNeighbor.auth
        norm += square(page.hub) // calculate the sum of the squared hub values to normalise
    norm = sqrt(norm)
    for page in G do  // then update all hub values
        page.hub = page.hub / norm   // normalize the hub values

קישורים חיצוניים

• מאמרו המקורי של ג'ון קליינברג
• סרטון הסבר של ג'ון קליינברג, באתר יוטיוב