❝论文标题 ｜ Object-Level Ranking: Bringing Order to Web Objects
论文来源 ｜ WWW 2005
论文链接 ｜ http://www.ra.ethz.ch/CDstore/www2005/docs/p567.pdf
源码参考 ｜ https://github.com/TommyCpp/nx-poprank
❞
TL;DR
网页检索的主要任务是按照应答用户查询的相关性和流行度对相关对象进行排名。由于不同网页对象间存在不同的关系类型，传统的 PageRank 模型在计算对象的流行度（Popularity）时不再有效。本文提出一种对特殊域中对象级排名的链接分析模型，明确的对每种的对象关系分配一个流行度传播因子（PPF，Popularity Propagation Factor），研究不同种类关系的不同 PPF 如何影响网页对象的流行度排名，同时提出一种自动搜索 PPF 的方法。
Algorithm/Model
网页链接构成的图称为网页图，这种图为同质图且算法 PageRank 和 HITS 可以通过分析链接来对网页进行排序。网页中不同种类的对象通过相互联系形成了对象图，由于图中包含不同对象及其不同的关系，明显 PageRank 算法不适用且未考虑对象间关系的影响，例如 Author 多的 Paper 其流行度不一定高。网页对象图如下所示：
文章中提出一种综合考虑对象的网页流行度和对象间关系的计算网页对象流行分数的排序算法 PopRank。该方法是对 PageRank 算法的扩展，通过给不同种类的链接关系分配一个 PPF。如上图的文献对象关系图所示，需要三个 PPF：, , 来表示三种类型的关系：「cited-by, authored-by, and published-by」。通过人工分配 PPF 显然不现实，因此文中提出一种基于模拟退火的方法（simulated annealing algorithm）来自动学习每种类型关系的 PPF，为了减小模拟退火算法的搜索空间，文中仅选用子图来计算 PPF。
上图表示类型为 对象的网页链接。由于 Web 中对象信息是嵌入在网页中的，因此可以根据 PageRank 来计算网页流行度（Web Popularity）。
利用向量 来表示对象 的网页流行度， 表示通过网页链路图或对象关系图找到对象的概率。为了计算对象的流行度分数，PopRank 算法综合考虑了网页对象流行度及其对象关系，使用以下公式来计算类型 对象的 PopRank 分数 ：
其中：
表示类型为 , 的对象集合。 和 表示类型为 , 的流行度分数。 为邻接矩阵。 如果对象 之间存在边，否则为 0，表示对象到类型为对象间的链接数量。 表示对象类型 与对象类型间的 PPF，。 表示对象类型的网页流行度。 表示衰减因子。
后续包括利用模拟退火算法自动学习 PPF（SAFA，Simulated Annealing for Factor Assignment）和子图选择过程。算法过程如下所示：
需要了解参数设置的同学可以查看原文。
Experiments
论文中使用的评价指标是计算两个排名间的距离，计算公式如下所示
其中 表示排序对象数量， 表示排序列表 中第 个对象。
实验结果如下图所示
Thoughts
整体思路和 PageRank 算法相同，创新点主要在于考虑了节点间不同关系的影响和自动学习 PPF 的过程。
dreamhomes
博客：dreamhomes.top
隐形字
公众号：DreamHub
长按识别二维码关注
👇🏻 点击「阅读原文」，排版效果更好哦！
