ページランクアルゴリズムとPythonでの実装

PageRankアルゴリズムはウェブページに適用されます。ウェブページは有向グラフであり、有向グラフの二つの構成要素はノードとエッジです。ページはノードであり、ハイパーリンクはエッジです、つまり、二つのノード間の接続です。

PageRankを使用して、各ページの重要性を見つけることができます。それは正確です。PageRankの値は、0から1の間。

図中の単一のノードのPageRank値は、それと接続されているすべてのノードのPageRank値に依存しており、これらのノードは周期的に私たちがランクを付けたいノードに接続されています。PageRank値は収束反復法を使用して値に割り当てられます。

サンプルコード

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(np.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))

出力結果

[[0.333]
[0.217]
[0.45　]]
[[0.415]
[0.217]
[0.368]]
[[0.358]
[0.245]
[0.397]]
[[0.378]
[0.225]
[0.397]]
[[0.378]
[0.232]
[0.39　]]
[[0.373]
[0.232]
[0.395]]
[[0.376]
[0.231]
[0.393]]
[[0.375]
[0.232]
[0.393]]
[[0.375]
[0.231]
[0.394]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
[[0.375]
[0.231]
[0.393]]
最終:
[[0.375]
[0.231]
[0.393]]
sum　0.9999999999999951