PopRank：异质信息网络中对象级别的节点排序模型

论文标题｜ 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： $\gamma_3$ , $\gamma_2$ , $\gamma_1$ 来表示三种类型的关系：cited-by, authored-by, and published-by。通过人工分配 PPF 显然不现实，因此文中提出一种基于模拟退火的方法（simulated annealing algorithm）来自动学习每种类型关系的 PPF，为了减小模拟退火算法的搜索空间，文中仅选用子图来计算 PPF。

上图表示类型为 $X_i$ 对象的网页链接。由于 Web 中对象信息是嵌入在网页中的，因此可以根据 PageRank 来计算网页流行度（Web Popularity）。

利用向量 $R_{EX}$ 来表示对象 $X$ 的网页流行度， $R_X$ 表示通过网页链路图或对象关系图找到对象 $X$ 的概率。为了计算对象的流行度分数，PopRank 算法综合考虑了网页对象流行度及其对象关系，使用以下公式来计算类型 $X$ 对象的 PopRank 分数 $R_X$ ：

$R_{X}=\varepsilon R_{E X}+(1-\varepsilon) \sum_{\forall Y} \gamma_{Y X} M_{Y X}^{T} R_{Y}$

其中：

$X=\{x_{1}, x_{2}, \ldots, x_{n}\}, Y=\{y_{1}, y_{2}, \ldots, y_{n}\}$ 表示类型为 $X$ , $Y$ 的对象集合。
$R_X$ 和 $R_Y$ 表示类型为 $X$ , $Y$ 的流行度分数。
$M_{YX}$ 为邻接矩阵。 $m_{y x}=\frac{1}{N u m(y, x)}$ 如果对象 $x, y$ 之间存在边，否则为 0， $Num(x, y)$ 表示对象 $y$ 到类型为 $X$ 对象间的链接数量。
$\gamma_{Y X}$ 表示对象类型 $X$ 与对象类型 $Y$ 间的 PPF， $\sum_{\forall Y} \gamma_{Y X}=1$ 。
$R_{EX}$ 表示对象类型 $X$ 的网页流行度。
$\varepsilon$ 表示衰减因子。

后续包括利用模拟退火算法自动学习 PPF（SAFA，Simulated Annealing for Factor Assignment）和子图选择过程。算法过程如下所示：

需要了解参数设置的同学可以查看原文。

Experiments

论文中使用的评价指标是计算两个排名间的距离，计算公式如下所示

$D\left(R, R^{\prime}\right)=\frac{\sum_{i=1}^{n}\left[(n-i) \times \sum_{j=1 \wedge R_{j}^{\prime} \notin\left\{R_{1}, \ldots, R_{i}\right\}}^{i} 1\right]}{\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}[(n-i) \times i]+\sum_{\left.i=L \frac{n}{2}\right\rfloor+1}^{n}[(n-i) \times(n-i)]}$