PageRank算法原理及代码

本文内容出自帅器学习的课程内容，讲得原理清晰，概念深入，链接： PANKRANK算法视频

另有一篇知乎文章，PAGERANK讲得系统透彻，链接在此：关键词提取和摘要算法TextRank详解与实战

PAGERANK算法是一种网页排名算法，其基本思路有两条：

• 链接数量。一个网页被越多的其他网页链接，说明这个网页很重要。
• 链接质量。一个网页被一个越高权值的网页链接，也能表明这个网页越重要。

1、课程导论

经过反复研究，这个最终公式是有问题的，应该改为

2、代码实践

俗话说实践出真知，听课听懂了，结果实践的时候折腾了一天才弄明白，因为计算pagerank目前已经有成熟的算法，我根据networkx和pygraph现成的算法去验证自己写的是否有问题。

问题，目前有4个网页A B C D

入链和出链关系如下图，那么这4个网页的pagerank是多少呢？

2.1 自写算法

import numpy as np p = 0.85 #引入浏览当前网页的概率为p,假设p=0.8 a = np.array([[1,0,0,0], [0,0,0,1], [0,0,0,1], [0,1,0,0]],dtype = float) #dtype指定为float length=a.shape[1] #网页数量 #构造转移矩阵 b = np.transpose(a) #b为a的转置矩阵 m = np.zeros((a.shape),dtype = float) for i in range(a.shape[0]): for j in range(a.shape[1]): #如果一个节点没有任何出链，Dead Ends if b[j].sum()==0: b[j]=b[j]+np.array([1/length]*length) m[i][j] = a[i][j] / (b[j].sum()) #完成初始化分配 #pr值得初始化 v = np.zeros((m.shape[0],1),dtype = float) #构造一个存放pr值得矩阵 for i in range(m.shape[0]): v[i] = float(1)/m.shape[0] count=0 ee=np.array([[1/length]*length]).reshape(length,-1) # 循环100次计算pageRank值 for i in range(100): # 解决spider traps问题，spider traps会导致网站权重向一个节点偏移，将转移矩阵加上打开其他网页的概率1-p v = p*np.dot(m,v) + (1-p)*ee count+=1 print("第{}次迭代".format(count)) #pageRank值 print(v)

2.2 networkx算法

import networkx as nx import matplotlib.pyplot as plt # 创建有向图 G = nx.DiGraph() # 有向图之间边的关系 edges = [("A", "A"), ("B", "D"), ("D", "B"), ("D", "C")] for edge in edges: G.add_edge(edge[0], edge[1]) nx.draw(G,with_labels=True) plt.show() pagerank_list = nx.pagerank(G, alpha=0.85) print("pagerank值是：\n", pagerank_list)

 2.3 pygraph算法

from pygraph.classes.digraph import digraph dg = digraph() dg.add_nodes(["A", "B", "C", "D"]) dg.add_edge(("A", "A")) dg.add_edge(("B", "D")) dg.add_edge(("D", "B")) dg.add_edge(("D", "C")) damping_factor = 0.85 # 阻尼系数,即α max_iterations = 100 # 最大迭代次数 min_delta = 0.00001 # 确定迭代是否结束的参数,即ϵ graph = dg for node in graph.nodes(): if len(graph.neighbors(node)) == 0: for node2 in graph.nodes(): print("node:",node,"node2:",node2) digraph.add_edge(graph, (node, node2)) print(graph) print("-"*5) print("="*30) nodes = graph.nodes() graph_size = len(nodes) page_rank = dict.fromkeys(nodes, 1.0 / graph_size) # 给每个节点赋予初始的PR值 damping_value = (1.0 - damping_factor) / graph_size # 公式中的(1−α)/N部分 flag = False for i in range(max_iterations): change = 0 for node in nodes: rank = 0 for incident_page in graph.incidents(node): # 遍历所有“入射”的页面 rank += damping_factor * (page_rank[incident_page] / len(graph.neighbors(incident_page))) rank += damping_value change += abs(page_rank[node] - rank) # 绝对值 page_rank[node] = rank if change < min_delta: flag = True break if flag: print("finished in %s iterations!" % node) else: print("finished out of 100 iterations!") print(page_rank) 

3、对比

自写算法结果： [[0.] [0.] [0.] [0.]] nx算法结果： {'A': 0.093023, 'B': 0., 'C': 0., 'D': 0.} pygraph结果： {'A': 0., 'B': 0.24163, 'C': 0.24163, 'D': 0.}

自此，我们的理论和实践初级入门就可以了！

4、应用

pagerank既可以用在网页质量的排名，也可以应用到网状节点类的各种问题，比如社交网络、各城市资本流向，以及改进后的TextRank,本文应用从希拉里用私人邮箱处理公务成为丑闻 事件为切入点，理解利用pagerank计算节点度量性。

# -*- coding: utf-8 -*- # 用 PageRank 挖掘希拉里邮件中的重要任务关系 import pandas as pd import networkx as nx import numpy as np from collections import defaultdict import matplotlib.pyplot as plt import os os.chdir("D:/pagerank/data/") # 数据加载 emails = pd.read_csv("Emails.csv") # 读取别名文件 file = pd.read_csv("Aliases.csv") aliases = {} for index, row in file.iterrows(): aliases[row['Alias']] = row['PersonId'] # 读取人名文件 file = pd.read_csv("Persons.csv") persons = {} for index, row in file.iterrows(): persons[row['Id']] = row['Name'] # 针对别名进行转换 def unify_name(name): # 姓名统一小写 name = str(name).lower() # 去掉, 和 @后面的内容 name = name.replace(",","").split("@")[0] # 别名转换 if name in aliases.keys(): return persons[aliases[name]] return name # 画网络图 def show_graph(graph, layout='spring_layout'): # 使用 Spring Layout 布局，类似中心放射状 if layout == 'circular_layout': positions=nx.circular_layout(graph) else: positions=nx.spring_layout(graph) # 设置网络图中的节点大小，大小与 pagerank 值相关，因为 pagerank 值很小所以需要 *20000 nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=True)] # 设置网络图中的边长度 edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)] # 绘制节点 nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4) # 绘制边 nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2) # 绘制节点的 label nx.draw_networkx_labels(graph, positions, font_size=10) # 输出希拉里邮件中的所有人物关系图 plt.show() # 将寄件人和收件人的姓名进行规范化 emails.MetadataFrom = emails.MetadataFrom.apply(unify_name) emails.MetadataTo = emails.MetadataTo.apply(unify_name) # 设置遍的权重等于发邮件的次数 edges_weights_temp = defaultdict(list) #defaultdict当字典里的Key不存在时，返回默认值[] for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText): temp = (row[0], row[1]) if temp not in edges_weights_temp: edges_weights_temp[temp] = 1 else: edges_weights_temp[temp] = edges_weights_temp[temp] + 1 # 转化格式 (from, to), weight => from, to, weight edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()] # 创建一个有向图 graph = nx.DiGraph() # 设置有向图中的路径及权重 (from, to, weight) add_weighted_edges_fromu、v、w 分别代表起点、终点和权重。 graph.add_weighted_edges_from(edges_weights) # 计算每个节点（人）的 PR 值，并作为节点的 pagerank 属性 pagerank = nx.pagerank(graph) # 将 pagerank 数值作为节点的属性 nx.set_node_attributes(graph, name = 'pagerank', values=pagerank) # 画网络图 show_graph(graph) # 将完整的图谱进行精简 # 设置 PR 值的阈值，筛选大于阈值的重要核心节点 pagerank_threshold = 0.005 # 复制一份计算好的网络图 small_graph = graph.copy() # 剪掉 PR 值小于 pagerank_threshold 的节点 for n, p_rank in graph.nodes(data=True): if p_rank['pagerank'] < pagerank_threshold: small_graph.remove_node(n) # 画网络图,采用circular_layout布局让筛选出来的点组成一个圆 show_graph(small_graph, 'circular_layout')

参考链接

PageRank算法与TextRank算法详解：点此链接

希拉里原始数据：点此链接

TextRank算法的基本原理及textrank4zh使用实例：点此链接