1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| class Vertex: def __init__(self): self.in_degree = 0 self.out_degree = 0 self.pagerank = 0.0
class Edge: def __init__(self, start, end): self.start_id = start self.end_id = end
def addVertex(vertex_name, vtx_map): ''' return the id of vertex_name if exists in vtx_map, return directly if not exists, add it, and then return
vertex_name: string, the url of a web page vtx_map: dict, the map from url to id ''' res_id = 0 if vertex_name in vtx_map: return vtx_map[vertex_name] else: res_id = len(vtx_map) vtx_map[vertex_name] = res_id return res_id
def readTable(fname, vtx_map, edge_list): ''' read fname line by line, update the vtx_map and edge_list
fname: string, the file name of the table vtx_map: dict, the map from url to id edge_list: list, the list of all edges ''' with open(fname, 'r') as fin: for line in fin.readlines(): tmp = line.strip().split('\t') assert(len(tmp) == 2) start = addVertex(tmp[0], vtx_map) end = addVertex(tmp[1], vtx_map) edge_list.append(Edge(start, end)) return None
def initialize(vtx_map, edge_list, vtx_list): ''' initialize the data structures
vtx_map: dict, the map from url to id edge_list: list, the list of all edges vtx_list: list, the list of all vertices ''' vtx_num = len(vtx_map) assert(vtx_num > 0) vtx_list = [Vertex() for _ in range(vtx_num)] for i in range(vtx_num): vtx_list[i].pagerank = 1.0 / vtx_num for edge in edge_list: vtx_list[edge.start_id].out_degree += 1 vtx_list[edge.end_id].in_degree += 1 return None
def calcPagerank(alpha, num_iter, vtx_map, edge_list): ''' calc PageRank for all vertices return: vtx_list, list, the list of all vertices
alpha: float, damping factor num_iter: int, the upper limitation of calculation vtx_map: dict, the map from url to id edge_list: list, the list of all edges ''' vtx_list, pr_list = list(), list() initialize(vtx_map, edge_list, vtx_list) vtx_num = len(vtx_list) assert(vtx_num > 0) alpha = float(alpha) for _ in range(num_iter): pr_list = [alpha / vtx_num for _ in range(vtx_num)] for edge in edge_list: pr_list.append((1 - alpha) * vtx_list[edge.start_id].pagerank / \ vtx_list[edge.start_id].out_degree) revise = sum(map(lambda vtx: (1 - alpha) * vtx.pagerank / vtx_num, \ filter(lambda vtx:(vtx.out_degree == 0), vtx_list))) for i in range(vtx_num): vtx_list[i].pagerank = pr_list[i] + revise return vtx_list
def doCalcPageRank(fname = 'wt2g_inlinks.source', alpha = 0.15, num_iter = 30): vtx_map = dict() edge_list = list() readTable(fname, vtx_map, edge_list) return calcPagerank(alpha, num_iter, vtx_map, edge_list)
if __name__ == '__main__': print doCalcPageRank()
|