几个常见的社区推荐算法

PageRank算法

PageRank算法预先给每个网页一个PR值(PR值指代PageRank值),PR值在物理意义上为一个网页被访问的概率,所以一般是1/N,其中N为网页总数。

另外,所有网页的PR值的和一般为1。(如果实在不为1也不是不行,最后算出来的不同网页之间PR值的大小关系仍然是正确的,只是这个数值不能直接地反映概率罢了。)

接着,运用下面的算法不断迭代计算,直至达到平稳分布为止。

普通情况

互联网中的众多网页可以看成一个有向图,箭头的指向即为链接的链入,根据上图,我们得到A的PR值为:PR(A)=PR(B)/2+PR©/1。

没有出链

网络中不乏一些没有出链的网页,如上图,其中,网页C没有出链,也就是说网页C对其他网页没有PR值的贡献,我们不喜欢这种“自私”的网页(其实是为了满足 Markov 链的收敛性),于是设定其对所有网页(包括它自己)都有出链,则此图中A的PR值表示为:PR(A)=PR(B)/2+PR©/4。

出链循环圈

网络中还存在这样的网页:只对自己有出链,或者几个网页的出链形成一个循环圈。那么在不断迭代的过程中,这一个或几个网页的PR值将只增不减,这显然是不合理的。

那么如何解决这个问题呢?我们假设某人正在浏览网页C,显然他不会一直停留在网页C,他可能会随机地输入一个网址从而去往另一个网页,并且其跳转到每个网页的概率是一样的。于是此图中A的PR值表示为:PR(A)=∂(PR(B)/2)+(1-∂)/4。

综上,一般情况下,一个网页的PR值计算公式如下:

其中,Mpi是所有对pi网页有出链的网页集合,L(pj)是网页pj的出链数目,N是网页总数,α一般取0.85。

根据上面的公式,我们就可以计算出每个网页的PR值,在不断迭代并趋于平稳的时候,即为最终结果。

HITS算法

算法简介:

首先把那些根据关键相关返回网页作为根集合S,再由S集合网页节点的链入和链出网页节点派生出结合C,结合C包括S,链入和链出节点集合。

C中的每个节点分配一对权重<h(s),a(s)>, 节点h(s)权重由节点链出的节点的a(s)决定,a(s)由节点的链入节点的h(s)决定。

算法过程:

网页的a权重向量:

关于HITS算法收敛性,可以从如下变换形式来得出:

当算法收敛时候,a其实就是对应矩阵A那个最大特征值对应的特征向量的归一化形式,同样,h也是H矩阵那个最大特征值对应的特征向量的归一化形式。

算法实现:

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
class HITSIterator:
__doc__ = '''计算一张图中的hub,authority值'''

def __init__(self, dg):
self.max_iterations = 100 # 最大迭代次数
self.min_delta = 0.0001 # 确定迭代是否结束的参数
self.graph = dg

self.hub = {}
self.authority = {}
for node in self.graph.nodes():
self.hub[node] = 1
self.authority[node] = 1

def hits(self):
"""
计算每个页面的hub,authority值
:return:
"""
if not self.graph:
return

flag = False
for i in range(self.max_iterations):
change = 0.0 # 记录每轮的变化值
norm = 0 # 标准化系数
tmp = {}
# 计算每个页面的authority值
tmp = self.authority.copy()
for node in self.graph.nodes():
self.authority[node] = 0
for incident_page in self.graph.incidents(node): # 遍历所有“入射”的页面
self.authority[node] += self.hub[incident_page]
norm += pow(self.authority[node], 2)
# 标准化
norm = sqrt(norm)
for node in self.graph.nodes():
self.authority[node] /= norm
change += abs(tmp[node] - self.authority[node])

# 计算每个页面的hub值
norm = 0
tmp = self.hub.copy()
for node in self.graph.nodes():
self.hub[node] = 0
for neighbor_page in self.graph.neighbors(node): # 遍历所有“出射”的页面
self.hub[node] += self.authority[neighbor_page]
norm += pow(self.hub[node], 2)
# 标准化
norm = sqrt(norm)
for node in self.graph.nodes():
self.hub[node] /= norm
change += abs(tmp[node] - self.hub[node])

print("This is NO.%s iteration" % (i + 1))
print("authority", self.authority)
print("hub", self.hub)

if change < self.min_delta:
flag = True
break
if flag:
print("finished in %s iterations!" % (i + 1))
else:
print("finished out of 100 iterations!")

print("The best authority page: ", max(self.authority.items(), key=lambda x: x[1]))
print("The best hub page: ", max(self.hub.items(), key=lambda x: x[1]))


if __name__ == '__main__':
dg = digraph()

dg.add_nodes(["A", "B", "C", "D", "E"])

dg.add_edge(("A", "C"))
dg.add_edge(("A", "D"))
dg.add_edge(("B", "D"))
dg.add_edge(("C", "E"))
dg.add_edge(("D", "E"))
dg.add_edge(("B", "E"))
dg.add_edge(("E", "A"))

hits = HITSIterator(dg)
hits.hits()

SALSA算法

SALSA算法和HITS算法初始部分一样,构建相同的集合集C和彼此的链接关系。

SALSA一种随机游走过程,但是不同经典的随机游走。它涉及到把一个网页节点看成2种不同类型节点:hub和authority,随机游走对应着这样两种不用类型的Markov链:hub链和authority链,状态转移为网页前向和后向。

首先是把构建一个无向图,原图节点分为2类,然后构建边。

这样从某个节点出发,进行两个方向的随机游走。h和a方向的状态转移矩阵:

对于以上的形式可以通过如下的矩阵相乘的方式展现:

有了H和A矩阵,就可以知道节点集合最终的h和a向量:和HITS一样,h和a对应H和A的最大特征值对应的归一化特征向量。其实,计算h和a可以参照HITS,进行迭代求解。



本文链接: http://home.meng.uno/articles/82a6b55c/ 欢迎转载!

© 2018.02.08 - 2020.10.14 Mengmeng Kuang  保留所有权利!

UV : | PV :

:D 获取中...

Creative Commons License