【大创_社区划分】——PageRank算法的解析与Python实现-阿里云开发者社区

开发者社区> thinkgamer.cn> 正文

【大创_社区划分】——PageRank算法的解析与Python实现

简介: 一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
+关注继续查看

一、什么是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),于是原来的迭代公式转化为:


现在我们来计算带陷阱的网页图的概率分布:

重复迭代下去,得到:


六、用Python实现Page Rank算法


from numpy import *

a = array([[0,1,1,0],
           [1,0,0,1],
           [1,0,0,1],
           [1,1,0,0]],dtype = float)  #dtype指定为float

def graphMove(a):   #构造转移矩阵
    b = transpose(a)  #b为a的转置矩阵
    c = zeros((a.shape),dtype = float)
    for i in range(a.shape[0]):
        for j in range(a.shape[1]):
            c[i][j] = a[i][j] / (b[j].sum())  #完成初始化分配
    #print c,"\n===================================================="
    return c

def firstPr(c):   #pr值得初始化
    pr = zeros((c.shape[0],1),dtype = float)  #构造一个存放pr值得矩阵
    for i in range(c.shape[0]):
        pr[i] = float(1)/c.shape[0]
    #print pr,"\n==================================================="
    return pr
    
def pageRank(p,m,v):  #计算pageRank值
    while((v == p*dot(m,v) + (1-p)*v).all()==False):  #判断pr矩阵是否收敛,(v == p*dot(m,v) + (1-p)*v).all()判断前后的pr矩阵是否相等,若相等则停止循环
        #print v
        v = p*dot(m,v) + (1-p)*v
        #print (v == p*dot(m,v) + (1-p)*v).all()
    return v

if __name__=="__main__":
    M = graphMove(a)
    pr = firstPr(M)
    p = 0.8           #引入浏览当前网页的概率为p,假设p=0.8
    print pageRank(p,M,pr)  # 计算pr值  


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)
14 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(红黑树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(红黑树)
12 0
go解析Prometheus的数据
访问一个api, 返回如下数据: {"status":"success","data":{"resultType":"matrix","result":[{"metric":{},"values":[[1473820558.
1484 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(线段树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(线段树)
13 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(映射)
【愚公系列】2021年11月 C#版 数据结构与算法解析(映射)
7 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(哈希)
【愚公系列】2021年11月 C#版 数据结构与算法解析(哈希)
8 0
十大经典排序算法动画与解析,看我就够了!(配代码完全版) | 算法必看系列三十八
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为 内部排序 和 外部排序 。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
1431 0
+关注
thinkgamer.cn
wechat 搜索【数据与算法联盟】,专注于云计算和算法,目前就职于京东
237
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载