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

搜索引擎PageRank算法实现及测试数据，测试输出，可执行文件。搜索引擎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（‘输入数据和输出结果所在的文件夹位置：\n示例输入：C:\\Users\\37618\\Desktop\\PageRank\\\n‘）
 damping_factor = input（‘输入阻尼系数α（一般取0.85）：\n‘）
 damping_factor = float（damping_factor）
 
 # 储存训练样本数据
 f = open（directory + ‘WikiData.txt‘）
 
 nodes = []
 edges = []
 
 for v in f:
  tmp = v.split（“\t“）
  tmp[1] = tmp[1].split（“\n“）[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\n“）
 for page_rank in page_ranks:
  print（page_rank ‘ ‘ page_ranks.get（page_rank））
 
 outputfile.close（）
 sys.stdout = output

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     739204  2018-06-09 11:50  PageRankDemo\build\NewPageRank\base_library.zip

     文件       1034  2018-06-09 11:50  PageRankDemo\build\NewPageRank\NewPageRank.exe.manifest

     文件      23734  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-Analysis.toc

     文件       8614  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-EXE.toc

     文件    5568510  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-PKG.pkg

     文件       7534  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-PKG.toc

     文件    1151061  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-PYZ.pyz

     文件      17360  2018-06-09 11:50  PageRankDemo\build\NewPageRank\out00-PYZ.toc

     文件       1872  2018-06-09 11:50  PageRankDemo\build\NewPageRank\warnNewPageRank.txt

     文件     290963  2018-06-09 11:50  PageRankDemo\build\NewPageRank\xref-NewPageRank.html

     文件    5812222  2018-06-09 11:50  PageRankDemo\dist\NewPageRank.exe

     文件       3197  2018-06-09 11:49  PageRankDemo\NewPageRank.py

     文件        772  2018-06-09 11:50  PageRankDemo\NewPageRank.spec

     文件         89  2018-06-09 11:56  PageRankDemo\Readme.txt

     文件     215432  2018-06-05 16:43  PageRankDemo\results\result（0.85）.txt

     文件     215601  2018-06-05 18:06  PageRankDemo\results\result（0.9）.txt

     文件     216650  2018-06-05 19:10  PageRankDemo\results\result（0.95）.txt

     文件    1094778  2017-12-18 12:35  PageRankDemo\WikiData.txt

     文件       3056  2018-06-09 11:50  PageRankDemo\__pycache__\NewPageRank.cpython-36.pyc

     目录          0  2018-06-09 14:08  PageRankDemo\build\NewPageRank

     目录          0  2018-06-09 14:08  PageRankDemo\build

     目录          0  2018-06-09 14:08  PageRankDemo\dist

     目录          0  2018-06-09 14:08  PageRankDemo\results

     目录          0  2018-06-09 14:08  PageRankDemo\__pycache__

     目录          0  2018-06-09 14:08  PageRankDemo

----------- ---------  ---------- -----  ----

             15371683                    25