谷歌矩阵及网页等级划分 .docx
《谷歌矩阵及网页等级划分 .docx》由会员分享,可在线阅读,更多相关《谷歌矩阵及网页等级划分 .docx(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、谷歌矩阵及网页等级划分摘要:搜索引擎技术的发展是随着电子技术的不断进步而形成的信息数字化和数据网络化的必然结果。一个好的搜索引擎能够及时为用户提供他们需要的信息,这就需要一个快速、高质量、高效的搜索算法来支持。谷歌搜索引擎凭借其PageRank机制和收敛算法在搜索领域一直处于领先地位。本文介绍了该搜索引擎的核心:PageRank算法。PageRank算法通过计算网页的重要性值PageRank值来确定网页排名的优先级,网页的PageRank值是指向该网页的其他页面的PageRank值。因此,谷歌的搜索结果是有效和客观的。PageRank是一个反映网页重要性的值。当一个网页A连向另一个网页B的时候
2、,A就等于给网页B投了有效的一票.一个网页接受的票越多,这个网页就越重要.同时,给网页B投票的网页本身的等级也决定了该选票的重要性. 谷歌通过每个投票的重要性和得到多少投票来计算网页的排名(重要性)。谷歌的核心是计算每个网页的排名(即PageRank)。本文主要介绍了谷歌矩阵的定义和生成,并阐述了PageRank的相关概念。证明Google矩阵及其第二特征值具有的一些性质,并简要介绍这些性质的应用。关键字:谷歌矩阵;特征值;网页等级;Google matrix and web page hierarchyAbsrtact:The development of search engine tec
3、hnology is an inevitable outcome of information digitization and data networking formed with the continuous progress of electronic technology. A good search engine can provide users with the information they need in a timely manner, which requires a fast, high-quality and efficient search algorithm
4、to support. Google search engine has been leading the field by relying on its PageRank mechanism and convergence algorithm. This paper introduces the core of this search engine :PageRank algorithm. The PageRank algorithm determines the priority of webpage ranking by calculating the importance value
5、of the webpage - PageRank value, and the PageRank value of the webpage is the PageRank value of other pages pointing to the webpage. Therefore, Googles search results are efficient and objective. Page rank (PageRank) is A reflect the importance of numerical page. When A web page A link to another pa
6、ge B, A is equal to give B to vote for the effective web pages. A web page to accept the more tickets, this web page is more important. At the same time, to rank web page B to vote itself also determines the importance of the votes. Google through the importance and the number of votes each ballot i
7、tself to calculate the level of A web page (importance). Googles core is the calculation of each web page level (PageRank). This paper mainly introduces the definition and Google matrix Generate, explain some related concepts of PageRank, prove some properties of Google matrix and its second eigenva
8、lue, and briefly introduce the application of these properties.Keywords: Google matrix; Characteristic value; PageRank;目录1 绪论31.1研究背景31.2研究意义31.3研究现状32 谷歌矩阵42.1谷歌矩阵的基本定义42.2谷歌矩阵的理论发展52.3谷歌矩阵的特征值和特征向量72.4谷歌矩阵的基本问题和研究现状83 运用数值分析方法和Matlab计算特征值和特征向量83.1运用数值分析法83.2使用Matlab83.3计算特征值和特征向量94 谷歌矩阵分解和谷歌谱理论方法1
9、24.1谷歌矩阵分解124.2谷歌矩阵谱理论方法135 谷歌矩阵在网页分级中的应用和理论意义145.1谷歌矩阵在网页分级中的应用145.2谷歌矩阵在网页分级中的理论意义165.3谷歌矩阵的网页分级实例216 总结26参考文献27致谢291 绪论1.1研究背景搜索引擎技术的发展是随着电子技术的不断进步而形成的信息数字化和数据网络化的必然结果。一个好的搜索引擎能够及时为用户提供他们需要的信息,这就需要一个快速、高质量、高效的搜索算法来支持。谷歌搜索引擎凭借其PageRank机制和收敛算法在搜索领域一直处于领先地位。本文介绍了该搜索引擎的核心:PageRank算法。PageRank算法通过计算网页的
10、重要性值PageRank值来确定网页排名的优先级,网页的PageRank值是指向该网页的其他页面的PageRank值。因此,谷歌的搜索结果是有效和客观的。PageRank是一个反映网页重要性的值。当一个网页A连向另一个网页B的时候,A就等于给网页B投了有效的一票.一个网页接受的票越多,这个网页就越重要.同时,给网页B投票的网页本身的等级也决定了该选票的重要性. 谷歌通过每个投票的重要性和得到多少投票来计算网页的排名(重要性)。谷歌的核心是计算每个网页的排名(即PageRank)。本文主要介绍了谷歌矩阵的定义和生成,并阐述了PageRank的相关概念。证明Google矩阵及其第二特征值具有的一些
11、性质,并简要介绍这些性质的应用。1.2研究意义随着计算机技术的普及和Internet网络技术的发展,信息数字化和数据网络化已成为现代经济社会发展的客观要求和必然趋势。当今世界上已经拥有超过10亿的Internet用户和近百万个不同级别的网络服务器。同时,包括政治、经济、科学、文化、艺术等各个不同的社会领域也都不同程度地实现了其资源信息的数字化和共享化。Internet网络已名副其实地成为世界最大的信息中心。作为一个Internet用户,自然希望能够最大程度地使用如此庞大而全面的信息资源,但是Internet网又是分散的,单靠浏览一个或几个网页所能得到的信息对于整个网络中的可用信息而言可谓是沧海
12、一粟,浅薄得很。用户自然地希望能够获得更多,更全面的信息,在这种需求下的网络搜索引擎技术。只要用户输入关键字,搜索引擎就可以从网络中找到匹配关键字的信息并将其返回给用户。目前,谷歌、百度、新浪、搜狐等搜索引擎在国内外得到了广泛的应用。它每分钟已经被使用了数万次。1.3研究现状谷歌现在是世界第一的搜索引擎,是斯坦福大学的创始人,两位博士生和d塞雷伯恩页面,在斯坦福大学学生宿舍在1998年发明了一种新的网络搜索引擎,现在被认为是世界上最大的搜索引擎,提供多种语言来查找信息,如查询,地图,和股票新闻,发现在美国所有城市的电话号码目录列表,搜索数以十亿美元计的图像,世界上最大的10亿篇帖子,用户可以在
13、一瞬间得到相关结果。在过去的一年里,谷歌已经取代了Iknot Yhaoo和网易的中文搜索引擎。自成立以来,谷歌已获得30多个行业奖项。被誉为“网络上寻找答案的终极杀手”。2 谷歌矩阵2.1谷歌矩阵的基本定义谷歌的核心软件“PageRank (PageRank),它由谷歌创始人LarryPage和SergeyBrin斯坦福大学开发了一套系统用于web评级。当从网页链接到网页B时,谷歌为“网页中网页B,一票”。谷歌基于选票来评估网页的重要性。除了考虑纯web投票的数量(链接)外,谷歌还分析了投票页面。投票给“重要的”网页将具有更高的权重,并有助于提高其他网页的“重要性”。重要的,高质量的网页会得到
14、更高层次的web页面。e首先介绍了谷歌的诞生和特点,以及与谷歌搜索引擎相关的概念,定义和PageRank的引入.PageRank对一个网页所链接的所有网站进行评估,为它们分配一个值, 通过分析网络的总体结构,以满足用户的需求和利益,以确定哪些网站可以被评为最好的信息来源。这里我们介绍一些基本概念。要定义一个网页分类是基于“来自大量高质量网页的链接必须是高质量的网页”的关系返回,来确定所有网页的重要性。它有效利用了大型Web具有链接结构的特点。从Web链接被认为是一个指南页面B的投票支持,跨页面为页面B、谷歌,根据投票来确定页面的重要性。但谷歌并不是唯一一个只看到选票的。,也对投票页面进行分析。
15、高重要性页面的投票由评价会更高,由投票页面的PageRank,也会得到提高。根据这种分析,获得了较高评价的重要页面将会得到较高的页面排名,在搜索结果中的排名将会提高,并且每个页面都有一个特定的页面排名。PageRank值取决于链网页面的大小、链接到web页面的质量以及链数进入web页面的质量。定义A = 2谷歌矩阵(aij):网页的相关矩矩阵A的元素aij=1,如果从第I页到第j页有链接;否则for = 0。如用符号表示N页,则A为N * N的方阵,矩阵称为谷歌PageRank,是将矩阵转置。20为了将每个列向量的和化为1(全概率),每个列向量除以相应的链路计数。这叫做矩阵的转移概率矩阵,还记
16、得a吧,它在每一行向量之间表示状态转移的概率。转置是指PageRank不重视链接到很多地方,而是看重本地链接的价值有多大。20可以看作随机矩阵,最大特征值为1。PageRank计算,是最大的特征向量(称为Perron向量),即x = Ax。因为当t -,我们可以根据变换矩阵的最大特征值的绝对值和从“从根本上”属于它的特征向量。换句话说,用概率表示过程,重复乘法的一个过程,并且能够计算未来状态的概率。邻接表的位图(图1)Apache在线手册(128页)中表示如下。当黑点水平排列时,表示本页有很多正向链接(即导出链接);相反,当黑点垂直对齐时,这意味着页面有很多反向链接(入站链接)。图1图2迁移概
17、率矩阵有时也被称作马尔可夫矩阵.称马尔可夫过程的试验矩阵的观测结果为马尔可夫链.为了以下的证明我们说明几个数学用语:定义3从有向图S的状态i出发,将有限时间之后再次回到状态i的概率作为1时,也就是说,当沿着有向图S的方向前进能够回到原来位置的路径存在的时候,i就被称为回归.不能回归的状态被称为非回归.定义4有向状态图S称为强连通的,若从S中的任意状态i到任意状态j都有有向路径可以到达.对应的马尔可夫链的样本路径表示S的任意两点间以正的概率来往通行.定义5一个集合S称为马尔可夫链M上的一个不可约分支,若S生成M中的一个最大强连通子图,即没有一个M的强连通子图真包含S.PageRank就是一定时间
18、内用户随机地沿着(网页)链接前进时对各个页面访问的固定分布,并以此来反映各个网页的重要性.但是现实的网页并不都是强连通的.也就是说邻接矩阵不都是最简的.具体来说,有时顺着链接前进会走到完全没有向外链接的网页.由现实的Web页组成的迁移概率矩阵大部分都不是最简的,此时,最大特征值1为重根,当然对应的特征矢量也就不止一个.换句话说,PageRank这时并不唯一.为了解决这样的问题,考虑了一种改革模式,即用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里.进一步,将时常固定为15%来计算:即用户在85%的情况下沿着链接前进,但在15%的情况下会突然跳跃到无关的页面中去.若将
19、此用算式来表示,即得到A=cP+(1-c)ET(c=0.85).(*)矩阵A称作一般情形下的Google矩阵.这里P是一个nn行随机矩阵,相当于网络连接图的邻接矩阵,E是一个n阶秩1行随机矩阵,它的所有元素为1/n,0c1.一般情况下,c=0.85.事实上,迁移矩阵最简化就是把非强连通图变成强连通.对全部元素都考虑0.15的迁移概率,就意味着将原本非最简的迁移概率矩阵转换为最简并回归的迁移概率矩阵.这样就能保证最大特征值为单根.从而A的最大特征矢量(PageRank)被唯一决定.若用2表示A的(模)第二大特征值.我们将证明:1)当0c1时,有|2|c;2)若A可约,则2=c.2.2谷歌矩阵的理
20、论发展GooglePanda是对Google搜索结果排名算法的更改,该算法于2011年2月23日首次发布。此更改旨在降低低质量网站或精简网站的排名,并返回靠近搜索顶部的高质量网站结果。CNET报道新闻网站和社交网站的排名飙升,以及包含大量广告的网站排名下降。据报道,这一变化几乎占所有搜索结果的12。不久之后,许多网站,包括谷歌(Google)的超级论坛,纷纷抱怨说,与原创网站相比,版权/版权的排名要好得多。有一次,Google公开要求提供数据点以帮助更好地检测数据。谷歌的熊猫自2011年2月推出以来已经收到了一些更新,并且该活动于2011年4月全球化。为了帮助受欢迎的出版商,谷歌在其博客上发布
21、了一份咨询报告,从而为网站质量的自我评估提供了一些方向。谷歌在其博客上提供了23个要点的清单,回答了“什么算是一个高质量的网站?”的问题,这应该可以帮助网站管理员进入谷歌的思维模式。GooglePanda是通过算法更新构建的,该算法更新使用了比以前更加复杂和可扩展的人工智能。人类质量测试人员根据质量指标评估了数千个网站,包括设计,可信度,速度以及他们是否会返回网站。谷歌的新熊猫机器学习算法由工程师纳维内特熊猫(NavneetPanda)命名,然后被用来寻找被认为是高质量和低质量的网站之间的相似之处。GooglePenguin是2012年4月24日首次公布的Google算法更新的代号。此更新旨在
22、通过使用黑帽SEO技术(如关键字)降低违反GoogleGoogle网站管理员指南行的网站的搜索引擎排名学习,隐藏真实内容,参与链接方案,故意创建重复内容等。Penguin更新于2012年4月24日上线。根据Googles的估计,约3.1%的搜索查询涉及英语查询,约3%的查询涉及德语、汉语和阿拉伯语,更大比例的查询是以英语查询。2012年5月25日,谷歌发布了最新的升级版,名为ACM1.1。这一更新,应该影响不到十分之一到百分之十三的英语搜索.指导原则对于更新的网站来说,是要用更好的技术来达到更高的排名。2012年,发布了第3版本,影响了0.3%的查询。2012年1月,发布了所谓的页面布局算法更
23、新,该更新针对的是内容较少的网站。Panda,Penguin和页面布局更新共享的战略目标是在Googles搜索结果的顶部显示更高质量的网站。但是,由于这些更新而缩减的网站具有不同的特征集。GooglePenguin的主要目标是垃圾邮件索引(包括链接轰炸)。2.3谷歌矩阵的特征值和特征向量引理2.1若矩阵A为正矩阵(即A的每个元素为正),则|2|1.证因为矩阵A的第二特征值和AT的相同,且任何一个非负方阵的每个特征值的模不大于其最大行和(=1),这一点很容易由特征值的定义来证明.因为A为正矩阵,故A不可约(事实上A为本原),由Perrons定理知,1=1为A的单特征根,且其余特征值的模均小于它.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 谷歌矩阵及网页等级划分 矩阵 网页 等级 划分
限制150内