PageRank گراف پیوند با پایتون؛ گره بی‌خروجی، جرم احتمال و آزمون همگرایی

ساختار پیوندهای یک مجموعهٔ سند را می‌توان جدا از متن و پرسش بررسی کرد. در این درس، چهار سند فرضی داریم و می‌خواهیم سهم عددی هر گره را در یک مدل سادهٔ PageRank حساب کنیم. مسئلهٔ اصلی، حفظ جرم احتمال، رفتار گره بدون پیوند خروجی و تعریف درست توقف تکرار است. هیچ صفحهٔ وبی خزش نمی‌شود و نتیجه دربارهٔ رتبهٔ گوگل، سئو یا کیفیت واقعی جست‌وجو نیست.

۱. گراف جهت‌دار با امتیاز ارتباط متن فرق دارد

چهار گره A، B، C و D را سند می‌گیریم. A به B و C اشاره می‌کند، B به C پیوند دارد، C به A برمی‌گردد و D هیچ خروجی ندارد. جهت مهم است: پیوند A به B به معنای پیوند B به A نیست. در قرارداد ما هر جفتِ مبدأ و مقصد حداکثر یک پیوند دارد و وزن همهٔ پیوندها یکسان است.

مقالهٔ Brin و Page در سال ۱۹۹۸ استفاده از ساختار پیوند و انتقال سهم گره‌ها را در نمونهٔ تاریخی موتور جست‌وجو توضیح می‌دهد. آن مقاله زمینهٔ این تمرین عددی است؛ کد ما الگوریتم سامانهٔ امروزی گوگل را بازسازی نمی‌کند. مدلِ نرمال‌شدهٔ همین درس را با فرض‌های صریح تعریف می‌کنیم و هیچ ادعای تاریخیِ کیفیت یا سرعت را به آزمایش کوچک خود تعمیم نمی‌دهیم.

برخلاف امتیاز BM25 متن، در اینجا واژه، طول سند و پرسش نداریم. عدد حاصل فقط از گراف فرضی به دست می‌آید؛ سندی با سهم بالاتر الزاماً پاسخ درست یا موضوع مرتبط‌تری ندارد. برای جایگاه این جزء در معماری کلی، مرور نمایه و رتبه‌بندی موتور جست‌وجو مفید است، اما ترکیب اجزا نیازمند ارزیابی جداست.

۲. سهم پیوند و پرش یکنواخت را دقیق تعریف کنیم

بردار آغازین به هر گره یک‌چهارم می‌دهد؛ جمع سهم‌ها یک و واحدشان بی‌بُعد است. ضریب alpha را یک‌دوم می‌گیریم. در هر گام، نیمِ سهم یک گره میان خروجی‌هایش به‌طور مساوی تقسیم می‌شود. بنابراین A سهم پیوندی خود را نصف‌نصف به B و C می‌دهد، ولی B تمام سهم پیوندی خود را به C می‌فرستد.

بخش دیگر مدل، پرش یکنواخت است: به هر گره مقدار «یک منهای alpha، تقسیم بر تعداد گره‌ها» اضافه می‌شود. در نمونهٔ چهارگرهی این مقدار یک‌هشتم است. این قرارداد اجازه می‌دهد حتی گره‌ای بدون ورودی نیز سهم مثبت بگیرد. alpha احتمال دنبال‌کردن مسیر پیوندی در این تعریف است؛ احتمال پرش برابر یک منهای آن است. این دو را نباید جابه‌جا کرد.

alpha از صفر تا کمتر از یک پذیرفته می‌شود. در صفر، ساختار پیوند اثری ندارد و خروجی یکنواخت است. یک را رد می‌کنیم تا فرض پرش مثبت و رفتار انقباضیِ مدل حفظ شود. این محدودیت به معنای تضمین پایان در هر تعداد تکرار دلخواه نیست؛ برنامه همچنان سقف تکرار و گزارش شکست دارد. شخصی‌سازی و وزن متفاوت پیوندها در این فایل پیاده نشده‌اند.

۳. سهم گره بی‌خروجی را گم نکنیم

D سهم دارد اما مقصد پیوندی ندارد. اگر فقط خروجی‌های موجود را پخش کنیم، سهم مربوط به این گره از محاسبه حذف می‌شود و جمع اعداد کاهش می‌یابد. راه انتخابیِ ما، پخش یکنواخت سهم تمام گره‌های بی‌خروجی میان همهٔ گره‌هاست؛ سپس ضریب alpha اعمال می‌شود. در گام اول، سهم D یک‌چهارم است و بخش پیوندیِ بازتوزیع‌شده برای هر گره یک‌سی‌ودوم می‌شود.

با اضافه‌کردن پرش یک‌هشتم و سهم پیوندهای ورودی، جواب دستی گام اول به ترتیب A، B، C و D برابر نُه، هفت، یازده و پنج، همگی تقسیم بر سی‌ودو است. جمع صورت‌ها سی‌ودو می‌شود؛ جرم احتمال حفظ شده است. برای نمونه، A از C یک‌هشتم می‌گیرد و همراه پرش و سهم بازتوزیع، به نُه‌سی‌ودوم می‌رسد.

مستندات PageRank در NetworkX 3.7 نیز گره‌های بی‌خروجی و بازتوزیع پیش‌فرض مطابق بردار شخصی‌سازی را توضیح می‌دهد. این درس حالت یکنواخت را انتخاب کرده است. نه آن کتابخانه اجرا شده، نه پشتیبان GPU آن؛ تنها قرارداد ریاضی روشن و پیاده‌سازی مستقلِ کوچک با کتابخانهٔ استاندارد پایتون داریم.

۴. کد کامل، پاسخ کسری و باقیماندهٔ واقعی

فایل link_graph_pagerank.py با Python 3.14.5 اجرا شده است. مسیر اصلی، بردار را تکرار می‌کند. مرجع مستقل، دستگاه خطی نقطهٔ ثابت را با Fraction و حذف گاوسی حل می‌کند؛ از تابع گامِ مسیر اصلی استفاده نمی‌کند. جواب دقیق نمونه برای A برابر چهارسیزدهم، برای B بیست‌نودویکم، برای C سی‌نودویکم و برای D یک‌هفتم است.

"""Small synthetic directed-graph PageRank; not a search engine or SEO model."""
from copy import deepcopy
from fractions import Fraction
from itertools import product
import json
import math
import platform
import re


def validated_graph(graph):
    identifier = re.compile(r'[A-Za-z][A-Za-z0-9_]{0,15}', re.ASCII)
    if type(graph) is not dict or not 1 <= len(graph) <= 8:
        raise ValueError('graph')
    if any(type(k) is not str or identifier.fullmatch(k) is None for k in graph):
        raise ValueError('node')
    for outgoing in graph.values():
        if (type(outgoing) is not list or len(outgoing) > 8
                or any(type(target) is not str or target not in graph for target in outgoing)
                or len(set(outgoing)) != len(outgoing)):
            raise ValueError('edges')
    return {node: tuple(sorted(graph[node])) for node in sorted(graph)}


def _step(graph, ranks, alpha):
    nodes = list(graph)
    n = len(nodes)
    dangling_mass = math.fsum(ranks[node] for node in nodes if not graph[node])
    base = (1 - alpha) / n + alpha * dangling_mass / n
    received = {node: [] for node in nodes}
    for source in nodes:
        if graph[source]:
            share = alpha * ranks[source] / len(graph[source])
            for target in graph[source]:
                received[target].append(share)
    return {node: base + math.fsum(received[node]) for node in nodes}


def pagerank(graph, alpha=0.5, tolerance=1e-13, max_iter=1000):
    graph = validated_graph(graph)
    if type(alpha) not in (int, float) or not 0 <= alpha < 1 or not math.isfinite(alpha):
        raise ValueError('alpha')
    if type(tolerance) not in (int, float) or not 0 < tolerance <= 1 or not math.isfinite(tolerance):
        raise ValueError('tolerance')
    if type(max_iter) is not int or not 1 <= max_iter <= 10000:
        raise ValueError('max_iter')
    ranks = {node: 1 / len(graph) for node in graph}
    for iteration in range(1, max_iter + 1):
        following = _step(graph, ranks, alpha)
        delta = math.fsum(abs(following[node] - ranks[node]) for node in graph)
        residual = math.fsum(abs(value - following[node])
                             for node, value in _step(graph, following, alpha).items())
        if residual <= tolerance:
            return {'ranks': following, 'iterations': iteration,
                    'successive_step_l1': delta, 'fixed_point_residual_l1': residual,
                    'dangling_nodes': [node for node in graph if not graph[node]]}
        ranks = following
    raise ValueError('not_converged')


def exact_linear_oracle(graph, alpha):
    """Fraction Gaussian elimination of (I-alpha*P^T)x=(1-alpha)/n.

    Independent of iteration/step; inputs are already known-valid fixtures.
    """
    nodes = sorted(graph)
    n = len(nodes)
    rows = []
    for target in nodes:
        coefficients = []
        for source in nodes:
            if not graph[source]:
                probability = Fraction(1, n)
            else:
                probability = Fraction(int(target in graph[source]), len(graph[source]))
            coefficients.append(Fraction(int(source == target)) - alpha * probability)
        rows.append(coefficients + [(1 - alpha) / n])
    for column in range(n):
        pivot = next(r for r in range(column, n) if rows[r][column])
        rows[column], rows[pivot] = rows[pivot], rows[column]
        scale = rows[column][column]
        rows[column] = [value / scale for value in rows[column]]
        for r in range(n):
            if r != column:
                scale = rows[r][column]
                rows[r] = [left - scale * right
                           for left, right in zip(rows[r], rows[column])]
    return {node: rows[i][-1] for i, node in enumerate(nodes)}


def rejected(call, message):
    try:
        call()
    except ValueError as error:
        return str(error) == message
    return False


def close_map(left, right, tolerance=2e-12):
    return left.keys() == right.keys() and all(abs(left[k] - float(right[k])) <= tolerance for k in left)


def run_example():
    graph = {'A': ['B', 'C'], 'B': ['C'], 'C': ['A'], 'D': []}
    before = deepcopy(graph)
    result = pagerank(graph)
    first = _step(validated_graph(graph), dict.fromkeys(graph, 0.25), 0.5)
    hand_first = {'A': 9/32, 'B': 7/32, 'C': 11/32, 'D': 5/32}
    hand_exact = {'A': Fraction(28, 91), 'B': Fraction(20, 91),
                  'C': Fraction(30, 91), 'D': Fraction(13, 91)}
    exact = exact_linear_oracle(graph, Fraction(1, 2))
    reverse = {node: [] for node in graph}
    for source, targets in graph.items():
        for target in targets:
            reverse[target].append(source)
    reversed_result = pagerank(reverse)
    renamed = {'A': 'K', 'B': 'M', 'C': 'J', 'D': 'L'}
    relabeled = {renamed[node]: [renamed[t] for t in outgoing]
                 for node, outgoing in graph.items()}
    relabeled_ranks = pagerank(relabeled)['ranks']
    small_cases = 0
    small_ok = True
    for bits in product([False, True], repeat=4):
        sample = {'A': [], 'B': []}
        for enabled, (source, target) in zip(bits, product(['A', 'B'], repeat=2)):
            if enabled:
                sample[source].append(target)
        for alpha in [Fraction(1, 4), Fraction(1, 2), Fraction(3, 4)]:
            observed = pagerank(sample, float(alpha))['ranks']
            small_ok &= close_map(observed, exact_linear_oracle(sample, alpha))
            small_cases += 1
    recomputed = _step(validated_graph(graph), result['ranks'], 0.5)
    actual_residual = math.fsum(abs(recomputed[k] - result['ranks'][k]) for k in graph)
    reordered = {'D': [], 'C': ['A'], 'B': ['C'], 'A': ['C', 'B']}
    invalid_graphs = [({}, 'graph'), ([], 'graph'), ({'A': 'B'}, 'edges'),
                      ({'A': ['B']}, 'edges'), ({'A': ['A', 'A']}, 'edges'),
                      ({True: []}, 'node'), ({'A/': []}, 'node'),
                      ({'A': [None]}, 'edges'),
                      ({str(i): [] for i in range(9)}, 'graph')]
    checks = {
      'hand_first_iteration_with_dangling_mass': first == hand_first,
      'hand_stationary_fractions_and_direct_oracle': exact == hand_exact and close_map(result['ranks'], hand_exact),
      'probability_mass_and_positive_values': (abs(math.fsum(result['ranks'].values()) - 1) < 1e-14
                                                 and all(value > 0 for value in result['ranks'].values())),
      'reported_residual_is_actual_Tx_minus_x': actual_residual == result['fixed_point_residual_l1'] <= 1e-13,
      'all_dangling_nodes_remain_uniform': close_map(pagerank({'A': [], 'B': [], 'C': []})['ranks'], dict.fromkeys(['A', 'B', 'C'], Fraction(1, 3))),
      'single_dangling_node_has_mass_one': pagerank({'A': []})['ranks'] == {'A': 1.0},
      'directed_cycle_uniform_fixed_point': pagerank({'A': ['B'], 'B': ['C'], 'C': ['A']})['ranks'] == dict.fromkeys(['A', 'B', 'C'], 1/3),
      'zero_alpha_discards_graph_structure': pagerank(graph, alpha=0)['ranks'] == dict.fromkeys(graph, 0.25),
      'self_loop_with_incoming_has_hand_solution': close_map(pagerank({'A': ['A'], 'B': ['A']})['ranks'], {'A': Fraction(3, 4), 'B': Fraction(1, 4)}),
      'dangling_redistribution_preserves_first_step_mass': math.fsum(first.values()) == 1 and result['dangling_nodes'] == ['D'],
      'reversing_edges_changes_structural_scores': abs(reversed_result['ranks']['A'] - result['ranks']['A']) > 1e-3,
      'renaming_preserves_corresponding_scores': all(abs(result['ranks'][k] - relabeled_ranks[renamed[k]]) < 1e-13 for k in graph),
      'independent_fraction_linear_oracle_small_graphs': small_cases == 48 and bool(small_ok),
      'invalid_graph_shapes_and_edges_reject': all(rejected(lambda g=g: pagerank(g), error) for g, error in invalid_graphs),
      'invalid_alpha_and_nonfinite_reject': all(rejected(lambda a=a: pagerank(graph, alpha=a), 'alpha') for a in [-1, 1, True, '0.5', float('nan'), float('inf'), 10**1000]),
      'invalid_tolerance_and_iteration_bounds_reject': (all(rejected(lambda t=t: pagerank(graph, tolerance=t), 'tolerance') for t in [0, -1, 2, True, float('nan')])
          and all(rejected(lambda m=m: pagerank(graph, max_iter=m), 'max_iter') for m in [0, 10001, True, 1.0])),
      'finite_iteration_failure_not_reported_converged': rejected(lambda: pagerank(graph, tolerance=1e-16, max_iter=1), 'not_converged'),
      'input_unchanged_and_order_invariant': graph == before and pagerank(reordered) == result,
    }
    assert len(checks) == 18 and all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
            'scope': 'Tiny synthetic unweighted directed graph, uniform teleportation/dangling redistribution; no Google implementation, SEO or relevance claim',
            'results': {'graph': graph, 'alpha': 0.5, 'absolute_residual_tolerance': 1e-13,
                        'first_step_hand': first, 'stationary_hand_exact': {k: str(v) for k, v in hand_exact.items()},
                        'solution': result, 'small_graph_cases_inside_one_group': small_cases},
            'checks': checks}


if __name__ == '__main__':
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

معیار توقف ما جمع قدرمطلق مؤلفه‌های T(x) منهای x است؛ T همان یک گام مدل و x بردار خروجیِ کاندید است. این باقیماندهٔ نقطهٔ ثابت با اختلاف دو تکرار قبلی یکی نیست. هر دو عدد با نام جدا ثبت می‌شوند. با آستانهٔ مطلق ده به توان منفی سیزده، نمونه پس از بیست‌وهفت به‌روزرسانی متوقف شد؛ باقیمانده حدود ۸٫۷۵ ضرب در ده به توان منفی چهارده است.

{
  "python": "3.14.5",
  "dependencies": "Python standard library only",
  "scope": "Tiny synthetic unweighted directed graph, uniform teleportation/dangling redistribution; no Google implementation, SEO or relevance claim",
  "results": {
    "graph": {
      "A": [
        "B",
        "C"
      ],
      "B": [
        "C"
      ],
      "C": [
        "A"
      ],
      "D": []
    },
    "alpha": 0.5,
    "absolute_residual_tolerance": 1e-13,
    "first_step_hand": {
      "A": 0.28125,
      "B": 0.21875,
      "C": 0.34375,
      "D": 0.15625
    },
    "stationary_hand_exact": {
      "A": "4/13",
      "B": "20/91",
      "C": "30/91",
      "D": "1/7"
    },
    "solution": {
      "ranks": {
        "A": 0.3076923076922727,
        "B": 0.21978021978025475,
        "C": 0.32967032967032966,
        "D": 0.14285714285714285
      },
      "iterations": 27,
      "successive_step_l1": 3.4985903063500245e-13,
      "fixed_point_residual_l1": 8.748557434046234e-14,
      "dangling_nodes": [
        "D"
      ]
    },
    "small_graph_cases_inside_one_group": 48
  },
  "checks": {
    "hand_first_iteration_with_dangling_mass": true,
    "hand_stationary_fractions_and_direct_oracle": true,
    "probability_mass_and_positive_values": true,
    "reported_residual_is_actual_Tx_minus_x": true,
    "all_dangling_nodes_remain_uniform": true,
    "single_dangling_node_has_mass_one": true,
    "directed_cycle_uniform_fixed_point": true,
    "zero_alpha_discards_graph_structure": true,
    "self_loop_with_incoming_has_hand_solution": true,
    "dangling_redistribution_preserves_first_step_mass": true,
    "reversing_edges_changes_structural_scores": true,
    "renaming_preserves_corresponding_scores": true,
    "independent_fraction_linear_oracle_small_graphs": true,
    "invalid_graph_shapes_and_edges_reject": true,
    "invalid_alpha_and_nonfinite_reject": true,
    "invalid_tolerance_and_iteration_bounds_reject": true,
    "finite_iteration_failure_not_reported_converged": true,
    "input_unchanged_and_order_invariant": true
  }
}

هجده گروه بررسی شامل پاسخ دستی، حفظ جرم، گراف چرخه‌ای، همهٔ گره‌های بی‌خروجی، حلقهٔ خودی، تغییر جهت، تغییر نام و ترتیب ورودی‌اند. مقایسهٔ چهل‌وهشت حالت گراف دوگرهی با پاسخ خطی مستقل فقط یک گروه است. گراف یک تا هشت گره دارد؛ مقصد ناشناخته، پیوند تکراری، پارامتر نامتناهی و نوع bool رد می‌شوند. شکست سقف تکرار خطا می‌دهد و نتیجهٔ ظاهراً همگرا برنمی‌گرداند.

۵. تفسیر نتیجه و چهار پرسش پاسخ‌دار

معیار API در NetworkX، آستانهٔ وابسته به تعداد گره‌ها دارد؛ معیار مطلق این کد را نباید همان tol آن API دانست. باقیماندهٔ کوچکِ محاسبهٔ شناور نیز گواه دقیقِ خطای واقعی نیست. برای همین گراف، پاسخ کسری امکان مقایسهٔ مستقل می‌دهد؛ چنین مرجعی برای گراف بسیار بزرگ به این سادگی در دسترس نیست. اعداد این تمرین پیشنهاد طراحی پیوند سایت نیستند.

پرسش اول: چرا سهم A مستقیماً و کامل به B نمی‌رسد؟ پاسخ: A دو خروجی دارد؛ بخش پیوندیِ سهمش به دو قسمت برابر تقسیم می‌شود. مقصد دیگر C است و ضریب alpha هم فقط بخش دنبال‌کردن پیوند را تعیین می‌کند.

پرسش دوم: اگر D را از پخش سهم حذف کنیم چه می‌شود؟ پاسخ: با همان تعریف، جرم احتمال گم می‌شود. حذف کامل گره نیز گراف دیگری با تعداد گرهٔ متفاوت می‌سازد؛ هر دو تغییر باید آشکار باشند و جای قرارداد بازتوزیع را نمی‌گیرند.

پرسش سوم: آیا یک تکرار با سقف بسیار کم، خروجی قابل قبول می‌دهد؟ پاسخ: فقط اگر معیار اعلام‌شده برقرار شود. در آزمونِ یک گام با آستانهٔ سخت، برنامه not_converged می‌دهد؛ رسیدن به سقف را موفقیت حساب نمی‌کند.

پرسش چهارم: آیا بزرگ‌ترین سهم، بهترین پاسخ جست‌وجوست؟ پاسخ: چنین نتیجه‌ای نداریم؛ مدل حتی متن پرسش را ندیده است. منابع در ۲۴ مهر ۱۴۰۵ خوانده شدند؛ مقالهٔ اصلی مربوط به ۱۹۹۸ و مرجع نرم‌افزاری نسخهٔ 3.7 است. این آموزش پایهٔ عددی، بدون ادعای خبر تازه، رتبهٔ واقعی یا اجرای NetworkX منتشر می‌شود.

منابع و مطالعهٔ بیشتر

• Brin و Page؛ مقالهٔ اصلی Anatomy، نسخهٔ ناشر میزبانی‌شده در Stanford
• Google Research؛ مشخصات انتشار مقالهٔ Anatomy
• NetworkX3.7؛ تعریف pagerank، گره بدون خروجی و معیار تکرار

بررسی منابع: ۲۴ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.