古典ランダムウォークと隣接行列 (PageRankとPersonalized PageRank)

概要

この記事では、古典ランダムウォークと隣接行列の概念を中心に、PageRankとPersonalized PageRankについて解説する。これらのアルゴリズムの定義や性質、具体的な応用例を数式とPythonのコードを用いて示し、企業のエンジニアがどのように利用できるかを説明する。

ソースコード

github

  • jupyter notebook形式のファイルはこちら

google colaboratory

  • google colaboratory で実行する場合はこちら

実行環境

OSはmacOSである。LinuxやUnixのコマンドとはオプションが異なることに注意。

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

pandasのテーブルを見やすいようにHTMLのテーブルにCSSの設定を行う。

基本的なライブラリをインポートし watermark を利用してそのバージョンを確認する。 ついでに乱数のseedの設定を行う。

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import random

import scipy
import numpy as np

import matplotlib
import matplotlib.pyplot as plt

seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)


from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

matplotlib: 3.8.1
numpy     : 1.25.2
scipy     : 1.11.2

Watermark: 2.4.3

古典ランダムウォーク

定義

ランダムウォークは、グラフ上でランダムに次のノードへ移動するプロセスである。グラフ $\mathbf{G}$ はノード集合 $\mathbf{V}$ とエッジ集合 $\mathbf{E}$ で構成される。エッジ集合は隣接行列 $\mathbf{A}$ で表される。隣接行列 $\mathbf{A}$ の要素 $\mathbf{A}_{ij}$ は、ノード $i$ からノード $j$ へのエッジが存在する場合に1、そうでない場合に0である。

$$ \mathbf{A} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix} $$

ランダムウォークの遷移行列

ランダムウォークの遷移行列 $\mathbf{P}$ は、隣接行列 $\mathbf{A}$ に基づいて定義される。遷移行列 $\mathbf{P}$ の要素 $\mathbf{P}_{ij}$ は、ノード $i$ からノード $j$ への遷移確率を表す。

$$ \mathbf{P}_{ij} = \frac{a_{ij}}{\sum_{k} a_{ik}} $$

ランダムウォークの性質

ランダムウォークの重要な性質として、定常状態に収束するが挙げられる。ランダムウォークが十分に長い時間を経過すると、ノードの訪問確率は一定値に収束する。

PageRankにおける収束性についてはGoogle行列とPageRank を参照のこと。

PageRank

数式による表現

PageRankは以下のように定義される。$ \mathbf{PR}(i) $ はノード $ i $ のPageRankを表す。

$$ \mathbf{PR}(i) = \frac{1-d}{N} + d \sum_{j \in \mathbf{M}(i)} \frac{\mathbf{PR}(j)}{\mathbf{L}(j)} $$

ここで、$ \mathbf{M}(i) $ はノード $ i $ へリンクするノードの集合、$ \mathbf{L}(j) $ はノード $ j $ からのリンク数、$ d $ はダンピングファクター（通常は0.85）、$ N $ はノードの総数である。

Pythonによる実装例

以下に、Pythonを用いたPageRankの実装例を示す。

定常状態は反復法を用いて導出する。

import numpy as np

# ダンピングファクター
d = 0.85

# 隣接行列
A = np.array([[0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [1, 0, 1, 0]])

# ノード数
N = A.shape[0]

# 初期PageRankベクトル
PR = np.ones(N) / N

# 遷移行列の計算
P = A / A.sum(axis=0)

# PageRankの反復計算
# 反復法で定常状態を求める
for _ in range(100):
    PR = (1 - d) / N + d * P.dot(PR)

print(np.round(PR, 2))

[0.29 0.21 0.26 0.24]

Personalized PageRank

Personalized PageRankの定義

Personalized PageRankは、特定のノードに重点を置いてPageRankを計算するアルゴリズムである。特定のユーザーやアイテムに関連するノードの重要度を評価する場合に有用である。

数式による表現

Personalized PageRankは、基本的なPageRankの数式を拡張したものである。特定のノード集合 $\mathbf{S}$ に対して、以下のように定義される。

$$ \mathbf{PPR}(i) = \frac{1-d}{N} + d \sum_{j \in \mathbf{M}(i)} \frac{\mathbf{PPR}(j)}{\mathbf{L}(j)} + \alpha \mathbf{e}_S(i) $$

ここで、$\alpha$ はパーソナライズ度合いを調整するパラメータ、$\mathbf{e}_S(i)$ はノード $i$ がパーソナライズされた集合 $\mathbf{S}$ に含まれるかどうかを示す指示関数である。

Pythonによる実装例

以下に、Pythonを用いたPersonalized PageRankの実装例を示す。

定常状態は反復法を用いて導出する。

# パーソナライズ度合い
alpha = 0.1

# パーソナライズされたノード集合
S = {0}

# 初期PageRankベクトル
PPR = np.ones(N) / N

# Personalized PageRankの反復計算
# 反復法で定常状態を求める
for _ in range(100):
    PPR = (1 - d) / N + d * P.dot(PPR) + alpha * np.isin(np.arange(N), list(S))

print(np.round(PPR, 2))

[0.53 0.32 0.43 0.38]

メリットとデメリット

メリット

  1. 効率的な重要度評価: ランダムウォークベースのアルゴリズムは、ノードの重要度を効率的に評価できる。
  2. 適用範囲の広さ: PageRankとPersonalized PageRankは、Webページのランキングから推薦システムまで広範囲に適用可能。

デメリット

  1. 計算コスト: 大規模グラフに対しては、計算コストが高くなることがある。
  2. パラメータ調整: ダンピングファクターやパーソナライズ度合いの調整が必要。

結論

この記事では、古典ランダムウォークと隣接行列の概念を用いて、PageRankとPersonalized PageRankについて解説した。これらのアルゴリズムは、Webページのランキングや推薦システムにおいて非常に有用である。Pythonによる具体的な実装例を通じて、その利用方法を示し、企業や研究者がどのように応用できるかを説明した。

参考文献