Hits

در بحث hub and authorities صفحات جعلی وجود دارند که تا فقط به سایت مورد نظر لینک داده و ارزش ان را بالا ببرن برای جلوگیری این اتفاقات ما از الگوریتم جان کلینبرگ به نام HITS استفاده خواهیم کرد این الگوریتم به شکل پایین می باشد.

همانطور که میدانید ما یدونه hub داریم که صفحه ای است که به صفحات دیگه لینک داده مانند یاهو و یدونه هم صفحات authority داریم که بهش لینک میدن چون صفحات مهمی هستند

یک hub خوب به صفحات authority زیادی لینک میده و یک authority خوب از hub های زیادی لینک می گیرد این تشخیص نوع این دو حال به سراغ الگوریتم و فرمول ها و نحوه کار آن برویم

ابتدا با یک مثال آغاز می کنیم در این الگوریتم هر صفحه ای وزن بخصوص خودشو داره که بهش می گن authority weight,hub weights این وزن ها به صورت بازگشتی تعریف می شوند.
یک authority weight بالا زمانی رخ می دهد که hub weights بالایی بهش لینک بدن و برعکس یک hub weights بالا زمانی رخ می دهد که آن صفحه به صفحات authority weight, بالایی لینک بدهد.

در اینجا ما بردار v را داریم که نشانگر authority weight و بردار u نشانگر hub weights میباشد

ما A را هم داریم که ماتریس گراف هست و با استفاده از این ماتریس و ترانهاده ی ان فرمول زیر را داریم :

اگر وزن نود هارا نیز طبق مقابل در نظر بگیریم:

و

داریم:

برای مثال ما در اینجا گراف پایین را کشیدیم :

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

فرض میکنیم وزن بردار hub weights به صورت مقابل است

طبق فرمول بالا داریم :

در اینجا می فهمیم که نود 3 از همه بیشترauthority دارد و نود های 1 و 2 هم hubهای مهمی هستن

طبق این توضیحات الگوریتم روش HITS تکه کد زیر را داریم که در کتابخانه ی Networkx این الگوریتم در آن جا اجرا شده هست

تکه کد زیر در زبان پایتون میباشد :

# add library

import networkx as nx

import matplotlib.pyplot as plt

G = nx.DiGarph() #build a digraph named G

G.add_edges_from([('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'A'),

('D', 'C'), ('E', 'D'), ('E', 'B'), ('E', 'F'),

('E', 'C'), ('F', 'C'), ('F', 'H'), ('G', 'A'),

('G', 'C'), ('H', 'A')])

#initialize edges

plt.figure(figsize =(10, 10)) #give the plot size

nx.draw_networkx(G, with_labels = True) #draw nx with 2 argument

hubs, authorities = nx.hits(G, max_iter = 50, normalized = True)

# The in-built hits function returns two dictionaries keyed by nodes

# containing hub scores and authority scores respectively.

print("Hub Scores: ", hubs)

print("Authority Scores: ", authorities)

output:

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}