展示型企业网站例子,好的网站制作平台,外贸网络营销实战,以下属于免费推广的方式是1. PageRank算法概述 PageRank,即网页排名#xff0c;又称网页级别、Google左側排名或佩奇排名。 是Google创始人拉里佩奇和谢尔盖布林于1997年构建早期的搜索系统原型时提出的链接分析算法#xff0c;自从Google在商业上获得空前的成功后#xff0c;该算法也成为其他搜索引… 1. PageRank算法概述 PageRank,即网页排名又称网页级别、Google左側排名或佩奇排名。 是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法自从Google在商业上获得空前的成功后该算法也成为其他搜索引擎和学术界十分关注的计算模型。眼下许多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法是Google用来衡量一个站点的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等全部其他因素之后Google通过PageRank来调整结果使那些更具“等级/重要性”的网页在搜索结果中另站点排名获得提升从而提高搜索结果的相关性和质量。其级别从0到10级10级为满分。PR值越高说明该网页越受欢迎越重要。比如一个PR值为1的站点表明这个站点不太具有流行度而PR值为7到10则表明这个站点很受欢迎或者说极其重要。一般PR值达到4就算是一个不错的站点了。Google把自己的站点的PR值定到10这说明Google这个站点是很受欢迎的也能够说这个站点很重要。 2. 从入链数量到 PageRank 在PageRank提出之前已经有研究者提出利用网页的入链数量来进行链接分析计算这样的入链方法如果一个网页的入链越多则该网页越重要。早期的非常多搜索引擎也採纳了入链数量作为链接分析方法对于搜索引擎效果提升也有较明显的效果。 PageRank除了考虑到入链数量的影响还參考了网页质量因素两者相结合获得了更好的网页重要性评价标准。 对于某个互联网网页A来说该网页PageRank的计算基于下面两个基本如果 数量如果在Web图模型中如果一个页面节点接收到的其它网页指向的入链数量越多那么这个页面越重要。 质量如果指向页面A的入链质量不同质量高的页面会通过链接向其它页面传递很多其它的权重。所以越是质量高的页面指向页面A则页面A越重要。 利用以上两个如果PageRank算法刚開始赋予每一个网页同样的重要性得分通过迭代递归计算来更新每一个页面节点的PageRank得分直到得分稳定为止。 PageRank计算得出的结果是网页的重要性评价这和用户输入的查询是没有不论什么关系的即算法是主题无关的。如果有一个搜索引擎其相似度计算函数不考虑内容相似因素全然採用PageRank来进行排序那么这个搜索引擎的表现是什么样子的呢这个搜索引擎对于随意不同的查询请求返回的结果都是同样的即返回PageRank值最高的页面。 3. PageRank算法原理 PageRank的计算充分利用了两个如果数量如果和质量如果。过程例如以下 1在初始阶段网页通过链接关系构建起Web图每一个页面设置同样的PageRank值通过若干轮的计算会得到每一个页面所获得的终于PageRank值。随着每一轮的计算进行网页当前的PageRank值会不断得到更新。 2在一轮中更新页面PageRank得分的计算方法在一轮更新页面PageRank得分的计算中每一个页面将其当前的PageRank值平均分配到本页面包括的出链上这样每一个链接即获得了对应的权值。而每一个页面将全部指向本页面的入链所传入的权值求和就可以得到新的PageRank得分。当每一个页面都获得了更新后的PageRank值就完毕了一轮PageRank计算。 3.2 基本思想 假设网页T存在一个指向网页A的连接则表明T的全部者觉得A比較重要从而把T的一部分重要性得分赋予A。这个重要性得分值为PRT/L(T) 当中PRT为T的PageRank值L(T)为T的出链数 则A的PageRank值为一系列类似于T的页面重要性得分值的累加。 即一个页面的得票数由全部链向它的页面的重要性来决定到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由全部链向它的页面链入页面的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级相反假设一个页面没有不论什么链入页面那么它没有等级。 3.3 PageRank简单计算 如果一个由仅仅有4个页面组成的集合ABC和D。如果全部页面都链向A那么A的PRPageRank值将是BC及D的和。 继续如果B也有链接到C而且D也有链接到包含A的3个页面。一个页面不能投票2次。所以B给每一个页面半票。以相同的逻辑D投出的票仅仅有三分之中的一个算到了A的PageRank上。 换句话说依据链出总数平分一个页面的PR值。 样例 如图1 所看到的的样例来说明PageRank的详细计算过程。 3.4 修正PageRank计算公式 因为存在一些出链为0也就是那些不链接不论什么其它网页的网 也称为孤立网页使得非常多网页能被訪问到。因此须要对 PageRank公式进行修正即在简单公式的基础上添加了阻尼系数damping factorq q一般取值q0.85。 其意义是在随意时刻用户到达某页面后并继续向后浏览的概率。 1- q 0.15就是用户停止点击随机跳到新URL的概率的算法被用到了全部页面上估算页面可能被上网者放入书签的概率。 最后即全部这些被换算为一个百分比再乘上一个系数q。因为以下的算法没有页面的PageRank会是0。所以Google通过数学系统给了每一个页面一个最小值。 这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定义的公式。 所以一个页面的PageRank是由其它页面的PageRank计算得到。Google不断的反复计算每一个页面的PageRank。假设给每一个页面一个随机PageRank值非0那么经过不断的反复计算这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。 4. PageRank幂法计算(线性代数应用) 4.1 完整公式 关于这节内容能够查阅谷歌背后的数学 首先求完整的公式 Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准确的表达为 是被研究的页面是链入页面的数量是链出页面的数量而N是全部页面的数量。 PageRank值是一个特殊矩阵中的特征向量。这个特征向量为 R是例如以下等式的一个解 假设网页i有指向网页j的一个链接则 否则0。 4.2 使用幂法求PageRank 那我们PageRank 公式能够转换为求解的值 当中矩阵为 A q × P ( 1 一 q) * /N 。 P 为概率转移矩阵为 n 维的全 1 行. 则 幂法计算步骤例如以下 X 设随意一个初始向量, 即设置初始每一个网页的 PageRank值均。一般为1. R AX; while (1 )( if ( l X - R I ) { //假设最后两次的结果近似或者同样返回R return R; } else { X R; R AX; } } 4.3 求解步骤 一、 P概率转移矩阵的计算过程: 先建立一个网页间的链接关系的模型,即我们须要合适的数据结构表示页面间的连接关系。 1) 首先我们使用图的形式来表述网页之间关系 如今如果仅仅有四张网页集合A、B、C其抽象结构例如以下图1 图1 网页间的链接关系 显然这个图是强连通的从任一节点出发都能够到达另外不论什么一个节点。 2我们用矩阵表示连通图 用邻接矩阵 P表示这个图中顶点关系 假设顶页面i向顶点页面j有链接情况 则pij 1 否则pij 0 。如图2所看到的。假设网页文件总数为N 那么这个网页链接矩阵就是一个N x N 的矩 阵 。 3网页链接概率矩阵 然后将每一行除以该行非零数字之和即每行非0数之和就是链接网个数则得到新矩阵P’如图3所看到的。 这个矩阵记录了 每一个网页跳转到其它网页的概率即当中i行j列的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C所以一个用户从A跳转到B、C的概率各为1/2。 4概率转移矩阵P 採用P’ 的转置矩 阵进行计算 也就是上面提到的概率转移矩阵P 。 如图4所看到的 图2 网页链接矩阵 图3 网页链接概率矩阵 图4 P’ 的转置矩 阵 二、 A矩阵计算过程。 1P概率转移矩阵 : 2/N 为 3A矩阵为q × P ( 1 一 q) * /N 0.85 × P 0.15 * /N 初始每一个网页的 PageRank值均为1 即X~t ( 1 1 1 ) 。 三、 循环迭代计算PageRank的过程 第一步 由于X 与R的区别较大。 继续迭代。 第二步 继续迭代这个过程... 直到最后两次的结果近似或者同样即R终于收敛R 约等于X此时计算停止。终于的R 就是各个页面的 PageRank 值。 用幂法计算PageRank 值总是收敛的即计算的次数是有限的。 Larry Page和Sergey Brin 两人从理论上证明了不论初始值怎样选取这样的算法都保证了网页排名的预计值能收敛到他们的真实值。 因为互联网上网页的数量是巨大的上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。假设我们假定有十亿个网页那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘计算量是很大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧大大的简化了计算量。 5. PageRank算法优缺点 长处 是一个与查询无关的静态算法全部网页的PageRank值通过离线计算获得有效降低在线查询时的计算量极大降低了查询响应时间。 缺点 1人们的查询具有主题特征PageRank忽略了主题相关性导致结果的相关性和主题性减少 2旧的页面等级会比新页面高。由于即使是非常好的新页面也不会有非常多上游链接除非它是某个网站的子网站。 參考文献 维基百科http://en.wikipedia.org/wiki/Page_rank PageRank算法的分析及实现 《这就是搜索引擎:核心技术具体解释》 转载于:https://www.cnblogs.com/gcczhongduan/p/4050781.html
