什么是网页挖掘中的页面排名算法?

PageRank 是一种客观、机械地对网页进行评级的方法,关注人的兴趣。网络搜索引擎必须与没有经验的客户和操纵传统排名服务的页面进行组织。一些计算网页可复制性质的评估方法不受操纵。

任务是利用 Web 的超链接结构来生成每个网页的全局重要性排名。此排名称为 PageRank。

Web 的机制依赖于一个包含大约 1.5 亿个节点(网页)和 17 亿条边(超链接)的图。如果网页 A 和 B 链接到页面 C,则 A 和 B 称为 C 的反向链接。通常,高度链接的页面更重要。因此他们有更多的反向链接,重要的反向链接数量较少。

例如,具有来自雅虎的单个反向链接的网页必须比具有来自未知或私有站点的多个反向链接的页面排名更高。如果一个网页的反向链接的总排名太大,那么它的排名就很高。

以下是 PageRank 的简化版:设 u,v 为网页。因此,设 Bu 是指向 u 的页面组。此外,让 Nv 是来自 v 的多个链接。让 c < 1 是标准化的一个因素。它可以描述一个简单的排名 R,这是对 PageRank 的简化解释 -

$$\mathrm{ R(u)\:=\:c\displaystyle\sum\limits_{u\in{Bu}}\frac{ R(v)}{N_v}}$$

页面的排名在其前向连接之间平均分配,以提供给他们标记的页面的排名。该方程是递归的,但这个简化函数存在问题。

如果两个网页相互指向,但没有其他网页,而其他网页指向其中一个网页,则在迭代过程中会产生循环。这个循环将组装排名,但永远不会共享任何排名。这种由没有外边的图中的循环形成的陷阱称为秩汇。

Page Rank 算法首先将数据库中的每个 URL 转换为一个数字。下一阶段是使用整数 ID 将每个超链接保存在数据库中以识别网页。在按父 ID 对链接结构进行排序并删除悬空链接后,将启动迭代。

必须选择最佳初始分配以加速收敛。当前时间步的权重保存在内存中,之前的权重在磁盘上以线性时间访问。在权重收敛后,悬空连接被插入回来并重新计算排名。计算实现得很好,但可以通过放宽收敛标准和使用更有效的优化方法来加快计算速度。