PageRank——1998年，为什么一个网页的重要性，取决于哪些网页指向了它？

computer science

A = 0.10
B = 0.40
C = 0.30
D = 0.20

A → B
A → D
B → C
C → B
D → 无出链

A 的 PageRank = 0.20

A → B
A → C

(B, 0.10)
(C, 0.10)

(B, 0.10)
(B, 0.07)
(B, 0.15)

B → [0.10, 0.07, 0.15]

def pagerank(
    graph,
    damping=0.85,
    tolerance=1e-10,
    max_iterations=1000,
):
    if not 0 < damping < 1:
        raise ValueError("damping must be between 0 and 1")

    # 包含那些只被链接、没有单独列出的网页
    nodes = sorted(
        set(graph)
        | {
            target
            for targets in graph.values()
            for target in targets
        }
    )

    if not nodes:
        return {}, 0

    n = len(nodes)

    # 删除重复出链，并为悬挂节点保留空列表
    links = {
        node: list(dict.fromkeys(graph.get(node, [])))
        for node in nodes
    }

    # 初始均匀分布
    rank = {
        node: 1.0 / n
        for node in nodes
    }

    for iteration in range(1, max_iterations + 1):

        # 所有悬挂节点的概率质量
        dangling_mass = sum(
            rank[node]
            for node in nodes
            if not links[node]
        )

        # 均匀随机跳转 + 悬挂质量均匀分配
        base = (
            (1.0 - damping) / n
            + damping * dangling_mass / n
        )

        new_rank = {
            node: base
            for node in nodes
        }

        # 沿真实出链传播 PageRank
        for source in nodes:
            targets = links[source]

            if not targets:
                continue

            contribution = (
                damping
                * rank[source]
                / len(targets)
            )

            for target in targets:
                new_rank[target] += contribution

        # L1 差：连续两轮的变化
        error = sum(
            abs(new_rank[node] - rank[node])
            for node in nodes
        )

        rank = new_rank

        if error < tolerance:
            return rank, iteration

    raise RuntimeError(
        "PageRank did not converge within max_iterations"
    )

graph = {
    "A": ["B", "D"],
    "B": ["C"],
    "C": ["B"],
    "D": [],
}

ranks, iterations = pagerank(graph)

for page, score in sorted(
    ranks.items(),
    key=lambda item: item[1],
    reverse=True,
):
    print(page, round(score, 4))

print("Total:", round(sum(ranks.values()), 6))
print("Iterations:", iterations)

import networkx as nx

G = nx.DiGraph()

G.add_nodes_from(graph)

for source, targets in graph.items():
    for target in targets:
        G.add_edge(source, target)

reference = nx.pagerank(
    G,
    alpha=0.85,
    tol=1e-12,
)

print(reference)