در این مطلب، روش نوشتن الگوریتم HITS در پایتون مورد بررسی قرار گرفته است. «جستجوی موضوع القا شده با ابر پیوند» (Hyperlink Induced Topic Search | HITS) یک «الگوریتم تحلیل پیوند» (Link Analysis Algorithm) است که صفحات وب را امتیازدهی می‌کند. این الگوریتم توسط «جان کلینبرگ» (Jon Kleinberg) توسعه داده شده است. از الگوریتم HITS برای ساختارهای لینک وب به منظور کشف و رتبه‌دهی صفحات وب مرتبط برای جستجوهای خاص استفاده می‌شود. HITS از هاب‌ها و احراز هویت‌ها برای تعریف یک رابطه بازگشتی بین صفحات وب استفاده می‌کند. پیش از درک الگوریتم، ابتدا باید درباره مفهوم هاب‌ها (Hubs) و «احراز هویت‌ها» (Authorities) توضیح داده شود.

  • یک کوئری (Query) به موتور جستجو داده شده است که یک مجموعه از صفحات وب به شدت مرتبط هستند که Roots نامیده می‌شوند. این‌ها Authoritie‌های بالقوه هستند.
  • به صفحاتی که خیلی مرتبط نیستند، اما به صفحاتی در Roots اشاره دارند، هاب گفته می‌شود. بنابراین، یک Authority یک صفحه وب است که هاب‌های زیادی به آن اتصال (پیوند) دارند، در حالیکه یک هاب، صفحه‌ای است که به بسیاری از Authority‌ها متصل است.

الگوریتم HITS در پایتون

  • تعداد تکرارها را برابر با k قرار بده.
  • به هر گره، یک Hub score = 1 و یک Authority score = 1 تخصیص بده.
  • به اندازه K بار تکرار کن:
    • به روز رسانی Hub: امتیاز هاب هر گره = $$\sum$$ گره (امتیاز Authority هر گره‌ای که به آن اشاره دارد.)
    • به روز رسانی Authority: امتیاز Authority هر گره = $$\sum$$ (امتیاز Hub هر گره‌ای که به آن اشاره دارد.)
    • نرمال‌سازی امتیازها با تقسیم امتیاز هاب‌ها بر ریشه دوم مجموع مربعات همه امتیازها و تقسیم هر امتیاز Authority بر ریشه دوم مجموع مربعات همه امتیازهای Authority (اختیاری).

در ادامه، چگونگی پیاده‌سازی الگوریتم بیان شده با استفاده از ماژول Networxx مورد بررسی قرار می‌گیرد. گراف زیر مفروض است.

الگوریتم HITS در پایتون -- راهنمای کاربردی

در صورت اجرای الگوریتم HITS با k = 3 (بدون نرمال‌سازی) داریم:

Initially,
Hub Scores:        Authority Scores:
A -> 1             A -> 1
B -> 1             B -> 1
C -> 1             C -> 1
D -> 1             D -> 1
E -> 1             E -> 1
F -> 1             F -> 1
G -> 1             G -> 1
H -> 1             H -> 1

After 1st iteration,
Hub Scores:        Authority Scores:
A -> 1             A -> 3
B -> 2             B -> 2
C -> 1             C -> 4
D -> 2             D -> 2
E -> 4             E -> 1
F -> 1             F -> 1
G -> 2             G -> 0
H -> 1             H -> 1

After 2nd iteration,
Hub Scores:        Authority Scores:
A -> 2             A -> 4
B -> 5             B -> 6
C -> 3             C -> 7
D -> 6             D -> 5
E -> 9             E -> 2
F -> 1             F -> 4
G -> 7             G -> 0
H -> 3             H -> 1

After 3rd iteration,
Hub Scores:        Authority Scores:
A -> 5             A -> 13
B -> 9             B -> 15
C -> 4             C -> 27
D -> 13            D -> 11
E -> 22            E -> 5
F -> 1             F -> 9
G -> 11            G -> 0
H -> 4             H -> 3

بسته پایتون Networkx یک تابع توکار برای اجرای الگوریتم HITS است. این کار را می‌توان با ارجاع به گراف بالا بصری‌سازی کرد.

خروجی قطعه کد بالا، به صورت زیر است.

Hub Scores:  {'A': 0.04642540386472174, 'D': 0.133660375232863,
              'B': 0.15763599440595596, 'C': 0.037389132480584515, 
              'E': 0.2588144594158868, 'F': 0.15763599440595596,
              'H': 0.037389132480584515, 'G': 0.17104950771344754}

Authority Scores:  {'A': 0.10864044085687284, 'D': 0.13489685393050574, 
                    'B': 0.11437974045401585, 'C': 0.3883728005172019,
                    'E': 0.06966521189369385, 'F': 0.11437974045401585,
                    'H': 0.06966521189369385, 'G': 0.0}

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

telegram
twitter

الهام حصارکی

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *