文档介绍：PageRank算法
姓名:陈咸康
研究方向:图形图像处理
导师:李兴民
华南师范大学计算机学院
主要内容结构(Contents)

2.
PageRank算法
诞生背景和动力(when)
是什么(what)
怎么样(how)
实例:谷歌
(case)
应用领域
(where)
结论
(conclusion)
估计网络流量.
反向链接预测.
用户导航:
PageRank 代理
其他应用.
诞生背景和动机
搜索引擎发展史

现代意义上的搜索引擎的祖先——Archie
1990年,还没有),ftp(文件传输协议)软件是共享文件主要工具。但要共享文件,必须要一个ftp服务器。检索ftp数据也要使用ftp客户端,然而很多数据都是零散分布在各个不同的地方,用户却缺乏一种直接查询ftp文件所在地址的工具。基于这种背景,加拿大蒙特利尔的麦吉尔大学(McGill University)的三位学生Alan Emtage、Peter Deutsch、Bill Wheelan发明了Archie。
Archie并非一个真正的搜索引擎
Archie 的特点
,不能获取诸如网页等其他类型的文件资源,只能算是ftp搜索引擎。
(Robot)程序,上的网页,它是基于脚本的文件名称收集器,通过正则表达式匹配用户查询与文件名称来实现查询,并通过文件列表的方式提供信息查询结果。
由于Archie深受用户欢迎,受其启发,puting Services大学于1993年开发了另一个与之非常相似的搜索工具,不过此时的搜索工具除了索引文件外,已能检索网页。
机器人
“机器人”一词在编程者中十分流行。电脑“机器人”(Computer Robot)是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的“机器人”程序像蜘蛛一样在网络间爬来爬去,因此,搜索引擎的“机器人”程序就被称为“蜘蛛”程序。
第一个“机器人”程序
Matthew Gray开发的World wide Web Wanderer。
用来统计互联网上的服务器数量,后来则发展为能够检索网站域名。
Wanderer相对应,Martin Koster于1993年10月创建了ALIWEB,它是Archie的HTTP版本。ALIWEB不使用“机器人”程序,而是靠网站主动提交信息来建立自己的链接索引,类似于现在我们熟知的Yahoo。
检索整个互联网
原理:所有网页都可能有连向其他网站的链接,那么从跟踪一个网站的链接开始,就有可能检索整个互联网。
在Matthew Gray的Wanderer基础上,一些编程者将传统的“蜘蛛”程序工作原理作了些改进。到1993年底,一些基于此原理的搜索引擎开始纷纷涌现,其中以JumpStation、The World Wide Web Worm(Goto的前身,也就是今天Overture,之后被Yahoo收购),和Repository-Based Software Engineering (RBSE) spider最负盛名。
JumpStation, , RBSE特点
JumpStation和联度可言。
而RBSE是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。
最早现代意义上的搜索引擎
1994年7月, Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中,创建了大家现在熟知的Lycos。
同年4月,斯坦福(Stanford)大学的两名博士生,David Filo和美籍华人杨致远(Gerry Yang)共同创办了超级目录索引Yahoo。