基于图的推荐算法
主要是要研究顶点之间的相关性
- 主要决定因素：
- 两个顶点之间的路径数
- 两个顶点之间的路径长度
- 两个顶点之间的路径经过的顶点
- 于是“相关性高”一般具有如下特征：
- 两个顶点之间有很多路径
- 连接两个顶点之间的路径都比较短
- 连接两个顶点之间的路径不会经过出度比较大的顶点
代码实现：
def PersonalRank(G, alpha, root, max_step):
rank = dict()
rank = {x:0 for x in G.keys()}
rank[root] = 1
#开始迭代
begin=time.time()
for k in range(max_step):
tmp = {x:0 for x in G.keys()}
#取节点i和它的出边尾节点集合ri
for i, ri in G.items():
#取节点i的出边的尾节点j以及边E(i,j)的权重wij, 边的权重都为1，归一化之后就上1/len(ri)
for j, wij in ri.items():
#i是j的其中一条入边的首节点，因此需要遍历图找到j的入边的首节点，
#这个遍历过程就是此处的2层for循环，一次遍历就是一次游走
tmp[j] += alpha * rank[i] / (1.0 * len(ri))
#我们每次游走都是从root节点出发，因此root节点的权重需要加上(1 - alpha)
tmp[root] += (1 - alpha)
rank = tmp
end=time.time()
print 'use time', end - begin
li = sorted(rank.items(), cmp=lambda x, y: cmp(x[1], y[1]), reverse=True)
for ele in li:
print "%s:%.3f, \t"%(ele[0], ele[1]),
print
return rank