Pagerank

グラフの基礎知識

• ノード(node): ネットワークの頂点
• リンク(link): ネットワークの頂点と頂点を結ぶ線
• 有向グラフ(directed graph): リンクのつながりに方向があるグラフ
  • ex) Twitterのフォロー関係
• 無向グラフ(undirected graph): リンクのつながりに方向がないグラフ
  • ex) Facebookの友人関係
• グラフ構造の値: 各ノードとリンクは値を持つことができる
  • ex) 地点Aの人口
  • ex) 地点Aから地点Bまでの距離

ex) 3つのノードを持つ有向グラフ

 <------------,
1<----,       |
└─ -> 2 <--> 3

nodes: {1, 2, 3}
links: { 1: {2}, 2: {1, 3}, 3: {1, 2}}
adjacencyList(matrix):
 {1: {1: 0,   2: 1,   3: 0},
  2: {1: 0.5, 2: 0,   3: 0.5}
  3: {1: 0.5, 2: 0.5, 3: 0}}

	1	2	3
1	0	1	0
2	1/2	0	1/2
3	1/2	1/2	0

Map / Reduce

Pagerankは、ひとつ前の状態S(t)から状態S(t + 1)が求められるという、 マルコフ連鎖仮定を置いている。
t -> t + 1をシミュレーションするにあたって、
Pagerankは２つのstepに分けて計算される。

• Step1
  • Nodeのランク値を、リンクがつながっているNode数で割ってわりふる
• Step2
  • 割り振られたランク値をすべて足しあわせて、Nodeの新しいランク値とする