第二十一章PageRank算法PageRank算法•在实际应用中许多数据都以图（graph)的形式存在，比如，互联网、社交网络都可以看作是一个图•图数据上的机器学习具有理论与应用上的重要意义•PageRank算法是图的链接分析（linkanalysis）的代表性算法，属于图数据上的无监督学习方法。•PageRank可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。PageRank算法•PageRank算法的基本想法是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为•在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。•PageRank是递归定义的，PageRank的计算可以通过迭代算法进行。PageRank的定义基本想法•历史上，PageRank算法作为计算互联网网页重要度的算法被提出•PageRank是定义在网页集合上的一个函数，它对每个网页给出一个正实数，表示网页的重要程度，整体构成一个向量•PageRank值越高，网页就越重要，在互联网搜索的排序中可能就被排在前面基本想法•假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程•假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链•PageRank表示这个马尔可夫链的平稳分布•每个网页的PageRank值就是平稳概率。基本想法•下图表示一个有向图，假设是简化的互联网例，结点A,B,C和D表示网页，结点之间的有向边表示网页之间的超链接，边上的权值表示网页之间随机跳转的概率基本想法•假设有一个浏览者，在网上随机游走•如果浏览者在网页A，•则下一步以1/3的概率转移到网页B,C和D•如果浏览者在网页B，•则下一步以1/2的概率转移到网页A和D•如果浏览者在网页C，•则下一步以概率1转移到网页A•如果浏览者在网页D，•则下一步以1/2的概率转移到网页B和C基本想法•直观上，一个网页，如果指向该网页的超链接越多，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要•一个网页，如果指向该网页的PageRank值越高，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要•PageRank值依赖于网络的拓扑结构，一旦网络的拓扑（连接关系）确定，PageRank值就确定基本想法•PageRank的计算可...
