5. Namazu 上的实际安装实验
为了使更简单地推测上文描述的问题，PageRank 并不是非世界所有的web页面而不能使用的考虑方法，即使是个人的利用方法也能实现。为了实现「Personalized PageRank」，针对在各种 UNIX 和 Windows 上运作的中小规模网站适用的全文检索系统 Namazu 进行了实际安装实验。(关于Namazu可参考 日语全文检索引擎软件列表。)
由于实验能简单地控制内存的使用量，并将最大特性值用1来考虑，所以将 Have liwala(1999)的想法做为基本的考虑方法。但是对 dangling pages 的处理有少许不同。固有矢量的计算内核使用了数值计算脚本 GNU Octave。所以基本的代码编写自己只用了一天就解决了。另外，从用 mknmz 编写的索引不能直接计算 PageRank，而要事前准备表示邻接关系的索引(邻接列表)。这个也有可能被编入检索者(Indexer)的主要部分。
以下表示了实际计算时间(单位：秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。
文书数N mknmz时间 准备时间 PageRank计算时间
============================================================
128 58 2 6
2,301 1, 575 46 214
49,604 15,975 478 5,872
因为没用一些巨大的web页群来做测试，所以实验只停留在小规模的基础上。虽然有这个难点,但从基本上可以了解与索引所花的时间相比，在很短的时间里就可以计算 PageRank 的倾向吧。
因为 Namazu 自身中也有很多难题，所以并不寄予很大的奢望，但至少使用 105 程度(尽可能 106)规模的web页面群来实验。从趋势来看可以预想 N=106 的计算时间恐怕会发散开去，所以在 N=106 时，若是能够讨论把mknmz时间变成和comparable一样的加速方法的话，对于Personalized PageRank 来说就十分实用了。作为参考，根据Page et al.(1998)，Google 对7500万的URL的实际 PageRank 计算时间约是5小时。(2001年2月现在不明)。从这个角度来说，研究更加高效的加速法的余地就十分得必要了吧。
计算实际运行时的使用内存最大也是10几MB左右。如果是Haveliwala (1999)那样的「吝啬地作战」的话，最大只有O(3N 2)左右的内存使用量就做完了,不过 N 是 104-5 程度和内存的使用量连 N2 也放不进的话，其他的也只能勉强调谐了，所以以 O(5N α) (α是疏松行列的非零成分数字，典型的是5-20N左右) 程度来编写代码。另外 N 是103 左右时，可以确认不压缩疏松行列就在内存上使用幂乘法来计算，从速度面上来说是非常有利的。实测时速度为上述数字的6-7倍左右的。但遗憾的是，这个方法从内存的限制来看，尽可能地只使用2-3千页以内。
此次我们使用了 Octave 分发附属的「Tsurushi」,不过，正像大家知道的那样，如果把 Octave 调谐的好的话，会戏剧性地提高完成的速度。Octave-2.1.x 和 ATLAS 的组合有时候根据情况甚至会使大规模行列乘法的运算速度提高10倍以上。
实验的详细结果请参照prnmz-1.0.tar.gz 中的文档。
Personalized PageRank 的基本性质
人们经常会利用 MHonArc、latex2html 或者 PowerPoint 这样的工具将文档变成 HTML，针对这样的人工制作的HTML链接群求 PageRank 的话，大部分页面的得分几乎都是一样的(～1/N)。如果考虑邻接行列，则大部分的成分是1，或者对角成分附近全部是1。因为这样的推移概率行列的固有矢量成为(1,1,…,1)。
或是象 sitemap.html 一样变成树状的情况下，分数会集中在sitemap.html中。就算占据全体的9成也不算新奇。
从现在起能说的是，为了计算有意义的 PageRank，要尽可能地排除机械生成的链接关系。如果把链接关系看做是推荐关系的话更加容易认同了吧。
6.对 PageRank 的个人的见解
(读者)应该没有余地去怀疑象 PageRank 那样利用超级链接来决定排列次序有效手法吧。
不过，阅读了这些论文以后笔者自身也考虑了许多问题。在这里，列举几个对 PageRank 的个人见解。虽是见解,说到底就是方法论，也许会有很多错误的地方。
关于 dangling page，不相反考虑的原因是什么？
只是因为考虑一定的变异概率时「偶然」会变成最简才不予考虑吗？还是有时看漏了什么吗？稍微有点不太明白。
改善推移概率行列的可能性
说起来，为了保证 PageRank 的单一意义的性质(一意)，只要保证推移概率行列是最简(有向图表是强联结)就行了，没有必要所有的要素 aij 都是非零要素。事实上，像在web上浏览 Toyota 汽车网站后紧接着跳向色情网站，接着又继续跳到白宫网站浏览的怪异的人应该是不存在的吧。(请注意这里是指在随时间变化连续的形式)。因此，从实用的意义上来说，区别于改善多少的使用方便程度，应该留下对算法改良的余地。
考虑「逗留概率」会怎样
根据 PageRank 的考虑方法，在一定的时间后必定顺着链接前进到其他的页面，或者突然怪异的、歪曲的跳到其他页面。但是如果对照现实的web浏览模型，也要考虑一定的逗留概率。具体地说，就是推移概率行列的对角成分中只取( 1-c)/N 的话取得过小了。在原本所有变迁概率都一定的情况下，更加进一步分析会怎样？因为对于无聊的页面(浏览者)必定会想都不想就转到另外的页面，反过来对于重要的页面却会停留较长的时间。
如果考虑概率论应用的话必定会考虑其他许多问题
即使是将实现性置之度外，我们也再来试着进一步考虑这个想法。概率论中，存在着一种叫消灭概率或叫固定概率的概率。比起 PageRank 的单纯而同样考虑方法，导入这种考虑方法会得到更期望的结果，所以理所当然被大家所期待。大家都知道马尔可夫链中的分枝过程的考虑方法。这是考虑遗传基因突变时的一个模型，即，说明经过一定的时间而产生淘汰的可能性的模型。很多人认为这个考虑方法或许会被采用。那么导入带有限制的概率(禁忌概率)又会怎么样呢？ 即，相当于导入通过 n 次的推移从状态 i 移动到状态 j 时，不经过状态 k 的概率。如果考虑到web浏览的性质的话，不是也能理所当然地成为假定吗？
不能作为非马尔可夫过程(或者说 m次的多重马尔可夫过程)来考虑吗
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
