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?????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