pagerank算法和hits算法
1.pagerank算法
算法原理
如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)
其中PR（T）为T的PageRank值，L(T)为T的出链数
则A的PageRank值为一系列类似于T的页面重要性得分值的累加。
即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。
Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准确的表达为：
是被研究的页面，是链入页面的数量，是链出页面的数量，而N是所有页面的数量。
PageRank值是一个特殊矩阵中的特征向量。这个特征向量为：
R是如下等式的一个解：
如果网页i有指向网页j的一个链接，则
否则
＝0.使用幂法求PageRank
那我们PageRank 公式可以转换为求解
的值，
其中矩阵为$A=q*P+(1-q)ee^t/N$, P 为概率转移矩阵,$ee^t$为
//幂法计算过程如下： //设任意一个初始量x, 即设置每个网页的初始PageRank值均相等，一般为1。 R = AX; while (1 )( if ( l X - R I < ) { //如果最后两次的结果近似或者相同，返回R return R; } else { X = R; R = AX; } }
＝0.
python代码
import numpy as np import json import pymysql class pagerankIterator: __doc__ = '''计算图中pagerank ''' def __init__(self, edges,path="/",a = {"host": '127.0.0.1', "user": 'root', "passwd": '110', "db": 'jingzhen1', "port": 3306, "charset": 'utf8'}): self.edges = edges self.a =a self.nodes = [] self.path=path def pagerank(self): for edge in self.edges: if edge[0] not in self.nodes: self.nodes.append(edge[0]) if edge[1] not in self.nodes: self.nodes.append(edge[1]) print(self.nodes) N = len(self.nodes) # 将节点符号（字母），映射成阿拉伯数字，便于后面生成A矩阵/S矩阵 i = 0 node_to_num = {} for node in self.nodes: node_to_num[node] = i i += 1 for edge in self.edges: edge[0] = node_to_num[edge[0]] edge[1] = node_to_num[edge[1]] print(self.edges) # 生成初步的S矩阵 S = self.np.zeros([N, N]) for edge in self.edges: S[edge[0], edge[1]] = round(edge[2],2) print(S) # 计算比例：即一个网页对其他网页的PageRank值的贡献，即进行列的归一化处理 for i in range(N): sum_of_row=0 #= sum(S[:,j]) for edge in self.edges: if edge[0] == i: sum_of_row += round(edge[2], 2) if sum_of_row != 0: for j in range(N): S[i, j] /= sum_of_row S = self.np.transpose(S) #转置矩阵 print(S) # 计算矩阵A alpha = 0.85 A = alpha*S + (1-alpha) / N * self.np.ones([N, N]) print(A) # 生成初始的PageRank值，记录在P_n中，P_n和P_n1均用于迭代 P_n = self.np.ones((N,1)) P_n1 = self.np.zeros((N,1)) e = 100000 # 误差初始化 k = 0 # 记录迭代次数 print('loop...') while e > 0.00000001: # 开始迭代 P_n1 = self.np.dot(A, P_n) # 迭代公式 e = P_n1-P_n e = max(map(abs, e)) # 计算误差 P_n = P_n1 k += 1 # print('iteration %s:'%str(k), P_n1) P_nList=P_n.tolist() PRmax = self.np.max(P_n) node_to_pr = {} for i in range(len(P_nList)): for key, value in node_to_num.items(): if value == i: node_to_pr[key]=P_nList[i][0] break sortedlist = sorted(node_to_pr.items(), key=lambda x: x[1], reverse=True) with open(self.path + "PRresult.json", 'w+', encoding='utf-8') as target: targetdict = {} targetdict["k"] = k targetdict["sortlist"] = sortedlist self.json.dump(targetdict, target) print("迭代次数：",k) print('max:',PRmax) print("P_n",P_n) print("P_nList",P_nList) print(node_to_pr) print(sortedlist) return node_to_pr # self.sql(node_to_pr)
2.hits算法
算法原理
HITS衡量1个页面用A[i]和H[i]值表示，A代表Authority权威值，H代表Hub枢纽值。
大意可理解为我指出的网页的权威值越高，我的Hub值越大。指向我的网页的Hub值越大，我的权威值越高。二者的变量相互权衡。下面一张图直接明了:
（1）对于“扩展集base”来说，我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这两个权值都是相同的，可以都设置为1，即：
$A(i)=1,H(i)=1$
（2）每次迭代计算Hub权值和Authority权值：
网页 a (i)在此轮迭代中的Authority权值即为所有指向网页 a (i)页面的Hub权值之和：
$a (i) = Σ h (i) $
网页 a (i)的Hub分值即为所指向的页面的Authority权值之和：
$h (i) = Σ a (i)$
对a (i)、h (i)进行规范化处理:
将所有网页的中心度都除以最高中心度以将其标准化：
$a (i) =\frac{a (i)}{ |a(i)|} $
将所有网页的权威度都除以最高权威度以将其标准化：
$h (i) = \frac{h (i)} {|h(i)| }$
步骤
如下有三个网页A，B，C及其链接关系：
(1)构造邻接矩阵（Adjacent Matrix）
(2)每个节点都有一个Hub分数和Authority分数，所以有一个Hub向量h和Authority向量a，向量的每个元素都初始化为1：
(3)按如下方式交替更新h和a的值：
需要注意的是每一步都需要对得到的向量进行归一化：
我对每个向量都除以 根号下向量元素的平方和
Python代码
import json class hitIterator(): import numpy as np import json import pymysql __doc__ = '''计算图中Authority,hub ''' def __init__(self, edges,path="/",a = {"host": '127.0.0.1', "user": 'root', "passwd": '110', "db": 'jingzhen1', "port": 3306, "charset": 'utf8'}): self.edges = edges self.a =a self.nodes = [] self.path=path def hits(self): for edge in self.edges: if edge[0] not in self.nodes: self.nodes.append(edge[0]) if edge[1] not in self.nodes: self.nodes.append(edge[1]) print(self.nodes) N = len(self.nodes) # 将节点符号（字母），映射成阿拉伯数字，便于后面生成S矩阵 i = 0 node_to_num = {} for node in self.nodes: node_to_num[node] = i i += 1 for edge in self.edges: edge[0] = node_to_num[edge[0]] edge[1] = node_to_num[edge[1]] print(self.edges) # 生成初步的S矩阵 S = self.np.zeros([N, N]) for edge in self.edges: S[edge[0], edge[1]] = round(edge[2],2) print(S) # 计算比例：即一个网页对其他网页的PageRank值的贡献，即进行列的归一化处理 for i in range(N): sum_of_row=0 #= sum(S[:,j]) for edge in self.edges: if edge[0] == i: sum_of_row += round(edge[2], 2) if sum_of_row != 0: for j in range(N): S[i, j] /= sum_of_row S_trans = self.np.transpose(S) #转置矩阵 print(S) print(S_trans) H_matrix_old = self.np.ones((N, 1)) A_matrix_old = self.np.ones((N, 1)) e = 100000 # 误差初始化 k = 0 # 记录迭代次数 print('loop...') while e > 0.00000001: # 开始迭代 A_matrix_new = self.np.dot(S_trans, H_matrix_old) # 迭代公式 H_matrix_new = self.np.dot(S, A_matrix_new) # 迭代公式 a = A_matrix_new ** 2 a = self.np.sqrt(a.sum()) A_matrix_new/=a h = H_matrix_new ** 2 h =self.np.sqrt(h.sum()) H_matrix_new/=h e1 = A_matrix_new-A_matrix_old e1 = max(map(abs, e1)) # 计算误差 e2 = H_matrix_new-H_matrix_old e2 = max(map(abs, e2)) e = e1 + e2 H_matrix_old = H_matrix_new A_matrix_old = A_matrix_new k += 1 H_matrixList=H_matrix_old.tolist() Hubmax = self.np.max(H_matrixList) node_to_Hub = {} for i in range(len(H_matrixList)): for key, value in node_to_num.items(): if value == i: node_to_Hub[key]=H_matrixList[i][0] break Hub_sortedlist = sorted(node_to_Hub.items(), key=lambda x: x[1], reverse=True) print("迭代次数：",k) print('Hubmax:', Hubmax) print('Hubmaxndoes',Hub_sortedlist[:10]) A_matrixList=A_matrix_old.tolist() Autmax = self.np.max(A_matrixList) node_to_Aut = {} for i in range(len(A_matrixList)): for key, value in node_to_num.items(): if value == i: node_to_Aut[key]=A_matrixList[i][0] break Aut_sortedlist = sorted(node_to_Aut.items(), key=lambda x: x[1], reverse=True) with open(self.path + "Hitsresult.json", 'w+', encoding='utf-8') as target: targetdict={} targetdict["Aut_sortlist"] = Aut_sortedlist targetdict["Hub_sortlist"] = Hub_sortedlist targetdict["k"]=k self.json.dump(targetdict, target) print("迭代次数：",k) print('Autmax:', Autmax) print('Autmaxndoes', Aut_sortedlist[:10]) node_to_AutandHub={} for node, value in node_to_Aut.items(): node_to_AutandHub[node] = [value, node_to_Hub[node]] return node_to_AutandHub
