PR算法的复杂度规模是log(n)，n是网页的数量。网页权值在算法执行过程中是一个振荡收敛的过程，这其中有两个主要矛盾：1.节点的数量巨大，内存成为瓶颈之一。2.巨大的2维矩阵每次计算消耗时间巨大，时间效率上也是瓶颈；其中大部分网页的权值比较低，而且都是浮点数计算。
改进思路一：迭代计算的次数和矩阵的规模（链接的个数）有一定的比例关系，例如
改进思路二：分而治之，对一个独立域名下的网页权值独立计算。比如http://www.zju.edu.cn下的子域名在爬虫抓取数据的过程中独立地计算相对网页权值，记作PR-R。然后再以域名为单位，做全局域名之间的权值计算，得出域名对应的权值PR-T。所以，最后域名下各个页面的权值等于PR-R×PR-T。
改进思路三：采用加速收敛的方法。每次迭代都会得到一个n维偏移向量p，但是取偏移为pk（k>1）作为此次迭代的偏移向量。
改进思路四：减少计算量。对大量的权值低于一定限值的网页，计算过程中忽略其链接产生的权值分配。
No comments:
Post a Comment