فهرست مقاله
در یک مجموعهٔ سندِ مهندسی، صفحهٔ فهرست و صفحهٔ توضیحِ تخصصی لزوماً نقشِ یکسانی ندارند. یکی به منابع اشاره می‌کند و دیگری از صفحه‌های مختلف پیوند می‌گیرد. HITS این دو نقش را با دو امتیازِ ساختاری جدا می‌کند. در این درس، گرافی ساختگی را از قبل داریم و حسابِ چند دورِ مشخص را با کسرِ دقیق انجام می‌دهیم. هیچ سایتی خزش نمی‌شود و امتیازِ حاصل، اعتبارِ علمیِ سند یا کیفیتِ پاسخ به پرسش نیست.
۱. دو نقش را در یک گرافِ ثابتِ سند جدا کنیم
پنج شناسهٔ A تا E را سند فرض می‌کنیم. A به C و D پیوند دارد و B فقط به D اشاره می‌کند؛ سه گرهٔ دیگر خروجی ندارند. این حروف نامِ سندهای تألیفی‌اند، نه نشانیِ واقعی یا نامِ محصول. جهتِ پیوند مهم است و جفتِ مبدأ و مقصد فقط یک بار می‌آید. یک سند می‌تواند در گرافی دیگر هم پیوندِ ورودی و هم خروجی داشته باشد؛ دو نقش، دو نوعِ انحصاریِ سند نیستند.
بخشِ کاملِ هاب و مرجع در کتابِ بازیابی اطلاعات، امتیازِ هاب را از مرجع‌های مقصد و امتیازِ مرجع را از هاب‌های مبدأ می‌سازد. در اینجا واژهٔ «مرجع» نامِ نقشِ authority در الگوریتم است؛ تأییدِ نویسنده، صحتِ محتوای فنی یا داشتنِ مجوز نیست. فقط پیوندهایِ داده‌شده در محاسبه حضور دارند و متنِ اسناد اصلاً ورودیِ برنامه نیست.
در درسِ PageRank و گرهِ بی‌خروجی یک بردارِ احتمال، تقسیمِ سهم میان خروجی‌ها و پرشِ یکنواخت داشتیم. اینجا دو بردار داریم، سهمِ هاب بر تعدادِ خروجی‌هایش تقسیم نمی‌شود و پرشِ تصادفی وجود ندارد. یکسان بودنِ جمعِ مؤلفه‌ها با یک، این دو مدل را معادل نمی‌کند. عددهای HITS در قراردادِ حاضر بی‌بُعد و نرمال‌شده‌اند؛ احتمالِ درست‌بودنِ سند نیستند.
۲. امتیازِ ورودی و خروجی را به‌نوبت حساب کنیم
هابِ آغازینِ هر پنج گره یک‌پنجم است. یک دور را دقیقاً چنین تعریف می‌کنیم: ابتدا مرجعِ هر مقصد، جمعِ هابِ مبدأهای ورودی است؛ سپس همهٔ مرجع‌ها بر جمعِ خودشان تقسیم می‌شوند. بعد، هابِ تازهٔ هر مبدأ از جمعِ مرجع‌های تازهٔ مقصدهایش ساخته و جداگانه بر جمعِ هاب‌ها تقسیم می‌شود. در مرحلهٔ دوم از مرجعِ تازه استفاده می‌کنیم؛ دو بردار هم‌زمان از حالتِ قدیمی به دست نمی‌آیند.
در دورِ اول، فقط C و D مرجعِ مثبت دارند. پیش از نرمال‌سازی، C یک‌پنجم و D دوپنجم می‌گیرند؛ پس سهم‌های نهاییِ مرجع یک‌سوم و دوسوم می‌شوند. هابِ A جمعِ این دو، یعنی یک، و هابِ B دوسوم است. جمعِ هابِ خام پنج‌سوم می‌شود؛ بنابراین هاب‌های نهاییِ A و B سه‌پنجم و دوپنجم‌اند. D با مرجعِ بالا، هابِ صفر دارد، چون به هیچ مقصدی اشاره نمی‌کند.
دورِ دوم، مرجعِ خامِ C را سه‌پنجم و مرجعِ خامِ D را یک می‌سازد. تقسیم بر هشت‌پنجم، سه‌هشتم و پنج‌هشتم می‌دهد. هابِ خامِ A دوباره یک و هابِ B پنج‌هشتم است؛ پاسخِ نرمال‌شده هشت‌سیزدهم و پنج‌سیزدهم می‌شود. این شاهد نشان می‌دهد شمارِ پیوندهای ورودی فقط نتیجهٔ یک مرحله با آغازِ یکنواخت را توضیح می‌دهد؛ دورهای بعد، وزنِ مبدأها هم اثر دارد.
۳. نرمال‌سازی و گرهٔ جدا را روشن نگه داریم
مستندِ دقیقِ HITS در NetworkX 3.7 دو خروجی و نرمال‌سازیِ نتیجه با مجموع را توضیح می‌دهد. کدِ ما در پایانِ هر نیم‌مرحله همین نوعِ نرمال‌سازی را صریح انجام می‌دهد. تعدادِ دورِ مثبت ورودی است؛ آستانهٔ همگرایی، روشِ SVD یا برابریِ کامل با رابطِ آن کتابخانه نداریم. NetworkX و NumPy در اجرای این فایل استفاده نشده‌اند.
E هیچ ورودی و خروجی ندارد و هر دو امتیازش بعد از دورِ نخست صفرند. افزودنِ چنین گرهِ جدا، در همین قراردادِ آغازِ یکنواخت و نرمال‌سازیِ سراسری، امتیازِ گره‌های قبلی را تغییر نمی‌دهد. این رفتار با پرشِ مثبتِ PageRank فرق دارد. اگر تمام گراف بی‌پیوند باشد، هیچ جمعِ مثبت برای تقسیم نداریم؛ برنامه آن ورودی را با خطای روشن رد می‌کند و صفرها را به‌عنوان بردارِ معتبرِ نرمال‌شده پس نمی‌دهد.
گرافِ جداشده نیز لزوماً یک جوابِ ترجیحیِ یکتا ندارد. برای دو پیوندِ مستقلِ A به C و B به D، آغازِ یکنواخت به هر دو هاب و هر دو مرجع سهمِ مساوی می‌دهد. اما نسبتِ دیگری میان دو مؤلفه هم می‌تواند ثابت بماند؛ الگوریتم خودش دلیلی برای ترجیحِ یکی نساخته است. همچنین چرخه در گرافِ اولیه به‌تنهایی به معنیِ نوسانِ این دورها نیست: حسابِ دو مرحله به ماتریسِ A*Aᵀ برای هاب‌ها مربوط می‌شود، نه تکرارِ مستقیمِ همان ماتریسِ مجاورت.
۴. شاهدِ کسری را با شمارشِ مستقل بسنجیم
فایل hits_hub_authority.py با Python 3.14.5 و فقط کتابخانهٔ استاندارد واقعاً اجرا شده است. گراف dict واقعی و غیرخالی است؛ شناسه‌ها رشتهٔ دقیقِ غیرخالی و بدون فاصلهٔ ابتدا و انتها هستند. خروجیِ هر گره list یا tuple از شناسه‌های موجود است. مقصدِ ناشناخته و پیوندِ تکراری خطا می‌دهند؛ تکرار را بی‌اعلان وزنِ بیشتر یا پیوندِ تازه نمی‌نامیم. حلقهٔ خودی صریح مجاز است.
"""Exact finite HITS update rounds on a supplied unweighted directed graph."""
from dataclasses import dataclass
from fractions import Fraction
from itertools import product
import copy
import json
import platform
@dataclass(frozen=True)
class Scores:
nodes: tuple
authority: tuple
hub: tuple
rounds: int
def hits_rounds(graph, rounds):
"""Each round: incoming authority, L1 normalize, outgoing hub, normalize.
Result is after a declared number of updates, NOT a convergence certificate.
A node may have both roles. Isolates score zero; all-edgeless input is invalid.
"""
if type(graph) is not dict or not graph:
raise ValueError('a nonempty actual dict is required')
if any(type(n) is not str or not n or n.strip() != n for n in graph):
raise ValueError('node IDs must be actual nonempty trimmed strings')
if type(rounds) is not int or rounds < 1:
raise ValueError('rounds must be an actual positive integer')
nodes = tuple(sorted(graph))
adjacency = {}
for node in nodes:
targets = graph[node]
if type(targets) not in (tuple, list):
raise ValueError('each outgoing list must be an actual tuple/list')
if any(type(v) is not str or v not in graph for v in targets):
raise ValueError('each target must name a supplied node')
if len(set(targets)) != len(targets):
raise ValueError('parallel duplicate links are outside this graph contract')
adjacency[node] = tuple(targets)
if not any(adjacency.values()):
raise ValueError('edgeless graph has no positive HITS normalization total')
hub = dict.fromkeys(nodes, Fraction(1, len(nodes)))
for _ in range(rounds):
authority = dict.fromkeys(nodes, Fraction(0))
for u in nodes:
for v in adjacency[u]:
authority[v] += hub[u]
total = sum(authority.values())
authority = {v: value / total for v, value in authority.items()}
new_hub = {u: sum((authority[v] for v in adjacency[u]), Fraction(0))
for u in nodes}
total = sum(new_hub.values())
hub = {u: value / total for u, value in new_hub.items()}
return Scores(nodes, tuple(authority[n] for n in nodes),
tuple(hub[n] for n in nodes), rounds)
def integer_twohop_reference(graph, rounds):
"""Integer A*A^T path counts, no rational update/normalizer/main calls."""
nodes = tuple(sorted(graph))
n = len(nodes)
adjacency = [[int(v in graph[u]) for v in nodes] for u in nodes]
twohop = [[sum(adjacency[i][k] * adjacency[j][k] for k in range(n))
for j in range(n)] for i in range(n)]
h = [1] * n
for _ in range(rounds - 1):
h = [sum(twohop[i][j] * h[j] for j in range(n)) for i in range(n)]
a = [sum(adjacency[i][j] * h[i] for i in range(n)) for j in range(n)]
next_h = [sum(twohop[i][j] * h[j] for j in range(n)) for i in range(n)]
return (tuple(Fraction(x, sum(a)) for x in a),
tuple(Fraction(x, sum(next_h)) for x in next_h))
def mapped(result, role):
return dict(zip(result.nodes, getattr(result, role), strict=True))
def rejected(graph, rounds):
try:
hits_rounds(graph, rounds)
except ValueError:
return True
return False
def serial(result):
return {'nodes': result.nodes, 'authority': [str(x) for x in result.authority],
'hub': [str(x) for x in result.hub], 'rounds': result.rounds}
def main():
graph = {'A': ('C', 'D'), 'B': ('D',), 'C': (), 'D': (), 'E': ()}
first = hits_rounds(graph, 1)
second = hits_rounds(graph, 2)
checks = {}
checks['literal_first_round_two_ordered_updates'] = (
first.authority == (0, 0, Fraction(1, 3), Fraction(2, 3), 0)
and first.hub == (Fraction(3, 5), Fraction(2, 5), 0, 0, 0))
checks['literal_second_round_fraction_hand_answer'] = (
second.authority == (0, 0, Fraction(3, 8), Fraction(5, 8), 0)
and second.hub == (Fraction(8, 13), Fraction(5, 13), 0, 0, 0))
cases = 0
for flags in product((0, 1), repeat=9):
g = {u: tuple(v for j, v in enumerate('ABC') if flags[3 * i + j])
for i, u in enumerate('ABC')}
if not any(flags):
continue
for rounds in range(1, 5):
got = hits_rounds(g, rounds)
expected_a, expected_h = integer_twohop_reference(g, rounds)
assert got.authority == expected_a and got.hub == expected_h
assert sum(got.authority) == sum(got.hub) == 1
assert all(x >= 0 for x in got.authority + got.hub)
cases += 1
checks['integer_twohop_oracle_2044_graph_round_pairs_one_group'] = cases == 2044
forward = hits_rounds({'A': ('B',), 'B': ()}, 3)
backward = hits_rounds({'A': (), 'B': ('A',)}, 3)
checks['one_link_direction_separates_incoming_and_outgoing_roles'] = (
forward.authority == (0, 1) and forward.hub == (1, 0)
and backward.authority == (1, 0) and backward.hub == (0, 1))
without_isolate = {u: v for u, v in graph.items() if u != 'E'}
reduced = hits_rounds(without_isolate, 2)
checks['adding_an_isolate_gives_zero_without_changing_other_scores'] = (
second.authority[-1] == second.hub[-1] == 0
and second.authority[:-1] == reduced.authority
and second.hub[:-1] == reduced.hub)
disconnected = {'A': ('C',), 'B': ('D',), 'C': (), 'D': ()}
symmetric = hits_rounds(disconnected, 4)
checks['equal_disconnected_blocks_keep_declared_uniform_start_symmetry'] = (
symmetric.authority == (0, 0, Fraction(1, 2), Fraction(1, 2))
and symmetric.hub == (Fraction(1, 2), Fraction(1, 2), 0, 0))
third = hits_rounds(graph, 3)
change = sum(abs(a - b) for a, b in zip(second.hub, third.hub, strict=True))
checks['finite_round_count_does_not_claim_stationarity'] = (
first.rounds == 1 and second.rounds == 2 and third.rounds == 3
and second.authority != third.authority and change > 0)
singleton = hits_rounds({'SELF': ('SELF',)}, 7)
checks['explicit_self_loop_singleton_has_both_roles_one'] = (
singleton.authority == singleton.hub == (1,))
order = {'E': (), 'D': (), 'C': (), 'B': ('D',), 'A': ('D', 'C')}
renamed = {'left': ('sink-z', 'sink-y'), 'right': ('sink-y',),
'sink-z': (), 'sink-y': (), 'alone': ()}
rename = {'A': 'left', 'B': 'right', 'C': 'sink-z', 'D': 'sink-y', 'E': 'alone'}
new = hits_rounds(renamed, 2)
checks['node_target_order_and_bijective_names_do_not_change_structure'] = (
hits_rounds(order, 2) == second
and all(mapped(new, role)[rename[u]] == mapped(second, role)[u]
for role in ('hub', 'authority') for u in graph))
mutable = {u: list(v) for u, v in graph.items()}
before = copy.deepcopy(mutable)
frozen_result = hits_rounds(mutable, 2)
unchanged = mutable == before
mutable['A'].clear()
checks['mutable_adjacencies_are_not_modified_or_aliased_by_result'] = (
unchanged and frozen_result == second)
checks['graph_identity_edge_container_unknown_and_duplicate_rejections'] = all(
rejected(g, 1) for g in (None, [], {}, {' A': ('A',)}, {1: (1,)},
{'A': {'A'}}, {'A': ('UNKNOWN',)}, {'A': ('A', 'A')}, {'A': (True,)}))
checks['positive_actual_integer_round_contract'] = all(
rejected(graph, value) for value in (True, 0, -1, 1.0, '2', None))
checks['entirely_edgeless_graph_is_explicit_error_not_division_by_zero'] = (
rejected({'A': ()}, 1) and rejected({'A': (), 'B': ()}, 2))
assert all(type(x) is bool and x for x in checks.values()), checks
print(json.dumps({
'python': platform.python_version(), 'dependencies': 'stdlib only',
'networkx_executed': False, 'numpy_executed': False,
'graph': graph, 'round1': serial(first), 'round2': serial(second),
'round3': serial(third), 'hub_change_round2_to3_L1': str(change),
'integer_twohop_graph_round_pairs_inside_one_group': cases,
'checks': checks, 'unique_check_groups': len(checks), 'all_passed': True,
'limits': 'Finite ordered Fraction updates on supplied graph, not a convergence certificate, probability, source credibility, textual relevance, crawl or production search ranking. Reducible equal-strength components need not define a unique preferred principal vector.'
}, ensure_ascii=False, indent=2))
if __name__ == '__main__':
main()
مسیرِ اصلی با Fraction، جمعِ ورودی‌ها و خروجی‌ها را به‌نوبت انجام می‌دهد. مرجع مستقل، ماتریسِ صفر و یکِ پیوندها و حاصلِ دوگامیِ آن با ترانهاده را با عددِ صحیح می‌سازد؛ این خانه‌ها تعدادِ مقصدهای مشترکِ دو مبدأ را می‌شمارند. شمارشِ صحیح تا دورِ خواسته‌شده ادامه می‌یابد و فقط در پایان به نسبت تبدیل می‌شود. مرجع از تابعِ اصلی یا نرمال‌سازِ آن برای ساختِ جوابِ انتظار استفاده نمی‌کند.
تمام ۵۱۲ گرافِ جهت‌دارِ سه‌گرهی با امکانِ حلقهٔ خودی در نظر گرفته شدند؛ حالتِ کاملاً بی‌پیوند کنار گذاشته شد. برای هر یک از ۵۱۱ گراف، یک تا چهار دور مقایسه می‌شود؛ ۲۰۴۴ زوجِ گراف و دور، یک گروهِ مرجع‌اند. پاسخِ دستی، جهتِ تک‌پیوند، گرهِ جدا، مؤلفه‌های مستقل، ترتیبِ ورودی و نام‌گذاری نیز شاهدهای جدا دارند. هیچ سقفِ کوچکِ دلخواه برای اندازهٔ گراف نگذاشته‌ایم؛ هزینهٔ عددهای صحیحِ بزرگ و ظرفیتِ حافظه همچنان محدودیت عملی‌اند.
{
"python": "3.14.5",
"dependencies": "stdlib only",
"networkx_executed": false,
"numpy_executed": false,
"graph": {
"A": [
"C",
"D"
],
"B": [
"D"
],
"C": [],
"D": [],
"E": []
},
"round1": {
"nodes": [
"A",
"B",
"C",
"D",
"E"
],
"authority": [
"0",
"0",
"1/3",
"2/3",
"0"
],
"hub": [
"3/5",
"2/5",
"0",
"0",
"0"
],
"rounds": 1
},
"round2": {
"nodes": [
"A",
"B",
"C",
"D",
"E"
],
"authority": [
"0",
"0",
"3/8",
"5/8",
"0"
],
"hub": [
"8/13",
"5/13",
"0",
"0",
"0"
],
"rounds": 2
},
"round3": {
"nodes": [
"A",
"B",
"C",
"D",
"E"
],
"authority": [
"0",
"0",
"8/21",
"13/21",
"0"
],
"hub": [
"21/34",
"13/34",
"0",
"0",
"0"
],
"rounds": 3
},
"hub_change_round2_to3_L1": "1/221",
"integer_twohop_graph_round_pairs_inside_one_group": 2044,
"checks": {
"literal_first_round_two_ordered_updates": true,
"literal_second_round_fraction_hand_answer": true,
"integer_twohop_oracle_2044_graph_round_pairs_one_group": true,
"one_link_direction_separates_incoming_and_outgoing_roles": true,
"adding_an_isolate_gives_zero_without_changing_other_scores": true,
"equal_disconnected_blocks_keep_declared_uniform_start_symmetry": true,
"finite_round_count_does_not_claim_stationarity": true,
"explicit_self_loop_singleton_has_both_roles_one": true,
"node_target_order_and_bijective_names_do_not_change_structure": true,
"mutable_adjacencies_are_not_modified_or_aliased_by_result": true,
"graph_identity_edge_container_unknown_and_duplicate_rejections": true,
"positive_actual_integer_round_contract": true,
"entirely_edgeless_graph_is_explicit_error_not_division_by_zero": true
},
"unique_check_groups": 13,
"all_passed": true,
"limits": "Finite ordered Fraction updates on supplied graph, not a convergence certificate, probability, source credibility, textual relevance, crawl or production search ranking. Reducible equal-strength components need not define a unique preferred principal vector."
}۵. تعدادِ دور را همگرایی یا اعتبارِ منبع ننامیم
سیزده گروهِ معنادار گذشتند، اما پایانِ دو دور، گواهِ نقطهٔ ثابت نیست. هابِ دورِ سوم در نمونه، بیست‌ویک‌سی‌وچهارم و سیزده‌سی‌وچهارم می‌شود؛ فاصلهٔ مجموعِ قدرمطلقِ آن با دورِ دوم یک‌دویست‌وبیست‌ویکم است. این عدد، تضمینِ خطای واقعی یا معیارِ توقفِ برنامه نیست. کتاب نیز برای یکتاییِ بردارِ غالب شرط دارد؛ تقسیم بر مجموع، مشکلِ یکتاییِ مؤلفه‌های مستقل را حل نمی‌کند.
پرسش اول: چرا A در دورِ دوم هابِ هشت‌سیزدهم ولی مرجعِ صفر دارد؟ پاسخ: به C و D پیوند دارد، اما هیچ مبدأیی به A اشاره نمی‌کند. هابِ بالا، مرجعِ بالا را الزام نمی‌کند.
پرسش دوم: چرا E سهمِ مثبتِ پرش نمی‌گیرد؟ پاسخ: این مدل اصلاً پرش ندارد. صفرِ E دربارهٔ نقشِ ساختاریِ آن در گرافِ داده‌شده است؛ بی‌ارزشیِ محتوای سند را ثابت نمی‌کند.
پرسش سوم: اگر پیوندِ A به D دوبار در ورودی بیاید چه می‌شود؟ پاسخ: برنامه رد می‌کند؛ برای گرافِ وزن‌دار باید معنای وزن و مرجعِ آزمونِ تازه مشخص شود. پاک‌کردن یا دوبارشمردنِ خاموش، دادهٔ ورودی را تغییر می‌دهد.
پرسش چهارم: دورهای بیشتر یعنی جوابِ جست‌وجوی بهتر؟ پاسخ: خیر؛ فقط حسابِ همان گراف ادامه می‌یابد. انتخابِ مجموعهٔ پایه در HITS مسئولیتِ جدا دارد؛ درسِ حذفِ نامزدهای بازیابی نیز نشان می‌دهد حسابِ درست روی مجموعهٔ محدود، مناسب‌بودنِ خودِ مجموعه را ثابت نمی‌کند. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ تاریخِ تولیدِ HTML کتاب در ۲۰۰۹ از انتشارِ اولیهٔ نامعلومِ صفحه و نسخهٔ نرم‌افزار جدا ثبت است. این آموزش خبرِ تازه یا گزارشِ کیفیتِ محصول نیست.
منابع و مطالعهٔ بیشتر
- کتاب بازیابی اطلاعات؛ دو امتیاز HITS و رابطهٔ ماتریسی
- NetworkX 3.7؛ نقش هاب و مرجع و قرارداد محاسبهٔ HITS
- کتاب بازیابی اطلاعات؛ انتخابِ مجموعهٔ پایه برای تحلیل HITS
بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
