关灯

PageRank算法原理与实现

[复制链接]
admin 发表于 2019-1-20 13:10:28 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
 

1、PageRank

1.1.简介

PageRank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。假设一个由4个网页组成的群体:A,B,C和D。如果所有页面都只链接至A,那么A的PR(PageRank)值将是B,C及D的Pagerank总和。

 

1532762247287744613.jpg

 

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

 

1532762238832115527.jpg

 

 

1.2.公式

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

1532762264513765890.jpg

 

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

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

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

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

 

该数值是根据上网者使用浏览器书签的平均频率估算而得,通常d=0.85还有一个版本的公式:

 

1532762167655218595.jpg

N为页面的总数

 

 

1.3.具体实例

1532762159949967486.jpg

 

 

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

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

 

1532762153669456933.jpg

 

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

1532762147268488165.jpg

 

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

1532762141558183138.jpg

 

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

 

1532762134982268920.jpg

 

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

 

 

2、代码实现

  1. import numpy as np
  2. from scipy.sparse import csc_matrix
  3. def pageRank(G, s=.85, maxerr=.0001):
  4. """
  5. Computes the pagerank for each of the n states
  6. Parameters
  7. ----------
  8. G: matrix representing state transitions
  9. Gij is a binary value representing a transition from state i to j.
  10. s: probability of following a transition. 1-s probability of teleporting
  11. to another state.
  12. maxerr: if the sum of pageranks between iterations is bellow this we will
  13.     have converged.
  14. """
  15. n = G.shape[0]
  16. # 将 G into 马尔科夫 A
  17. A = csc_matrix(G, dtype=np.float)
  18. rsums = np.array(A.sum(1))[:, 0]
  19. ri, ci = A.nonzero()
  20. A.data /= rsums[ri]
  21. sink = rsums == 0
  22. # 计算PR值,直到满足收敛条件
  23. ro, r = np.zeros(n), np.ones(n)
  24. while np.sum(np.abs(r - ro)) > maxerr:
  25. ro = r.copy()
  26. for i in range(0, n):
  27.    Ai = np.array(A[:, i].todense())[:, 0]
  28.     Di = sink / float(n)
  29.     Ei = np.ones(n) / float(n)
  30.    r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))
  31.  # 归一化
  32.  return r / float(sum(r))
  33.  if __name__ == '__main__':
  34.  # 上面的例子
  35.  G = np.array([[0, 0, 1],
  36.           [1, 0, 0],
  37.           [1, 1, 0]])
  38.  print(pageRank(G, s=0.85))
  39.  # 结果:
  40.  [0.51203622 0.19313191 0.29483187]
复制代码
 
回复

使用道具 举报

 
*滑块验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


1关注

0粉丝

1603帖子

排行榜

关注我们:微信订阅号

官方微信

APP下载

全国服务热线:

4000-018-018

公司地址:上海市嘉定区银翔路655号B区1068室

运营中心:成都市锦江区东华正街42号广电仕百达国际大厦25楼

邮编:610066 Email:3318850993#qq.com

Copyright   ©2015-2016  比特趋势Powered by©Discuz!技术支持:迪恩网络