Ken*_*edy 21 algorithm math search pagerank
我是一名学生,有兴趣开发一个索引来自我国的网页的搜索引擎.我一直在研究使用的算法,我已经确定HITS和PageRank是最好的.我决定使用PageRank,因为它比HITS算法更稳定(或者我读过).
我找到了无数与PageRank相关的文章和学术论文,但我的问题是我不理解在这些论文中形成算法的大多数数学符号.具体来说,我不明白如何计算Google Matrix(不可缩减的随机矩阵).
我的理解是基于这两篇文章:
有人可以用较少的数学符号提供基本的解释(例子会很好)吗？
提前致谢.
mjv*_*mjv 26
如引用文件第4页所定义的PageRank的正式定义用数字方程表示,带有有趣的"E"符号(实际上是大写的Sigma希腊字母.Sigma是字母"S",在这里代表为求和).
简而言之,这个公式说要计算第X页的PageRank ......
For all the backlinks to this page (=all the pages that link to X)
you need to calculate a value that is
The PageRank of the page that links to X [R'(v)]
divided by
the number of links found on this page. [Nv]
to which you add
some "source of rank", [E(u)] normalized by c
(we'll get to the purpose of that later.)
And you need to make the sum of all these values [The Sigma thing]
and finally, multiply it by a constant [c]
(this constant is just to keep the range of PageRank manageable)
这个公式的关键思想是链接到给定页面X的所有网页都在为其"价值"增加价值.通过链接到某个页面,他们"投票"赞成此页面.然而,这种"投票"或多或少有重量,取决于两个因素:
这两个因素反映了非常直观的想法:
正如您所注意到的,此公式使用了一些循环引用,因为要知道X的页面范围,您需要知道链接到X的所有页面的PageRank.那么如何计算这些PageRank值？...这是文件一节中解释的下一个收敛问题.
基本上,通过开始一些"随机"(或优选"体面猜测"的PageRank值,对于所有页面,并通过使用上面的公式计算PageRank,新的计算值变得"更好",因为您迭代此过程一些这些值会收敛,即它们各自越来越接近实际/理论值.因此,通过迭代足够的次数,我们达到一个时刻,当额外的迭代不会给由此提供的值增加任何实际精度时.最后一次迭代.
现在......从理论上讲,那是好事和花花公子.诀窍是将此算法转换为等效的,但可以更快地完成.有几篇论文描述了如何完成这项任务和类似的任务.我手边没有这样的引用,但稍后会添加这些引用.要注意它们会涉及健康剂量的线性代数.
编辑:正如所承诺的,这里有一些关于计算页面排名的算法的链接. PageRank Haveliwala的有效计算1999 /// 利用网络块结构进行计算PR Kamvar etal 2003 /// 一个快速的两阶段计算算法PageRank Lee et al.2002年
尽管上面提供的链接的许多作者都来自斯坦福大学,但不久就会意识到寻求有效的类PageRank计算是一个热门的研究领域.我意识到这种材料超出了OP的范围,但重要的是暗示基本算法对大型网络不实用.
要完成一个非常易于访问的文本(但有许多链接到深入的信息),我想提及维基百科的优秀文章
如果你对这类事情很认真,你可以考虑数学的入门/复习课,特别是线性代数,以及一般处理图形的计算机科学课.顺便提一下,迈克尔·多尔夫曼在这篇文章中对OCW的1806年讲座视频提出了很好的建议.
我希望这能有所帮助...
如果您认真考虑为搜索引擎开发算法,我认真建议您参加线性代数课程.在没有面对面课程的情况下,Gilbert Strang的麻省理工学院开放式课程非常好(视频讲座见http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/).
像这样的课程肯定会让你理解你提供的文件中的数学符号 - 那篇论文中没有任何内容在第一年的线性代数课程中没有涉及.
我知道这不是您正在寻找的答案,但它确实是您的最佳选择.当你没有很好地掌握基本概念时,有人试图向你解释个别符号或算法并不能很好地利用任何人的时间.
这是您需要的论文:http://infolab.stanford.edu/~backrub/google.html(如果您不认识作者的姓名,您可以在此处找到有关他们的更多信息:http:// www .google.com/corporate/execs.html).
文档中使用的符号在英文文档中描述.
谢谢你让我谷歌这个.