PageRank算法.pptx

PageRank算法
主要内容结构(Contents)







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

现代意义上的搜索引擎的祖先——Archie
1990年，还没有www（万维网），ftp（文件传输协议）软件是共享文件主要工具。但要共享文件，必须要一个ftp服务器。检索ftp数据也要使用ftp客户端，然而很多数据都是零散分布在各个不同的地方，用户却缺乏一种直接查询ftp文件所在地址的工具。基于这种背景，加拿大蒙特利尔的麦吉尔大学（McGill University）的三位学生Alan Emtage、Peter Deutsch、Bill Wheelan发明了Archie。
机器人
“机器人”一词在编程者中十分流行。电脑“机器人”（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, WWW Worm, RBSE特点
JumpStation和WWW Worm只是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果，因此毫无信息关联度可言。
而RBSE是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。
最早现代意义上的搜索引擎
1994年7月， Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的Lycos。
同年4月，斯坦福（Stanford）大学的两名博士生，David Filo和美籍华人杨致远（Gerry Yang）共同创办了超级目录索引Yahoo。