个性化网页权重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页的超链比重仅为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算法中，该方法较为客观和全面。