Skip to content

网页排序

Jump to bottom
Conghuai Cai edited this page Mar 25, 2018 · 3 revisions

如果把互联网上的网页当做节点，网页间的链接关系当做边，那么这些节点和边将会构成一个有向图，如果我们的爬虫程序要把与某个网页相关联的网页都爬取下来（类似于搜索引擎的功能），我们可以采用广度优先或者深度优先的策略来遍历这个图，再遍历完之后，我们会得到一个网页集合，但是如何去对这些网页进行排序呢？这是很多搜索引擎需要解决的问题。 网页排序的算法主要有两种：

  • HITS(Hypertext Induced Topic Search)
  • PageRank

PageRank

构建网页图结构

PageRank算法的第一步是构建网页图结构，web page代表节点，hyperlinks代表边：

定义节点的重要性

有了图结构之后，我们需要定义每个page的重要性，我们可以通过指向该网页的超链接来判断，越重要的网页，它接收到的超链接越多。当然了， 我们需要一种形式化的定义：$PR(A) = (1-d)+d(\frac{PR(T_1)}{C(T_1)}+\frac{PR(T_2)}{C(T_2)}+...+\frac{PR(T_N)}{C(T_N)})$

  • $PR(A)$ ：A网页的PageRank值（PR值越高，该网页越重要）。
  • d ：0~1之间的值，后面会说明为什么会加这个值。
  • $PR(T_1), PR(T_2), ..., PR(T_N)$ ：指向A网页的PR值。
  • $C(T_1), C(T_2), ..., C(T_N)$ ：指向A网页的网页的out links数目。

算法过程

  1. 初始化，一开始所有网页的PR值都是 $\frac{1}{N}$
  2. 迭代直到收敛，$PR_{t+1}(P_i) = \sum_{P_j}\frac{PR_t(P_j)}{C(P_j)}$，其中$P_j$为指向$P_i$的网页。

例子

当然，我们也可以用矩阵来表示这一过程，令转移矩阵为$H$，$H_{(.,j)}$列表示网页j的链接情况:

PageRank存在的问题

Clone this wiki locally