PageRank：Google を作ったグラフ中心性アルゴリズムを Python で再現

import numpy as np
def pagerank(adj, d=0.85, max_iter=100, tol=1e-9):    '''    adj: N x N の隣接行列 (adj[i][j]=1 なら i → j のリンク)    '''    N = len(adj)    # 行ごとに正規化 (確率行列にする)    out_deg = adj.sum(axis=1, keepdims=True)    out_deg[out_deg == 0] = 1  # dangling node 対策    M = adj / out_deg
    # 初期化    r = np.ones(N) / N
    # Power Iteration    for it in range(max_iter):        r_new = (1 - d) / N + d * M.T @ r        if np.abs(r_new - r).sum() < tol:            print(f'収束: {it+1} 反復')            break        r = r_new
    return r_new
# 5 ページのウェブ# A → B, A → C# B → C# C → A, C → D# D → E# E → Aadj = np.array([    [0, 1, 1, 0, 0],  # A    [0, 0, 1, 0, 0],  # B    [1, 0, 0, 1, 0],  # C    [0, 0, 0, 0, 1],  # D    [1, 0, 0, 0, 0],  # E], dtype=float)
ranks = pagerank(adj)labels = ['A', 'B', 'C', 'D', 'E']ranked = sorted(zip(labels, ranks), key=lambda x: -x[1])print('\nPageRank ランキング:')for name, r in ranked:    print(f'  {name}: {r:.4f}')
# 実機実行結果 (例):# A: 0.278  ← C と E からリンクされて高い# C: 0.274  ← A と B からリンクされて高い# E: 0.154# B: 0.148# D: 0.146

import networkx as nx
# 同じグラフを NetworkX でG = nx.DiGraph()edges = [('A','B'), ('A','C'), ('B','C'),         ('C','A'), ('C','D'), ('D','E'), ('E','A')]G.add_edges_from(edges)
ranks = nx.pagerank(G, alpha=0.85)for n, r in sorted(ranks.items(), key=lambda x: -x[1]):    print(f'  {n}: {r:.4f}')