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
| import random
class pageRank: def __init__(self, nodes, matrix): self.nodes = nodes self.matrix = matrix
def matrix_multi(self, A, B): result = [[0] * len(B[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): result[i][j] += A[i][k] * B[k][j] return result
def matrix_multiN(self, n, A): result = [[1] * len(A[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(A[0])): result[i][j] = n * A[i][j] return result def matrix_add(self, A, B): if len(A[0]) != len(B[0]) and len(A) != len(B): return result = [[0] * len(A[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(A[0])): result[i][j] = A[i][j] + B[i][j] return result
def tran_and_convert(self, A): result = [[0] * len(A[0]) for i in range(len(A))] result_convert = [[0] * len(A[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(A[0])): result[i][j] = A[i][j] * 1.0 / sum(A[i]) for i in range(len(result)): for j in range(len(result[0])): result_convert[i][j] = result[j][i] return result_convert
def main(self): N = len(self.nodes) d = 0.85 delt = 0.00001
e = [] for i in range(N): e.append(1) New_P = [] for i in range(N): New_P.append([random.random()]) r = [[(1 - d) * i * 1 / N] for i in e]
A = self.tran_and_convert(self.matrix) norm = 100 while norm > delt: P = New_P New_P = self.matrix_add(r, self.matrix_multiN(d, self.matrix_multi(A, P))) norm = 0 for i in range(N): norm += abs(New_P[i][0] - P[i][0]) print(New_P)
if __name__ == '__main__': nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
matrix = [[0, 10, 0, 0, 0, 11, 0, 0, 0], [10, 0, 18, 0, 0, 0, 16, 0, 12], [0, 18, 0, 22, 0, 0, 0, 0, 8], [0, 0, 22, 0, 20, 0, 0, 16, 21], [0, 0, 0, 20, 0, 26, 7, 19, 0], [11, 0, 0, 0, 26, 0, 17, 0, 0], [0, 16, 0, 0, 7, 17, 0, 19, 0], [0, 0, 0, 16, 19, 0, 19, 0, 0], [0, 12, 8, 21, 0, 0, 0, 0, 0]]
p = pageRank(nodes, matrix) p.main()
|