个性化网页权重PageRank算法研究

目前关于个性化PageRank，其他的常见方法还有模型化PageRank(modular PageRank)和BlockRank等。这些方法在具体的计算方法上，主要的特点体现在从效率的角度上对算法进行了必要的优化。

关于加速PageRank算法的先前研究内容主要使用稀疏性图结构技术，比如Arasu等提出的观点，他们不仅仅单纯使用上次迭代循环产生值来计算本轮循环值，也使用本轮循环已经产生的值来加速本轮循环的计算。甚至提出了Web网络的蝴蝶结结构，并将其用于PageRank值的有效计算中。然而这些方法并不具有很大的实用性，主要原因在于算法要求对Web网络矩阵进行排序，这个操作需要按照深度搜索优先的原则进行网络遍历，这显然是一种代价极大的运算。最近Kamvar等也提出一些算法，使用连续中间循环来推断真实PageRank更好的估计值，但是仍然存在受PageRank算法初始参数影响的不足之处。

目前对于Web网络图结构的分析主要关注于研究图的属性，如节点的分布、网页链接的情况和Web网页图结构的建模等。然而，对于这些研究并没有强调如何有效利用这些属性来加快超链分析。

不少学者提出了一些改进做法，如Raghavan和Garcia-Molina等利用主机名称或者URL隐含的Web结构来代表Web图更为成功的做法也有很多，如Jeh和Widom通过有限修改网页的权值来表达的个性化网页权重，这个重要性权值可以反映用户指定的初始兴趣网页。由于对个性化视图的计算需要反复遍历整个Web图结构中的网页，这只有在运行期间才能实现，所以事先计算和存储所有的个性化视图并不现实。他们利用新的图论结果和技术构建出表达个性化视图的“偏好向量”(partial vector)，它可以在不同用户的个性化视图中共享，同时关于它的计算和存储花费与视图数量的多少呈现出合理的比例。在计算中，还可以采用递增式计算，这就使得在查询期间利用偏好向量去构建个性化视图是可行的。这个偏好向量即为个性化PageRank向量(personalized PageRank vector，PPV)，通俗地说，PPV是种Web网页的个性化视图。按照这个PPV来对网页结果进行排序可以有效地表达用户的偏好。

简单地看，每个PPV的长度都为咒，即Web的网页数量。但是由于从一个固定的角度循环计算PPV需要多次遍历Web网页图，这显然是不可能作为一种在线响应用户查询的方式。从另一个角度来看，所有PPV向量的总数量会达到2n(n为网页总数)，这显然又过于巨大而无法实现离线存储。所以，必须将p集合中出现的网页限制为hub网页集合H的子集。H集合通常包含一些用户最为感兴趣的网页。在实践中，H集合可以是具有较高PageRank值的网页集合(重要网页)、在人工分类目录中的网页(如Yahoo和Open Directory)、特定企业或程序的重要网页等。H集合可以看成是计算个性化的基础。这种基于PPV的计算方式，不像传统的方式，能够和H集合大小成良好的比例缩放关系，并且这种技术也可以在更大的PPV集合上取得近似的效果，满足一些对于任意偏好网页集合的个性化计算要求。

除此以外，还有一些在计算效果上进行改进的算法。

如一种较为成功的做法是BlockRank方法，它主要是充分利用Web网页间链接结构呈现一种块状结构的特征来改进算法效率。关于Web网络块状结构的特征，已有很多学者进行了论证。例如，据Bharat等的分析，通过对比分析Web网络的链接结构，可以发现近80％左右的网页超链都是同一站点主机内部不同网页间形成的，而不同主机站点间网页的超链比重仅为20％左右。如果去除无用的死链接，这一比重表现得更加不平衡，近似于9：l。进一步将考察范围限定在域名级别后，上述的两个比重都有明显的增加，一为84：16，二为95：5，不平衡性明显加剧。一般在一个主机站点内，大部分的超链由于导航和站点安排，往往会在几个关键的网页上具有较多的内部链接。例如，高校站点内一般会对诸如图书馆、教务处和学生处等网页产生很高的链接比重。其实这种内部链接较高、外部链接较低的情况在不同级别的Web网页图结构中广泛存在，产生了明显的块化现象，而且大部分的块结构都远远小于整个Web的图结构。

这种Web网络所具有的块化结构有助于快速计算PageRank，同时为表达个性化PageRank提供了良好的基础。这个算法的思路大体描述如下：先对每个主机的网页计算本地化的PageRank值，得到在主机内部的相对重要权值。这些本地化的PageRank向量可以进一步按照不同Web网页块的相对重要程度加权形成全局PageRank值的近似值，然后将此PageRank向量作为标准PageRank算法的起始向量。不可否认，个性化PageRank虽然是个非常吸引人的主意，但是它需要对大规模的PageRank向量进行有效的迭代计算，而使用BlockRank算法和对冲浪者的随机冲浪行为做简单的限制就可以有效地减少个性化PageRank值的计算复杂度。这个限制就是当他厌倦时，他并不是从诸多网页中选择，而是从主机站点中进行选择。也就是说，此时无需考察冲浪者跳转的网页，而只考虑跳转的站点。这时构造的个性化向量具有的维度就是Web网络中主机的个数K，并且向量的元素值也反映冲浪者对不同主机的偏好程度。有了这个限制，本地化PageRank向量就无需针对不同的个性化用户而改变。事实上，本地化的PageRank向量也不会因为矩阵B结构的改变而改变，只有BlockRank向量6才会因为不同的个性化特征而改变，因此只需对每个基于块结构的个性化PageRank向量进行重新计算。

应该说，不论从理论上看，还是从实践上看，利用个性化PageRank来实现搜索引擎的个性化服务是个非常可行的选择，适应Web网络资源对信息检索提出的特点要求。它不仅在推荐结果内容上综合考虑网页客观性权重这个重要指标，而且该方法性能较高，主要计算工作都在离线阶段完成。然而，这些现有的个性化PageRank技术都需要用户登录并主动提交个性化信息，却忽略了用户对Web网页的理解，没有挖掘用户使用行为，收集用户个性化信息的方式不自然，这显然加重了用户的使用负担。所以，虽然说节省了用户挑选相关网页的时间，但是用户却需要花更多的时间去实现搜索个性化。由此可以看出，探讨获取用户个性化信息的其他有效形式将是提高此方法效果的关键所在，本书也主要对此进行研究，探寻更好的个性化信息收集和表达方法以适用于个性化PageRank算法中，该方法较为客观和全面。