今回は、ページランク(PageRank)という指標について紹介します。
これは、Webページの重要度を決定するために作られた指標で、Googleの創業者のラリー・ペイジとセルゲイ・ブリンによって発明されました。
参考: Brin, S. and Page, L. (1998) The Anatomy of a Large-Scale Hypertextual Web Search Engine.
基本的に、次の条件を満たすページが重要である、という考えを元にしています。
1. 多くのページからリンクされている。
2. 重要なページからリンクされている。
3. リンク先を厳選したページからリンクされている。
これの、1.と2.が、前の記事で紹介した、固有ベクトル中心性に似ています。
そして、PageRankのアルゴリズム自体は固有ベクトル中心性を改善して作られています。
その際に、3.を実装しただけでなく、元の固有ベクトル中心性を有向グラフに適用した時に発生する
入力エッジがないノードに対する対応や、出力エッジがない行き止まりのノードに対する対応などが改善されています。
具体的には、グラフの隣接行列を次のように改良した Google行列を使って、固有ベクトル中心性と同じ操作を行います。
以下の説明ですが、紹介しているサイトによって、行と列が逆なので実験の際はご注意ください。
このページでは networkxで得られる隣接行列を使うので、
ノードiからノードjにエッジが伸びている時に(i, j)成分が1になる隣接行列を使います。
(1) 隣接行列の各行の値を合計値で割り、各行の値の合計を1にする。
(2) どこにも遷移先がないノードからは、任意のノードに等確率で遷移するものとする。
つまり、隣接行列の行ベクトルのうち、全ての値が0の行は、$1/(ノード数)$で埋める。
(3) ある一定確率$1-\alpha$、(通常は15%)で、隣接行列に関わらず、グラフ中のどれかのノードにランダムに移動する。
つまり、元の隣接行列に(1)(2)を施したものを$\mathbf{A}$、全ての成分が$1$の同サイズの行列を$\mathbf{I}$、
グラフのノード数を$N$とすると、$\alpha \mathbf{A} + (1-\alpha)\mathbf{I}/N$ を考える。
これをGoogle行列と言うそうです。
Wikipedia – Google matrix
(行と列が逆なので注意。)
(1)により、 3. のリンク先を厳選したページからのリンクが重要視される性質が実装されます。
(どちらかというと、リンクを乱発しているページからのリンクが軽視される、と考えた方がわかりやすいです。)
そして、(2)により行き止まりの問題が解消され、(3)によって、グラフが連結でなくても相互に行き来できるようになります。
また、(2)、(3)のそれぞれにより、入力エッジがないノードも無視されずに済みます。
さて、固有ベクトル中心性を再帰的に計算した時、値がどんどん大きくなってしまうので毎回l2ノルムで正規化していたのを覚えているでしょうか。
非常に都合のいいことに、Google行列で同じ操作をしても、値が大きくなり続ける現象は発生せず、
値の合計値がそのまま一定に保たれます。
そのため、この後のサンプルコードでは、ポイントの合計値を$1/(ノード数)$で開始します。
さて、それでは実装です。
まずはランダムにグラフを生成し、隣接行列からGoogle行列の算出まで行いました。
import networkx as nx
import numpy as np
# ランダムにグラフを生成する
G = nx.random_graphs.fast_gnp_random_graph(
n=7,
p=0.3,
directed=True
)
# 隣接行列 (i番目からj番目のノードにパスがある時、(i, j)成分が1)
adj_matrix = nx.to_numpy_array(G)
print(adj_matrix)
"""
[[0. 1. 0. 0. 1. 0. 1.]
[0. 0. 1. 1. 1. 0. 1.]
[0. 1. 0. 0. 1. 0. 0.]
[0. 0. 0. 0. 1. 1. 0.]
[0. 1. 0. 1. 0. 0. 1.]
[0. 0. 1. 0. 0. 0. 0.]
[0. 0. 1. 0. 1. 1. 0.]]
"""
for i in range(adj_matrix.shape[0]):
if sum(adj_matrix[i]) != 0:
# 行の値の合計値を1に正規化する。
adj_matrix[i] /= sum(adj_matrix[i])
elif sum(adj_matrix[i]) == 0:
# 行の値が全て0の行は、1/Nで埋める。
adj_matrix[i] = 1/nx.number_of_nodes(G)
print(adj_matrix.round(2))
"""
[[0. 0.33 0. 0. 0.33 0. 0.33]
[0. 0. 0.25 0.25 0.25 0. 0.25]
[0. 0.5 0. 0. 0.5 0. 0. ]
[0. 0. 0. 0. 0.5 0.5 0. ]
[0. 0.33 0. 0.33 0. 0. 0.33]
[0. 0. 1. 0. 0. 0. 0. ]
[0. 0. 0.33 0. 0.33 0.33 0. ]]
"""
# Google行列の計算
N = nx.number_of_nodes(G)
alpha = 0.85
g_matrix = alpha*adj_matrix+(1-alpha)*np.ones(shape=adj_matrix.shape)/N
print(g_matrix)
"""
[[0.021 0.305 0.021 0.021 0.305 0.021 0.305]
[0.021 0.021 0.234 0.234 0.234 0.021 0.234]
[0.021 0.446 0.021 0.021 0.446 0.021 0.021]
[0.021 0.021 0.021 0.021 0.446 0.446 0.021]
[0.021 0.305 0.021 0.305 0.021 0.021 0.305]
[0.021 0.021 0.871 0.021 0.021 0.021 0.021]
[0.021 0.021 0.305 0.021 0.305 0.305 0.021]]
"""
Google 行列が求まったので、固有ベクトル中心性の時と同様に、
定数のベクトルに繰り返しかけて見ます。
# ページランクを1/Nで初期化する
page_rank = np.ones(shape=N)/N
print(page_rank.round(3))
# Google行列を繰り返し掛ける
for _ in range(30):
page_rank = page_rank@g_matrix
print(page_rank.round(3))
"""
[0.143 0.143 0.143 0.143 0.143 0.143 0.143]
[0.021 0.163 0.214 0.092 0.254 0.123 0.133]
[0.021 0.19 0.198 0.128 0.23 0.098 0.134]
-- (中略) --
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
"""
一定の値に収束していますね。これこそが掲題のPageRankです。
もちろんですが、networkxを使って計算することもできます。普段はこれを使いましょう。
numpyを使った実装と、scipyを使った実装、どちらも使っていないものの、3種類用意されています。
ドキュメントはこちら。
print(nx.pagerank_numpy(G))
"""
{0: 0.021428571428571422,
1: 0.17666594642678057,
2: 0.19229348384918474,
3: 0.12641130083513927,
4: 0.23802782043838958,
5: 0.11269014761536654,
6: 0.1324827294065679}
"""
また、最初のコード例の中で定義に沿ってGoogle行列を計算しましたが、グラフからGoogle行列を計算する関数も用意してくれています。
google_matrix
一応動かして結果が同じであることを見ておきましょう。
print(nx.google_matrix(G).round(3))
"""
[[0.021 0.305 0.021 0.021 0.305 0.021 0.305]
[0.021 0.021 0.234 0.234 0.234 0.021 0.234]
[0.021 0.446 0.021 0.021 0.446 0.021 0.021]
[0.021 0.021 0.021 0.021 0.446 0.446 0.021]
[0.021 0.305 0.021 0.305 0.021 0.021 0.305]
[0.021 0.021 0.871 0.021 0.021 0.021 0.021]
[0.021 0.021 0.305 0.021 0.305 0.305 0.021]]
"""
値は揃っていますね。 ただ、データ型が numpy.matrix なのでそこだけ注意しましょう。
(と言っても、numpy.arrayとの違いで困ることはほぼないのですが。)
最後に、このページランクですが、固有ベクトル中心性と同じように、
Google行列の固有ベクトルとしても計算できます。
固有ベクトルを求める前に、この記事の定義だと転置する必要があることと、
numpyの固有ベクトルはl2ノルムが1に正則化されているので、
l1ノルムが1になるようにスカラー倍してやる必要があることに注意が必要です。
実際にやってみます。
eigen_vector = np.abs(np.linalg.eig(g_matrix.T)[1][:, 0])
eigen_vector /= sum(eigen_vector)
print(eigen_vector.round(3))
# [0.021 0.177 0.192 0.126 0.238 0.113 0.132]
ご覧の通り、再帰的に求めたPageRank,ライブラリで求めたPageRankと一致しました。
もともと、Webページの重要度を測るために考案されたものですが、
世の中には有向グラフの構造を持つデータは意外に多く、
その各ノードの重要度を測りたい場面というのは頻繁にあるので、活用の場面はたくさんあります。