今天看到博客中有一位网友提出了问题,如下:
梁老师,您好。我是通过走进搜索引擎这本书知道您的,这本书我也读了好几遍,就是在这个web直径的公式证明一直无法解决。找到您的博客,所说的方法就是利用可达性矩阵幂次方去做,但是水平有限,梁老师能不能给我一个证明过程,或者是推荐网上的证明页面。 ps:我也利用谷歌搜偶国外的,都没找到这个公式证明。我的邮箱是695950380@qq.com。谢谢。
来源:http://blog.csdn.net/pennyliang/archive/2007/02/24/1513312.aspx#1492642
Page和Page之间的可达关系可以用有向图来描述,我们举一个具体的例子(Page可以自己指向自己,因此可以包含自反关系,但为了简单起见,例子中不含这种自反关系)
写成矩阵形式如下
则直接可达,路径为1的关系有,<1,2>,<2,3>…,矩阵中元素和(含1的个数)=5。
路径为2的关系有<1,3>,<1,5>,<2,2>…,矩阵中元素和=5;
依次计算下去。
由于存在<2,3>,<3,2>这种情况,因此<1,4>的路径可以是3,5,7等等,这种情况只需要取最短的3即可(可能有更好的方法,我没有细致考虑,应该会有让计算快速收敛的更好方法)。同时如果不断求乘积的过程中,可达关系均为已经出现过的,或者均为0的情况下,则计算终止。
最后,计算总的路径数:
同时计算总的具有可达关系的关系数总和R(例如<4,5>不是可达,因此这个关系不计入在R中,<1,2>等类似关系计入在R中)
则Web直径可以用R/P求得。
在实际处理中,可以采用一些方法来优化矩阵的计算,有文献表明目前的可以公开访问的互联网网页超过200亿。因此如果做计算的话200亿的规模过于巨大,可以进行一些采样。同时可以借助矩阵的稀疏性做一些优化。例如:
可以给每个节点做一个邻接表(每个节点拉出一个list,每个元素是它link到的page)
1->2 (->看做1跳可达,key=1,value=2)
2->3,5
3->2,4
这样做A*A的过程可以转化为
1->2 and 2->3,4 >> 1=>3,4 (=>看做2跳可达)
2->3,5 and 3->2,4 >> 2=>2,2=>4
3->2,4 and 2->3,5 >> 3=>5
余不例举,这样相当于仅存储有效边,在计算中连接表均为顺序存储,且key可以支持随机读取因此可以大大加速。同时还可以做分块话的处理,可以支持多机并行计算,不在深入,有机会会就这一方面主题作专题探讨。
另外,指出问题中的一个问题,Web直径的大小是测量出来的,并不是证明出来的,就好像万有引力定律的那个系数一样,也是测量出来的,并无办法证明,当然这可能有什么更深入的自然原理,可以证明,但就人类目前认识来说,类似的值均是测量测定的,还很难做出证明。
关于web直径的最早测定来源于: Albert, Jeong, and Barabasi 99. R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the World Wide Web, Nature 401:130-131, Sep 1999.
在这篇论文中,作者通过计算拟合出这样的公式:web直径=0.35+2.06log(N),目前网页数量发展很快,新的计算和测定,据我了解,还没有进一步的数据,
推荐阅读:
http://www9.org/w9cdrom/160/160.html#AlbertJeongBarabasi
分享到:
相关推荐
问题: 在本地计算机无法启动 world wide web Publishing 服务错误127:找不到指定的程序 但找不到 KB939373 补丁 下载后运行UninstallKB939373.exe 容易解决
web常见问题解答,可以受到很大的启发, web常见问题解答,可以受到很大的启发 web常见问题解答,可以受到很大的启发 web常见问题解答,可以受到很大的启发
Web Navigator常见问题解答zip,Web Navigator常见问题解答
基于WEB的在线问题解答系统.doc
基于web的在线问题解答系统.docx
面向Web服务计算2006.ppt
Web问题解答一.mp4
Web问题解答二.mp4
针对Web服务和Web业务的选择问题,提出一种基于动态需求服务反馈的Web业务可信度协同计算算法,动态分析了用户的Web服务选择和组合问题,采用了基于用户满意度信息的服务反馈模型来解决Web服务的选择问题,从而防止...
Learn web scraping and crawling techniques to access unlimited data from any web source in any format. With this practical guide, you’ll learn how to use Python scripts and web APIs to gather and ...
Web表单设计:点石成金的艺术.pdf
Fundamentals of Web Computing
计算Web页面的高度并给div赋高度,得到的是工作区的高度,根据工作区高度计算的
web简单购物车计算代码
这是我做实验时候做的一个简单的可以计算三角形面积和周长的小实验,希望对于正在学web可以有所帮助
ASP.NET MVC 4 Web编程 目录: 第1章:ASP.NET MVC基础 第2章:ASP.NET Web Form开发人员必读 第3章:使用数据 第4章:客户端开发 第5章:Web应用程序架构 第6章:使用AJAX提升网站体验 第7章:ASP.NET Web API 第8...
Eclipse核心编程:插件、界面与Web开发Eclipse核心编程:插件、界面与Web开发Eclipse核心编程:插件、界面与Web开发Eclipse核心编程:插件、界面与Web开发
H3C 交换机Web网管操作指南 H3C 以太网交换机WEB网管用户手册简介: 1.产品简介 2.通过Web页面配置 3.常见问题解答
英文新版:Agile Web Development with Rails, 4th Edition(For Rails 3.1 & 3.2) 内容简介 《Web开发敏捷之道:应用Rails进行敏捷Web开发(第3版)》主要分为两大部分。在“构建应用程序”部分中,读者将看到一个完整...
dataX部署以及常见问题解答,以及一点源码修改的内容