PageRankアルゴリズム
5321 ワード
最近机械の学习と高级なコンピュータのネットを准备して、すべてpagerankのアルゴリズムに出会って、ちょうど始まってあまり注意していないで、资料を调べて、やっとこれがラリーペッチのスタンフォード大学の中のオリジナルのアルゴリズムであることを発见して、やはりすごいで、感心しなければならなくて、私は同様に私の大华科の図书馆の秘蔵の本の中でこのアルゴリズムを见て本当に縁があったことを见て、以下は私の自分の见方を话して、もし间违いがあるならばまた大神达に许してもらいます!!!
PageRankの核心思想は2点ある:1.1つのページが他の多くのページにリンクされている場合は、このページが重要であることを示します.つまりpagerankの値が比較的高いことです. 2.pagerank値の高いページが他のページにリンクされている場合、リンクされたページのpagerank値はそれに応じて向上します.次はWikiPediaからの図で、各ボールは1つのページを表し、ボールの大きさはページのpagerank値の大きさを反映しています.ページBとページEへのリンクが多いため、BとEのpagerank値が高く、また、Cを指すページは少ないが、最も重要なページBがCを指すため、Cのpagerank値はEよりも大きい.
1.問題の背景
2.数学モデリング
ページ接続マトリクス$G$,マルコフプロセス(「ネットサーフィン」)は,転送マトリクス$A$,確率$p$がユーザが現在のページのリンクアドレスをクリックする確率(一般的に0.85)であることが理解できる.
最後に等式$Ax=x$が得られ、これは実際には行列$A$の特徴値が1である特徴ベクトルを求めることである.
以下の内容は円盤定理を用いて1が行列$A$の主な特徴値であることを説明するので,べき乗法を用いて解くことができる.
3.PageRankを解く
上の図の右側に示すようなウェブリンクモデルがあると仮定します.
(1)べき乗法
wikiには転移確率を考慮せずに反復的にすべてのページのpagerank値を更新するPagerankの簡便なアルゴリズムがあり、更新の方法は各ページのpagerank値を指向するすべてのページに均等に割り当て、各ページ累計はそのページを指向するすべての値をそのラウンドのpagerank値として均等に割り当てることである.すべてのページのpagerank値が収束するか、一定のしきい値条件を満たすまで停止します.
後のMapReduceフレームワークの下でPageRankアルゴリズムの実現はこの考えを採用した.遷移確率を考慮する場合,このアルゴリズムと同様に,1つの遷移確率に加えてランダムジャンプの確率を乗じる.
以上のように,以下のMatlabコード実装では各ページのPageRank値を得ることができる.
得られたベクトル$x$は、各ページのpagerank値を保存し、リンク数は同じであるが、ページ1は、ページ4およびページ5よりも高く、ページ2のpagerank値は、ページ1がその上にリンクされ、ページ1の光に相当するため、2番目に高い.
この文章はこのアルゴリズムの1つのPythonバージョンの実現を提供して、このブロガーはサードパーティのモジュールpython-graphを使って、python-graphモジュールは多くの図のアルゴリズムを実現して、このモジュールの使用例、使用する前に先にインストールする必要があって、コードは以下の通りです:
Pythonバージョンのアルゴリズム実装:
# coding=utf-8
# python-graph https://code.google.com/p/python-graph/
# Import graphviz
import graphviz as gv
# Import pygraph
from pygraph.classes.digraph import digraph
from pygraph.readwrite.dot import write
# Define pagerank function
def pagerank(graph, damping_factor=0.85, max_iterations=100,\
min_delta=0.00001):
"""
Compute and return the PageRank in an directed graph.
@type graph: digraph
@param graph: Digraph.
@type damping_factor: number
@param damping_factor: PageRank dumping factor.
@type max_iterations: number
@param max_iterations: Maximum number of iterations.
@type min_delta: number
@param min_delta: Smallest variation required for a new iteration.
@rtype: Dict
@return: Dict containing all the nodes PageRank.
"""
nodes = graph.nodes()
graph_size = len(nodes)
if graph_size == 0:
return {}
# value for nodes without inbound links
min_value = (1.0-damping_factor)/graph_size
# itialize the page rank dict with 1/N for all nodes
#pagerank = dict.fromkeys(nodes, 1.0/graph_size)
pagerank = dict.fromkeys(nodes, 1.0)
for i in range(max_iterations):
diff = 0 #total difference compared to last iteraction
# computes each node PageRank based on inbound links
for node in nodes:
rank = min_value
for referring_page in graph.incidents(node):
rank += damping_factor * pagerank[referring_page]/\
len(graph.neighbors(referring_page))
diff += abs(pagerank[node] - rank)
pagerank[node] = rank
print 'This is NO.%s iteration' % (i+1)
print pagerank
print ''
#stop if PageRank has converged
if diff < min_delta:
break
return pagerank
# Graph creation
gr = digraph()
# Add nodes and edges
gr.add_nodes(["1","2","3","4"])
gr.add_edge(("1","2"))
gr.add_edge(("1","3"))
gr.add_edge(("1","4"))
gr.add_edge(("2","3"))
gr.add_edge(("2","4"))
gr.add_edge(("3","4"))
gr.add_edge(("4","2"))
# Draw as PNG
# dot = write(gr)
# gvv = gv.readstring(dot)
# gv.layout(gvv,'dot')
# gv.render(gvv,'png','Model.png')
pagerank(gr)
32回の反復により得られた結果は、以下のようになり、前の結果と一致した.
This is NO.32 iteration {'1': 0.2675338708706491, '3': 0.13227261904986046, '2': 0.2524037902400518, '5': 0.062477242064127136, '4': 0.1697488529161491, '6': 0.1155828978186352}
PageRankの核心思想は2点ある:1.1つのページが他の多くのページにリンクされている場合は、このページが重要であることを示します.つまりpagerankの値が比較的高いことです. 2.pagerank値の高いページが他のページにリンクされている場合、リンクされたページのpagerank値はそれに応じて向上します.次はWikiPediaからの図で、各ボールは1つのページを表し、ボールの大きさはページのpagerank値の大きさを反映しています.ページBとページEへのリンクが多いため、BとEのpagerank値が高く、また、Cを指すページは少ないが、最も重要なページBがCを指すため、Cのpagerank値はEよりも大きい.
1.問題の背景
2.数学モデリング
ページ接続マトリクス$G$,マルコフプロセス(「ネットサーフィン」)は,転送マトリクス$A$,確率$p$がユーザが現在のページのリンクアドレスをクリックする確率(一般的に0.85)であることが理解できる.
最後に等式$Ax=x$が得られ、これは実際には行列$A$の特徴値が1である特徴ベクトルを求めることである.
以下の内容は円盤定理を用いて1が行列$A$の主な特徴値であることを説明するので,べき乗法を用いて解くことができる.
3.PageRankを解く
上の図の右側に示すようなウェブリンクモデルがあると仮定します.
(1)べき乗法
wikiには転移確率を考慮せずに反復的にすべてのページのpagerank値を更新するPagerankの簡便なアルゴリズムがあり、更新の方法は各ページのpagerank値を指向するすべてのページに均等に割り当て、各ページ累計はそのページを指向するすべての値をそのラウンドのpagerank値として均等に割り当てることである.すべてのページのpagerank値が収束するか、一定のしきい値条件を満たすまで停止します.
後のMapReduceフレームワークの下でPageRankアルゴリズムの実現はこの考えを採用した.遷移確率を考慮する場合,このアルゴリズムと同様に,1つの遷移確率に加えてランダムジャンプの確率を乗じる.
以上のように,以下のMatlabコード実装では各ページのPageRank値を得ることができる.
n=6;
i=[2 3 4 4 5 6 1 6 1];
j=[1 2 2 3 3 3 4 5 6];
G=sparse(i,j,1,n,n);
% Power method
for j = 1:n
L{j} = find(G(:,j));
c(j) = length(L{j});
end
p = .85;
delta = (1-p)/n;
x = ones(n,1)/n;
z = zeros(n,1);
cnt = 0;
while max(abs(x-z)) > .0001
z = x;
x = zeros(n,1);
for j = 1:n
if c(j) == 0
x = x + z(j)/n;%
else
x(L{j}) = x(L{j}) + z(j)/c(j);% pagerank
end
end
x = p*x + delta;
cnt = cnt+1;
end得られたベクトル$x$は、各ページのpagerank値を保存し、リンク数は同じであるが、ページ1は、ページ4およびページ5よりも高く、ページ2のpagerank値は、ページ1がその上にリンクされ、ページ1の光に相当するため、2番目に高い.
x =
0.2675
0.2524
0.1323
0.1698
0.0625
0.1156この文章はこのアルゴリズムの1つのPythonバージョンの実現を提供して、このブロガーはサードパーティのモジュールpython-graphを使って、python-graphモジュールは多くの図のアルゴリズムを実現して、このモジュールの使用例、使用する前に先にインストールする必要があって、コードは以下の通りです:
easy_install python-graph-core
easy_install python-graph-dotPythonバージョンのアルゴリズム実装:
# coding=utf-8
# python-graph https://code.google.com/p/python-graph/
# Import graphviz
import graphviz as gv
# Import pygraph
from pygraph.classes.digraph import digraph
from pygraph.readwrite.dot import write
# Define pagerank function
def pagerank(graph, damping_factor=0.85, max_iterations=100,\
min_delta=0.00001):
"""
Compute and return the PageRank in an directed graph.
@type graph: digraph
@param graph: Digraph.
@type damping_factor: number
@param damping_factor: PageRank dumping factor.
@type max_iterations: number
@param max_iterations: Maximum number of iterations.
@type min_delta: number
@param min_delta: Smallest variation required for a new iteration.
@rtype: Dict
@return: Dict containing all the nodes PageRank.
"""
nodes = graph.nodes()
graph_size = len(nodes)
if graph_size == 0:
return {}
# value for nodes without inbound links
min_value = (1.0-damping_factor)/graph_size
# itialize the page rank dict with 1/N for all nodes
#pagerank = dict.fromkeys(nodes, 1.0/graph_size)
pagerank = dict.fromkeys(nodes, 1.0)
for i in range(max_iterations):
diff = 0 #total difference compared to last iteraction
# computes each node PageRank based on inbound links
for node in nodes:
rank = min_value
for referring_page in graph.incidents(node):
rank += damping_factor * pagerank[referring_page]/\
len(graph.neighbors(referring_page))
diff += abs(pagerank[node] - rank)
pagerank[node] = rank
print 'This is NO.%s iteration' % (i+1)
print pagerank
print ''
#stop if PageRank has converged
if diff < min_delta:
break
return pagerank
# Graph creation
gr = digraph()
# Add nodes and edges
gr.add_nodes(["1","2","3","4"])
gr.add_edge(("1","2"))
gr.add_edge(("1","3"))
gr.add_edge(("1","4"))
gr.add_edge(("2","3"))
gr.add_edge(("2","4"))
gr.add_edge(("3","4"))
gr.add_edge(("4","2"))
# Draw as PNG
# dot = write(gr)
# gvv = gv.readstring(dot)
# gv.layout(gvv,'dot')
# gv.render(gvv,'png','Model.png')
pagerank(gr)
32回の反復により得られた結果は、以下のようになり、前の結果と一致した.
This is NO.32 iteration {'1': 0.2675338708706491, '3': 0.13227261904986046, '2': 0.2524037902400518, '5': 0.062477242064127136, '4': 0.1697488529161491, '6': 0.1155828978186352}