pagerank_pagerank算法 - CSDN
pagerank 订阅
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。 展开全文
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。
信息
外文名
google pagerank
开发公司
美国Google
中文名
网页排名
性    质
计算机领域的算法
google pagerank概念
PageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和 Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。PageRank将对页面的链接看成投票,指示了重要性。
收起全文
精华内容
参与话题
  • Pagerank算法论文包

    2020-07-25 23:31:40
    写论文时用过的pagerank 资料 写论文时用过的pagerank 资料
  • **一、什么是pagerank** PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。PageRank算法计算每一个网页的PageRank值...

    文章来源:http://www.cnblogs.com/fengfenggirl/p/pagerank-introduction.html
    **

    一、什么是pagerank

    **

      PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。PageRank算法计算每一个网页的PageRank值,然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

    **

    二、最简单pagerank模型

    **

      互联网中的网页可以看出是一个有向图,其中网页是结点,如果网页A有链接到网页B,则存在一条有向边A->B,下面是一个简单的示例:
      这里写图片描述

      这个例子中只有四个网页,如果当前在A网页,那么悠闲的上网者将会各以1/3的概率跳转到B、C、D,这里的3表示A有3条出链,如果一个网页有k条出链,那么跳转任意一个出链上的概率是1/k,同理D到B、C的概率各为1/2,而B到C的概率为0。一般用转移矩阵表示上网者的跳转概率,如果用n表示网页的数目,则转移矩阵M是一个n*n的方阵;如果网页j有k个出链,那么对每一个出链指向的网页i,有M[i][j]=1/k,而其他网页的M[i][j]=0;上面示例图对应的转移矩阵如下:
    这里写图片描述

      初试时,假设上网者在每一个网页的概率都是相等的,即1/n,于是初试的概率分布就是一个所有值都为1/n的n维列向量V0,用V0去右乘转移矩阵M,就得到了第一步之后上网者的概率分布向量MV0,(nXn)*(nX1)依然得到一个nX1的矩阵。下面是V1的计算过程:
    这里写图片描述

      注意矩阵M中M[i][j]不为0表示用一个链接从j指向i,M的第一行乘以V0,表示累加所有网页到网页A的概率即得到9/24。得到了V1后,再用V1去右乘M得到V2,一直下去,最终V会收敛,即Vn=MV(n-1),上面的图示例,不断的迭代,最终V=[3/9,2/9,2/9,2/9]’:
    这里写图片描述

    **

    三、终止点问题

    **

      上述上网者的行为是一个马尔科夫过程的实例,要满足收敛性,需要具备一个条件:

    图是强连通的,即从任意网页可以到达其他任意网页:
      互联网上的网页不满足强连通的特性,因为有一些网页不指向任何网页,如果按照上面的计算,上网者到达这样的网页后便走投无路、四顾茫然,导致前面累计得到的转移概率被清零,这样下去,最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉,C变成了一个终止点,得到下面这个图:
    这里写图片描述

      对应的转移矩阵为:
    这里写图片描述

      连续迭代下去,最终所有元素都为0:  

    这里写图片描述

    四、陷阱问题

      另外一个问题就是陷阱问题,即有些网页不存在指向其他网页的链接,但存在指向自己的链接。比如下面这个图:

    这里写图片描述

      上网者跑到C网页后,就像跳进了陷阱,陷入了漩涡,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为: 
    这里写图片描述

      不断的迭代下去,就变成了这样:

    这里写图片描述

    五、解决终止点问题和陷阱问题

      上面过程,我们忽略了一个问题,那就是上网者是一个悠闲的上网者,而不是一个愚蠢的上网者,我们的上网者是聪明而悠闲,他悠闲,漫无目的,总是随机的选择网页,他聪明,在走到一个终结网页或者一个陷阱网页(比如两个示例中的C),不会傻傻的干着急,他会在浏览器的地址随机输入一个地址,当然这个地址可能又是原来的网页,但这里给了他一个逃离的机会,让他离开这万丈深渊。模拟聪明而又悠闲的上网者,对算法进行改进,每一步,上网者可能都不想看当前网页了,不看当前网页也就不会点击上面的连接,而上悄悄地在地址栏输入另外一个地址,而在地址栏输入而跳转到各个网页的概率是1/n。假设上网者每一步查看当前网页的概率为a,那么他从浏览器地址栏跳转的概率为(1-a),于是原来的迭代公式转化为:

    这里写图片描述

      现在我们来计算带陷阱的网页图的概率分布:
    这里写图片描述

      重复迭代下去,得到:
    这里写图片描述
    (因为转载,计算结果没做验证,结果正确与否有待检验)

      可以看到C虽然占了很大一部分pagerank值,但其他网页页获得的一些值,因此C的链接结构,它的权重确实应该会大些。

    展开全文
  • PageRank算法原理与实现

    万次阅读 多人点赞 2019-07-05 10:19:40
    正文共835个字,8张图,预计阅读时间6分钟。1、PageRank1.1.简介PageRank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的...
        


    正文共835个字,8张图,预计阅读时间6分钟。


    1、PageRank


    1.1.简介


    PageRank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。


    假设一个由4个网页组成的群体:A,B,C和D。如果所有页面都只链接至A,那么A的PR(PageRank)值将是B,C及D的Pagerank总和。


    640?wx_fmt=png


    重新假设B链接到A和C,C只链接到A,并且D链接到全部其他的3个页面。一个页面总共只有一票。所以B给A和C每个页面半票。以同样的逻辑,D投出的票只有三分之一算到了A的PageRank上。


    640?wx_fmt=png


    1.2.公式


    对于一个页面A,那么它的PR值为:


    640?wx_fmt=png


    • PR(A) 是页面A的PR值

    • PR(Ti)是页面Ti的PR值,在这里,页面Ti是指向A的所有页面中的某个页面

    • C(Ti)是页面Ti的出度,也就是Ti指向其他页面的边的个数

    • d 为阻尼系数,其意义是,在任意时刻,用户到达某页面后并继续向后浏览的概率,


    该数值是根据上网者使用浏览器书签的平均频率估算而得,通常d=0.85


    还有一个版本的公式:


    640?wx_fmt=png


    N为页面的总数


    1.3.具体实例


    640?wx_fmt=png

    三个页面A、B、C


    为了便于计算,我们假设每个页面的PR初始值为1,d为0.5。


    • 页面A的PR值计算如下:

    640?wx_fmt=png

    • 页面B的PR值计算如下:

    640?wx_fmt=png

    • 页面C的PR值计算如下:

    640?wx_fmt=png


    下面是迭代计算12轮之后,各个页面的PR值:



    640?wx_fmt=png


    那么什么时候,迭代结束哪?一般要设置收敛条件:比如上次迭代结果与本次迭代结果小于某个误差,我们结束程序运行;比如还可以设置最大循环次数。


    2、代码实现


     1import numpy as np
    2from scipy.sparse import csc_matrix
    3
    4def pageRank(G, s=.85, maxerr=.0001):
    5"""
    6Computes the pagerank for each of the n states
    7Parameters
    8----------
    9G: matrix representing state transitions
    10Gij is a binary value representing a transition from state i to j.
    11s: probability of following a transition. 1-s probability of teleporting
    12to another state.
    13maxerr: if the sum of pageranks between iterations is bellow this we will
    14    have converged.
    15"""

    16n = G.shape[0]
    17# 将 G into 马尔科夫 A
    18A = csc_matrix(G, dtype=np.float)
    19rsums = np.array(A.sum(1))[:, 0]
    20ri, ci = A.nonzero()
    21A.data /= rsums[ri]
    22sink = rsums == 0
    23# 计算PR值,直到满足收敛条件
    24ro, r = np.zeros(n), np.ones(n)
    25while np.sum(np.abs(r - ro)) > maxerr:
    26ro = r.copy()
    27for i in range(0, n):
    28    Ai = np.array(A[:, i].todense())[:, 0]
    29    Di = sink / float(n)
    30    Ei = np.ones(n) / float(n)
    31    r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))
    32 # 归一化
    33 return r / float(sum(r))
    34 if __name__ == '__main__':
    35 # 上面的例子
    36 G = np.array([[001],
    37          [100],
    38          [110]])
    39 print(pageRank(G, s=0.85))
    40 # 结果:
    41 [0.51203622 0.19313191 0.29483187]

    3、参考资料


    1、Pagerank Algorithm Explained(https://www.slideshare.net/jdhaar/pagerank-algorithm-explaned)


    2、【大创_社区划分】——PageRank算法的解析与Python实现(https://blog.csdn.net/gamer_gyt/article/details/47443877)


    3、浅入浅出:PageRank算法(https://www.letiantian.me/2014-06-10-pagerank/)


    4、PageRankhttps://en.wikipedia.org/wiki/PageRank


    原文链接:https://www.jianshu.com/p/6af90342c3ba


    查阅更为简洁方便的分类文章以及最新的课程、产品信息,请移步至全新呈现的“LeadAI学院官网”:

    www.leadai.org


    请关注人工智能LeadAI公众号,查看更多专业文章

    640?wx_fmt=jpeg

    大家都在看

    640.png?

    LSTM模型在问答系统中的应用

    基于TensorFlow的神经网络解决用户流失概览问题

    最全常见算法工程师面试题目整理(一)

    最全常见算法工程师面试题目整理(二)

    TensorFlow从1到2 | 第三章 深度学习革命的开端:卷积神经网络

    装饰器 | Python高级编程

    今天不如来复习下Python基础

    展开全文
  • PageRank算法

    万次阅读 多人点赞 2012-09-24 16:17:03
    1. PageRank算法概述  PageRank,即网页排名,又称网页级别、Google左侧排名或佩奇排名。  是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法,自从Google在商业上获得...

    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。这个重要性得分值为:PR(T)/L(T)

         其中PR(T)为T的PageRank值,L(T)为T的出链数

            则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

            即一个页面的得票数由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

    3.3 PageRank简单计算:

           假设一个由只有4个页面组成的集合:A,B,C和D。如果所有页面都链向A,那么A的PR(PageRank)值将是B,C及D的和。

          

           继续假设B也有链接到C,并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑,D投出的票只有三分之一算到了A的PageRank上。

          

          换句话说,根据链出总数平分一个页面的PR值。

          

    例子:

            如图1 所示的例子来说明PageRank的具体计算过程。  

                               

           

     

    3.4  修正PageRank计算公式:

             由于存在一些出链为0,也就是那些不链接任何其他网页的网, 也称为孤立网页,使得很多网页能被访问到。因此需要对 PageRank公式进行修正,即在简单公式的基础上增加了阻尼系数(damping factor)q, q一般取值q=0.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:

           

                                        网页间的链接关系

          显然这个图是强连通的(从任一节点出发都可以到达另外任何一个节点)。

          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矩阵计算过程。


          1)P概率转移矩阵  :

          

          2)/N 为:

        

          3)A矩阵为: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算法的分析及实现

    《这就是搜索引擎:核心技术详解》

     

     

    展开全文
  • PageRank - 原理及代码解析

    千次阅读 2019-09-26 15:34:27
    而它是由PageRank改进而来的。 来源 搜索引擎中用到,用来进行网页重要性的排名。 谷歌创始人,斯坦福大学的佩奇和布林参考学术界对论文重要性的评判方法,引用次数越多说明约重要。 PageRank思想类似: 如果一个...

    前言

    因为最近要准备毕业设计了,论文设计到抽取句子中的关键词,要用到TextRank算法。而它是由PageRank改进而来的。

    来源

    搜索引擎中用到,用来进行网页重要性的排名。
    谷歌创始人,斯坦福大学的佩奇和布林参考学术界对论文重要性的评判方法,引用次数越多说明约重要。
    PageRank思想类似:

    • 如果一个网页被其他很多网页链接,则重要,权值高。
    • 如果PageRank值高的网页链接某个网页,则该网页权值也提高。

    模型

    将网页抽象成节点。举个例子,4个网页A,B,C,D。如图
    在这里插入图片描述
    对于A来说,A指向B,C,D. 因为分成了3分,所以每条支路只能算1/3的权重。
    输入形式采用json格式,如下:

    {"A":["B","C","D"], "B":["A","C"], "C":["D"], "D":["A","B"]}
    

    把上面的图写成转移矩阵M的形式:
    M=[AABACADAABBBCBDBACBCCCDCADBDCDDD] M = \begin{bmatrix} A\rightarrow A & B\rightarrow A & C\rightarrow A &D\rightarrow A \\ A\rightarrow B & B\rightarrow B & C\rightarrow B &D\rightarrow B \\ A\rightarrow C & B\rightarrow C & C\rightarrow C &D\rightarrow C \\ A\rightarrow D & B\rightarrow D & C\rightarrow D &D\rightarrow D \\ \end{bmatrix}
    对应这个例子M为:

        [[0.         0.5        0.         0.5       ]
         [0.33333333 0.         0.         0.5       ]
         [0.33333333 0.5        0.         0.        ]
         [0.33333333 0.         1.         0.        ]]
    

    构建M矩阵代码:

    def to_matrix(d):
        var = get_all_variables(d)
        n = len(var)
        # {'A': 0, 'B': 1, 'C': 2, 'D': 3}
        char2id = {var[i]:i for i in range(n)}
        M = np.zeros((n,n))
        # 构造M矩阵,先统计,后平均
        #[A->A  B->A  C->A  D->A]
        #[A->B  B->B  C->B  D->B] 等等
        # 统计
        for ch in var: #例如A
            for to in d[ch]: #["B","C","D"]
                y = char2id[ch]
                x = char2id[to]
                M[x][y] += 1
        '''M:
        [[0. 1. 0. 1.]
         [1. 0. 0. 1.]
         [1. 1. 0. 0.]
         [1. 0. 1. 0.]]
        '''
        #在列维度上取平均
        for j in range(n):
            sum1 = 0
            for i in range(n):
                sum1 += M[i][j]
            if sum1>0:
                for i in range(n):
                    M[i][j] /= sum1
        '''M:
        [[0.         0.5        0.         0.5       ]
         [0.33333333 0.         0.         0.5       ]
         [0.33333333 0.5        0.         0.        ]
         [0.33333333 0.         1.         0.        ]]
        '''
        return np.matrix(M)
    

    计算

    在这里插入图片描述
    初始权重为1/N
    从上图可以看出,可以用矩阵的乘法来快速计算。

    实验结果:
    在这里插入图片描述

    代码实现:

    import json
    import numpy as np
    def to_matrix(d):
        var = get_all_variables(d)
        n = len(var)
        # {'A': 0, 'B': 1, 'C': 2, 'D': 3}
        char2id = {var[i]:i for i in range(n)}
        M = np.zeros((n,n))
        # 构造M矩阵,先统计,后平均
        #[A->A  B->A  C->A  D->A]
        #[A->B  B->B  C->B  D->B] 等等
        # 统计
        for ch in var: #例如A
            for to in d[ch]: #["B","C","D"]
                y = char2id[ch]
                x = char2id[to]
                M[x][y] += 1
        '''M:
        [[0. 1. 0. 1.]
         [1. 0. 0. 1.]
         [1. 1. 0. 0.]
         [1. 0. 1. 0.]]
        '''
        #在列维度上取平均
        for j in range(n):
            sum1 = 0
            for i in range(n):
                sum1 += M[i][j]
            if sum1>0:
                for i in range(n):
                    M[i][j] /= sum1
        '''M:
        [[0.         0.5        0.         0.5       ]
         [0.33333333 0.         0.         0.5       ]
         [0.33333333 0.5        0.         0.        ]
         [0.33333333 0.         1.         0.        ]]
        '''
        return np.matrix(M)
    
    def diedai(M, p):#迭代
        #矩阵相乘要用matmul,而不是multily
        #(4,4) * (4,1)
        return np.matmul(M,p)
    
    def get_all_variables(d):
        s = set()
        #把所有元素加入集合中
        for k,v in d.items():
            s.add(k)
            for t in v:
                s.add(t)
        var = list(s)
        var.sort() #['A', 'B', 'C', 'D']
        return var
    
    def page_rank(d,m):
        #迭代m次
        var = get_all_variables(d)
        M = to_matrix(d)
        tmp = 1.0/len(var)
        p = np.ones((len(var),1))*tmp
        p = np.matrix(p) #matrix可以直接p[0,0]这样取值
        print("iteration\tPR(A)\tPR(B)\tPR(C)\tPR(D)")
        print("{}\t{:.4f}\t{:.4f}\t{:.4f}\t".format(0,p[0,0],p[1,0],p[2,0],p[3,0]))
        for i in range(m):
            p = diedai(M,p) #用:.4f方式保留小数
            print("{}\t{:.4f}\t{:.4f}\t{:.4f}\t".format(i+1, p[0, 0], p[1, 0], p[2, 0], p[3, 0]))
        '''
        m=1时,p:
        [[0.25      ]
         [0.20833333]
         [0.20833333]
         [0.33333333]]
         '''
        return p
    
    
    if __name__=="__main__":
        # str1 = input().strip()
        str1 = '''{"A":["B","C","D"], "B":["A","C"], "C":["D"], "D":["A","B"]}'''
        d = json.loads(str1)
        res = page_rank(d,10)
    
    

    补充

    这只是最简答的形式,实际上会做一个平滑处理:
    d常取0.85,
    PR(A)=(1d)+d(PR(T1))L(T1))+...+PR(Tn)L(Tn)) PR(A) = (1-d) + d(\frac{PR(T_{1}))}{L(T_{1}))} + ... + \frac{PR(T_{n})}{L(T_{n})})

    参考:PageRank 笔记

    展开全文
  • pagerank原理总结

    千次阅读 2016-08-16 14:16:17
    1.pagerank算法概述 又名网页排名,是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法,自从Google在商业上获得空前的成功后,该算法也成为其他搜索引擎和学术界十分关注...
  • 机器学习:PageRank

    千次阅读 2020-10-17 11:27:03
    PageRank 核心思想 PageRank算法 PageRank算法总的来说就是预先给每个网页一个PR值(下面用PR值指代PageRank值),由于PR值物理意义上为一个网页被访问概率,所以一般是1N\frac{1}{N}N1​,其中N为网页总数。...
  • PageRank学习一

    2016-06-21 10:42:55
    The Google Pagerank Algorithm and How It Works Ian Rogers IPR Computing Ltd. ian@iprcom.com Introduction Page Rank is a topic much discussed by Search Engine Optimisation (SEO) experts. At the h
  • pagerank以及个性化的pagerank算法

    千次阅读 2015-07-21 20:11:40
    pagerank以及个性化的pagerank算法 pagerank最开始是Google提出来用来衡量网页重要度排行的算法。 她的思想是基于网页之间互相的链接作为加权投票。假如网页a指向b, 那么网页b的重要程度受网页a的影响,a...
  • 如何优雅的理解PageRank

    千次阅读 2019-08-23 22:51:36
    终于Tex调好了 刚好最近又多次提及PageRank 于是~ 目测这一系列 有个两三篇blog PageRank 是 由佩奇(Larry Page)等人提出 的 Google 最为有名的技术之一 我 乔治 甘拜下风 PageRank 是一种基于随机游走 的 ...
  • PageRank 笔记

    千次阅读 多人点赞 2020-09-18 22:45:37
    PageRank 要说到 PageRank 算法的来源,这个要从搜索引擎的发展讲起。最早的搜索引擎采用的是分类目录的方法,即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用这种方法。 后来...
  • PageRank算法(二)

    千次阅读 2019-02-26 09:52:57
    说明:这是我学习过程中看到对PageRank来龙去脉解释非常清晰的博客,博主很厉害,大家可以关注一下原创作者! 一、PageRank算法的简单举例 Google PageRank算法的思想精华在于:将一个网页级别/重要性的排序问题...
  • PageRank

    千次阅读 2014-03-12 16:49:49
    PageRank生成的Web网页排序是静态的,这是指每个网页的排序值是通过离线计算得到的,并且该值与查询无关。也就是说,网页排序值的计算纯粹基于Web上现有链接,而不考虑任何用户的任何查询。 知识背景: ...
  • pagerank

    2013-04-24 00:20:52
     通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算,PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量,而是将从网页 A 指向网页 B 的链接解释为由网页 A ...
  • 浅谈PageRank

    万次阅读 多人点赞 2017-04-25 19:14:54
    1996年,两位还在斯坦福大学攻读计算机理学博士学位的研究生,开始了一项研究:如何对互联网上“成万上亿”的网页进行排序。在当时看来,这只是发生在斯坦福的一个普通课题研究而已,然而包括其研究者在内,都没有...
  • GraphX PageRank

    千次阅读 2014-11-17 11:04:52
    GraphX算法模型:PageRank 一:算法介绍  PageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。 一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个...
1 2 3 4 5 ... 20
收藏数 16,857
精华内容 6,742
关键字:

pagerank