搜索引擎PageRank算法实现及测试数据

class digraph:
 def init_nodes（self nodes）:
  self.nodes = nodes
 
 def init_edges（self edges）:
  self.edges = edges
 
 def add_edge（self edge）:
  self.edges.append（edge）
 
 def neighbors（self node）:
  neighbors = []
  for edge in self.edges:
   if edge[0] == node:
    neighbors.append（edge[1]）
  return neighbors
 
 def incidents（self node）:
  incidents = []
  for edge in self.edges:
   if edge[1] == node:
    incidents.append（edge[0]）
  return incidents

class PRIterator:
 __doc__ = ‘‘‘计算一张图中的PR值‘‘‘
 
 def __init__（self dg damping_factor）:
  self.damping_factor = damping_factor  # 阻尼系数即α
  self.max_iterations = 100             # 最大迭代次数
  self.min_delta = 0.00001              # 确定迭代是否结束的参数即ϵ
  self.graph = dg
 
 def page_rank（self）:
  #  先将图中没有出链的节点改为对所有节点都有出链
  for node in self.graph.nodes:
   if len（self.graph.neighbors（node）） == 0:
    for node2 in self.graph.nodes:
     self.graph.add_edge（（node node2））
  
  nodes = self.graph.nodes
  graph_size = len（nodes）
  
  if graph_size == 0:
   return {}
  page_rank = dict.fromkeys（nodes 1.0 / graph_size）  # 给每个节点赋予初始的PR值
  damping_value = （1.0 - self.damping_factor） / graph_size  # 公式中的（1−α）/N部分
  
  flag = False
  for i in range（self.max_iterations）:
   change = 0
   for node in nodes:
    rank = 0
    for incident_page in self.graph.incidents（node）:  # 遍历所有“入射“的页面
     rank += self.damping_factor * （page_rank[incident_page] / len（self.graph.neighbors（incident_page）））
    rank += damping_value
    change += abs（page_rank[node] - rank）  # 绝对值
    page_rank[node] = rank
   
   print（“This is NO.%s iteration“ % （i + 1））
   
   if change < self.min_delta:
    flag = True
    break
  if flag:
   print（“finished in %s iterations!“ % node）
  else:
   print（“finished out of 100 iterations!“）
  return page_rank


if __name__ == ‘__main__‘:
 # python NewPageRankDemo.py
 
 # 输入数据和输出结果所在的文件夹位置
 directory = input（‘输入数据和输出结果所在的文件夹位置：
示例输入：C:\Users\37618\Desktop\PageRank\
‘）
 damping_factor = input（‘输入阻尼系数α（一般取0.85）：
‘）
 damping_factor = float（damping_factor）
 
 # 储存训练样本数据
 f = open（directory + ‘WikiData.txt‘）
 
 nodes = []
 edges = []
 
 for v in f:
  tmp = v.split（“	“）
  tmp[1] = tmp[1].split（“
“）[0]
  if nodes.count（tmp[0]） == 0:
   nodes.append（tmp[0]）
  if nodes.count（tmp[1]） == 0:
   nodes.append（tmp[1]）
  edges.append（（tmp[0] tmp[1]））
 
 # 输出预测结果
 import sys
 
 output = sys.stdout
 outputfile = open（directory + ‘result（‘ +str（damping_factor）+ ‘）.txt‘ ‘w‘）
 sys.stdout = outputfile
 
 dg = digraph（）
 
 dg.init_nodes（nodes）
 
 dg.init_edges（edges）
 
 pr = PRIterator（dg damping_factor）
 page_ranks = pr.page_rank（）
 
 print（“The final page rank is
“）
 for page_rank in page_ranks:
  print（page_rank ‘ ‘ page_ranks.get（page_rank））
 
 outputfile.close（）
 sys.stdout = output