上一篇中，我们简单介绍了链接分析中的PageRank算法以及HITS算法，在本文中，我们将继续介绍两种链接分析的算法——主题敏感的PageRank以及TrustRank。
1 主题敏感的PageRank
我们知道，PageRank的排名是与用户搜索的关键词完全无关的。主题敏感的PageRank (Topic-sensitive Pagerank[ref]Topic-Sensitive PageRank[/ref])因此而诞生来弥补这一缺陷。主题敏感的PageRank旨在做到如同HITS算法一样排名与主题有关的前提下减少算法的计算复杂度。为了计算主题敏感的PageRank，我们要做的第一步便是确定$k$个主题，一般我们从一些目录网站选取主题。开放目录项目(DMOZ)是其中比较知名的，但很可惜的是该项目已于2017年3月1关闭，我们只可以访问该项目的静态镜像。第二步则是主题敏感的PageRank的核心了。和普通PageRank算法只计算一个全局的PageRank向量不同，主题敏感的PageRank算法会计算一组PageRank向量。改组向量中向量的个数等于选定主题的总数$k$，其中每一个向量对应一个不同的主题。也就是说，每个网页都有$k$个PageRank分值。最后在进行搜索时，我们根据用户搜索的词语，用户的个人数据（例如浏览历史，书签，收藏夹内容等），利用一些信息检索中的技术（例如自然语言处理，机器学习，深度学习等）估计用户想要搜索的主题的概率并且对我们生成的一组主题敏感的PageRank向量进行线性组合得到最终结果。
为了详细讲解主题敏感的PageRank，我们先来回顾一下普通的PageRank算法。我们从在有向图中随机行走的角度出发，可以得到关于PageRank向量$\vec{Rank}$的等式如下：
$$\vec{Rank} = M \times \vec{Rank}$$
其中$M$为转移矩阵(Stochastic matrix)。为了保证算法的合理以及收敛性，我们引入阻尼系数(Damping factor)$1-\alpha$并且用矩阵$M'$替换上述等式中的$M$，其中$M'$符合：
$$M' = (1 - \alpha ) M + \alpha [\frac{1}{N}]_{N \times N}$$
所以，我们更新关于$\vec{Rank}$的等式如下：
$$\vec{Rank} = M' \times \vec{Rank}=( 1 - \alpha ) M \times \vec{Rank} + \alpha \vec{p}$$
注意上面化简的过程中，我们利用到了$\left|\vec{Rank}\right|{1}=1$的性质，并且$\vec{p}=[\frac{1}{N}]$。$\vec{p}$被称作个性化向量(Personalization Vector)，主题敏感的PageRank计算中最重要的一点就是使用不均一的(Nonuniform)的个性化向量。假设$T_j$是开放目录中一个分类$c_j$中所以的URL的集合，那么多于这个话题$c_j$，我们用$\vec{w_j}$替换$\vec{p}$，对于页面$i$，我们有：
$$w_j(i)=\begin{cases} \frac{1}{|T_j|},i \in T_j \ 0,i \notin T_j \end{cases}$$
在查询时，对于查询词$q$，我们利用每个页面$u$主题敏感$c_j$的PageRank分数$rank(u,j)$乘以$q$属于主题$c_j$的概率并且求和来计算页面$u$关于查询词$q$的分数$Score(u,q)$：
$$Score(u,q) = \sum_{j=1...k} \Pr(c_j|q) \cdot rank(i,j)$$
值得讨论的是，对于$\Pr(c_j|q)$我们可以运用不同的模型计算，以基本的一元(Unigram)语言模型为例：
$$\Pr (c_j|q) = \frac{\Pr (c_j) \Pr (q|c_j)}{\Pr (q)} \propto \Pr (c_j) \Pi_i \Pr (q_i |c_j)$$
以上是关于主题敏感的PageRank的基本数学解释，我们可以发现，大部分的计算都是离线完成（多个PageRank向量的生成），计算复杂度并没有大幅增加。但是该算法中需要大量信息检索方面的算法来辅助，例如网页分类，主题的判断等。在问答网站注册时，网站往往需要你选择你感兴趣的话题，这些信息便可以配合主题敏感的PageRank来为你生成个性化的搜索结果。除此之外，例如谷歌和百度等现代的搜索引擎都会通过记录你的私人数据来分析判断你的喜欢，这使得搜索引擎有更好的搜索结果，但也可能会有隐私泄露的风险。
2 TrustRank
TrustRank[ref]Combating Web Spam with TrustRank[/ref]的基本假设是一个好的页面往往不会指向一个垃圾页面(Spam Page)。我们利用这个假设，人工筛选一个包含一些页面的集合，以此为基础对网络中所以的页面进行打分。这个基本的页面集合被称为种子页面(Seed Pages)，由于人工选择种子页面是一个非常昂贵的工作，我们需要把种子页面的数量控制的尽量少。种子页面中较好的页面被称为信任页面，我们将它们的TrustRank数值初始化为$1$，其它垃圾页面我们则初始化为$0$，然后我们在整个网络中进行可信度传播(Trust Propagation)。可信度传播遵守一些两条基本规则：
-
信任衰减(Trust attenuation)：信任页面授予的可信度随着距离的增加而衰减
-
信任分裂(Trust splitting)：一个信任页面指向的网页越多，则每个网页分到的信任值越少
TrustRank的数值范围都在0到1之间，我可以通过设定一个阀值来将TrustRank值低于阀值的网页标注为垃圾网页。我们也可以将TrustRank和PageRank结合在一起，通过判断可信页面对一个网页PageRank的贡献比来更精确的筛选垃圾网页。TrustRank的计算方式与PageRank非常近似，我们就不再详细讲述了。关于链接分析中各种常用算法的更多解释可以阅读斯坦福大学Mining Massive Datasets课程中的链接分析章节。
Comments