本文主要介绍社团检测中节点排序LeaderRank算法。
基本思想
L
e
a
d
e
r
R
a
n
k
L
e
a
d
e
r
R
a
n
k
算法通过在网络中增加一个节点
g
(
G
r
o
u
n
d
n
o
d
e
)
g
(
G
r
o
u
n
d
n
o
d
e
)
，将其与网络中的所有节点相连接从而得到一个强连接的
N
+
1
N
+
1
个节点的新网络。算法首先给节点
g
g
之外的
个节点分配1单位的
L
R
L
R
值，将这1单位的
L
R
L
R
值分配给其直接相连的邻居节点，这一过程根据下面公式不断进行迭代，直到达到稳定状态：
s
i
(
t
+
1
)
=
∑
j
=
0
N
a
i
j
k
j
s
j
(
t
)
s
i
(
t
+
1
)
=
∑
j
=
0
N
a
i
j
k
j
s
j
(
t
)
其中，节点i与j直接相连则
a
i
j
=
1
a
i
j
=
1
，否则为0；
k
j
k
j
代表节点j的度数。
a
i
j
k
j
a
i
j
k
j
代表节点
i
i
随机游走到
的概率。初始状态下除
g
g
外的所有节点的
，而
s
g
(
0
)
=
0
s
g
(
0
)
=
0
。最后将节点
g
g
的
值平均分给其它
N
N
个节点：
其中，
s
g
(
t
c
)
s
g
(
t
c
)
是稳定状态下节点
g
g
的
值，
t
c
t
c
表示收敛次数。
参考论文 :
Leaders in Social Networks, the Delicious Case
Python代码实现
# -*- coding: UTF-8 -*-
"""
Created on 18-3-5
@summary: LeaderRank 节点排序算法
@author: dreamhomes
"""
import get_graph
def leaderrank(graph):
"""
节点排序
:param graph:复杂网络图Graph
:return: 返回节点排序值
"""
# 节点个数
num_nodes = graph.number_of_nodes()
# 节点
nodes = graph.nodes()
# 在网络中增加节点g并且与所有节点进行连接
graph.add_node(0)
for node in nodes:
graph.add_edge(0, node)
# LR值初始化
LR = dict.fromkeys(nodes, 1.0)
LR[0] = 0.0
# 迭代从而满足停止条件
while True:
tempLR = {}
for node1 in graph.nodes():
s = 0.0
for node2 in graph.nodes():
if node2 in graph.neighbors(node1):
s += 1.0 / graph.degree([node2])[node2] * LR[node2]
tempLR[node1] = s
# 终止条件:LR值不在变化
error = 0.0
for n in tempLR.keys():
error += abs(tempLR[n] - LR[n])
if error == 0.0:
break
LR = tempLR
# 节点g的LR值平均分给其它的N个节点并且删除节点
avg = LR[0] / num_nodes
LR.pop(0)
for k in LR.keys():
LR[k] += avg
return LR
if __name__ == "__main__":
path = "/home/dreamhome/network-datasets/karate/karate.paj"
graph = get_graph.read_graph_from_file(path)
print sorted(leaderrank(graph).items(), key=lambda item: item[1])