Pythonで実装するPageRankアルゴリズム：仕組みからコード例まで徹底解説

PageRank（ページランク）アルゴリズムは、Googleの創業者であるラリー・ペイジとセルゲイ・ブリンによって考案された、Webページの重要度を評価するためのアルゴリズムです。本記事では、PageRankの基本的な考え方と、Pythonを使った具体的な実装方法をわかりやすく解説します。

PageRankアルゴリズムの基本概念

Webページの集合は「有向グラフ」として表現できます。有向グラフは「ノード（頂点）」と「接続（エッジ）」という2つの要素で構成されます。PageRankの世界では、各ページがノードに相当し、ページ間をつなぐハイパーリンクが接続に相当します。

PageRankを用いることで、各ページの重要度を数値化して求めることができます。PageRank値は確率として定義されるため、その値は必ず0から1の間に収まります。

PageRankの計算の仕組み

グラフ内のあるノードのPageRank値は、そのノードへリンクを張っているすべてのノードのPageRank値によって決まります。さらに、それらのノード自身も他のノードと循環的につながっているため、一度の計算で最終的な値を求めることはできません。

そこでPageRankでは、収束する反復計算を用いて各ノードの値を割り当てます。計算を繰り返すうちに値がほぼ変化しなくなった時点で、その値を最終的なPageRank値とみなします。

Pythonによる実装例

以下は、3つのページからなる小さなグラフに対してPageRankを計算するPythonコードです。NumPyによる行列演算を利用し、ダンピング係数β=0.7、初期値を1/3として設定しています。

import numpy as np
import scipy as sc
import pandas as pd
from fractions import Fraction

def display_format(my_vector, my_decimal):
    return np.round((my_vector).astype(float), decimals=my_decimal)

my_dp = Fraction(1, 3)
Mat = np.matrix([[0, 0, 1],
                 [Fraction(1, 2), 0, 0],
                 [Fraction(1, 2), 1, 0]])
Ex = np.zeros((3, 3))
Ex[:] = my_dp
beta = 0.7
Al = beta * Mat + ((1 - beta) * Ex)
r = np.matrix([my_dp, my_dp, my_dp])
r = np.transpose(r)
previous_r = r

for i in range(1, 100):
    r = Al * r
    print(display_format(r, 3))
    if (previous_r == r).all():
        break
    previous_r = r

print("Final:\n", display_format(r, 3))
print("sum", np.sum(r))

コードのポイント解説

• Mat： ページ間のリンク構造を表す遷移行列。Fractionクラスを使うことで分数を誤差なく保持しています。
• Ex： 全要素が1/3のテレポート（ランダムジャンプ）行列。リンクが極端に偏ったグラフでも計算が破綻しないようにする役割があります。
• beta = 0.7： ダンピング係数。実際にリンクをたどる確率を表し、残りの0.3はどのページにもランダムにジャンプする確率です。
• Al： 「Google行列」と呼ばれる最終的な遷移行列で、beta × Mat ＋ (1−beta) × Ex として求められます。
• forループ： r = Al × r を繰り返し適用し、前回の結果と完全に一致したらbreakで終了する収束判定を行っています。

実行結果

プログラムを実行すると、反復ごとのPageRank値が出力され、やがて値が収束していきます。以下は出力の一部です（途中の反復は省略しています）。

[[0.333]
 [0.217]
 [0.45 ]]
...
Final:
[[0.375]
 [0.231]
 [0.393]]
sum 0.9999999999999951

結果の読み方

最終的に、3つのページのPageRank値はそれぞれ約0.375、0.231、0.393へと収束しました。合計が約1.0になっていることからも、PageRank値が確率として妥当であることが確認できます。この例では3番目のページが最も高い重要度を持つことが示されています。

このように、PageRankはシンプルな行列演算と反復計算だけで実装でき、検索エンジンのランキング技術の基礎となる強力な手法です。ぜひ実際にコードを動かして、収束の様子を観察してみてください。