pagerank算法(pagerank算法原理)

pagerank算法

PageRank算法将网页按重要性进行排序。有了这个排序，人们在查找关键词时就能优先看到重要且优质的网页，然后更易于得到所需求的信息。
拉里·佩奇LarryPage和谢尔盖·布林SergeyBrin于1996年在斯坦福大学开发了PageRank算法，此后于1998年根据该算法，一起创立了Google公司。PageRank这个名字一语双关，既源于其算法创始人LarryPage，也源于网页WebPage。
二、PageRank算法的原理
PageRank是一种根据图论的算法。它将万维网上一切的网页视作节点node，将超链接视作边edge。网络中的每个节点都有一个PageRank值，表明该节点的重要程度。
PageRank的设计遭到学术论文引证启发。衡量一篇学术论文质量高与否，最重要的一个指标是引证次数，高引证量的论文通常意味着高质量。同理，假如一张网页被引证（参加超链接）的次数多了，那么该网页就比较重要。
PageRank的核心思维有两点（结合下图进行阐明）：
有越多的网页链接到某个网页，则阐明这个网页越重要，网页对应的PageRank值越高。例如图中的B有很多网页链接到它。
PageRank值高的网页链接到某个网页，则阐明这张网页也很重要。例如，图中的C尽管只要一张网页B链接到它，但C的重要性仍然很高。而图中的E尽管有很多网页链接到它，但仍然不如C重要。
如何核算节点的PageRank值呢？关于网页u，其PageRank值由以下公式算出：
其中，Bu表明u连接的一切网页，c为常数，R(v)为网页v的PageRank值，Nv为网页v的链接数（度Degree）。
PageRank算法经过输出概率散布来体现或人随机地点击某个网页的概率。在初次核算前，总概率将被均分到每个网页上，使得每个网页被访问的概率都是相同的。接下来在重复多次的核算（即迭代）中，算法将不断调整各网页的PageRank值，使得其越来越挨近最终的理论值。
三、PageRank算法的应用
PageRank算法适用于任何复杂网络相关范畴。例如，它被广泛用于剖析社会网络、信息网络、生物网络等，并应用在链接猜测和引荐系统中。
PageRank算法成功的基础在于“注意力经济”。查找排序顶部的网页获得更多的关注，有更大的概率进入人们的意识，然后进一步影响行为。因而，这些网页有更高的潜力能够让用户为他们的业务进行更多的付费。
除了商业外，PageRank算法还有其他范畴的应用。例如经过剖析科学论文协作网络，为作者和期刊排名，量化其范畴影响力。在体育运动中，PageRank算法可以对球队或者运动员的体现进行排名。在路途规划中，Pagerank算法可以对区域或大街进行排序，以猜测有多少行人或车辆来到各个区域或大街。
此外，运用PageRank算法可以：在蛋白质相互作用网络中猜测潜在的药物治疗靶点；在生态系统网络中确认对环境可持续发展不可或缺的物种；在神经网络中研究神经元的位置与其放电速率的相关性等等。

pagerank算法原理

PageRank算法是google的网页排序算法，在《TheTopTenAlgorithmsinDataMining》一书中第6章有介绍。大致原理是用户查找出的多个网页需要依照必定的重要程度（即后面讲的权重）排序，每个网页的权重由一切链接到它的其他网页的权重的加权和，加权系数为每个网页链出的网页数的倒数，也就是说每个网页的权重会平均分配到其链向的一切网页。
例如A链接到B和C，B链接到C，C链接到A，P（X）表明X的权重,如下图所示
则每个节点的权重关系为：
P(A)=P(C)
P(B)=P(A)/2
P(C)=P(A)/2+P(B)
一般地，能够写成个线性方程组方式：
P=AP
如此经过迭代即可求出终究各个网页的权重值。
可是，当存在某些特殊情况时，如某个网页的链入或链出数为0，则迭代不会收敛。因此在上述算法中增加了个阻尼系数d，d表明用户会持续点击下一网页的概率，一起用户在1-d的概率下会随机拜访到恣意网页，那么上面的公式会修正为：
P=(1-d)/N*ones(N,1)+d*AP
其间N为一切网页数，ones(N,1)表明N行1列的全1矩阵。经过上述公式能够迭代计算出终究各网页权重。