PageRank Description
PageRank是对搜索引擎搜索结果的排序算法，根据谷歌的描述:
PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.
PageRank算法
出边迭代(Link value iteration)
谷歌在从网络上爬取一次网页数据就会重新计算
P
a
g
e
R
a
n
k
P a g e R a n k
和网页索引。
假设有四个web网页A, B, C和D组成的网络，忽略网页的自环边。将一个网页指向另一个网页的多条出边看作单独的一个link链接。所有网页的初始PageRank值相等，为了更好地展现概率，所有网页的初始PageRank和为1。这里有
P
R
(
A
)
=
P
R
(
B
)
=
P
R
(
C
)
=
P
R
(
D
)
P R ( A ) = P R ( B ) = P R ( C ) = P R ( D )
-
example 1:
如果图中只有B,C,D指向A的三条边，那么在第一次迭代后，网络中的三个节点都会向A传递
0.25
P
a
g
e
R
a
n
k
0.25 P a g e R a n k
，因此有
P
R
(
A
)
=
P
R
(
B
)
+
P
R
(
C
)
+
P
R
(
D
)
P R ( A ) = P R ( B ) + P R ( C ) + P R ( D )
，A的
P
a
g
e
R
a
n
k
P a g e R a n k
值因此变为0.75。 -
example 2:
假设B link to C和A，C link to A, D link to all three。因此B会向A传递1/2的
P
a
g
e
R
a
n
k
P a g e R a n k
，C向A传递1/1的
P
a
g
e
R
a
n
k
P a g e R a n k
值，D向A传递1/3的
P
a
g
e
R
a
n
k
P a g e R a n k
值，由此可得
P
R
(
A
)
=
P
R
(
B
)
2
+
P
R