之前写的newman fast算法有错误,更正过来了并上传一下代码,希望能有帮助,如果有错误也请指出。 算法原理: 先将每个节点看作一个社区,然后选择模块度增值最大的进行合并,直到所有社团变成一个社团为止。
所需包安装
pip install networkx==1.11
# networkx目前版本2.0,遍历邻居函数G.neighbors(node)返回不再是一个list,读者可自行调整
import networkx as nx
# newman快速算法
# 合并社团函数
def cluAssemble(self, other, currentCluList):
currentCluList.remove(self)
currentCluList.remove(other)
for node in self:
if node not in other:
other.append(node)
currentCluList.append(other)
cluAfterAssemble = currentCluList
return cluAfterAssemble
# 判断两个社团之间是否有边相连
def cluHasEdge(clu1, clu2, graph):
for p1 in clu1:
for p2 in clu2:
if graph.has_edge(p1, p2):
return True
return False
# 从path中读取图
def load_graph(path):
G = nx.Graph()
with open(path) as text:
for line in text:
vertices = line.strip().split(" ")
sourcePoint = int(vertices[0])
targetPoint = int(vertices[1])
G.add_edge(sourcePoint, targetPoint)
return G
# 计时器函数,该函数是一个装饰器decorator
def fn_timer(function):
@wraps(function)
def function_timer(*args, **kwargs):
t0 = time.time()
result = function(*args, **kwargs)
t1 = time.time()
print("time:%s s" % (str(t1 - t0)))
return result
return function_timer
# 写入所属社团标号
def writeClu(G, currentCluList):
cluID = 0
for item in currentCluList:
cluID += 1
for item2 in item:
G.node[item2]['groupID'] = str(cluID)
# print(G.nodes(data=True))
# Q = 社团内部边数/网络总边数 - (社团内所有点度数之和/2倍总边数)平方
def cal_Q(partition, G):
m = len(G.edges())
a = 0.0
e = 0.0
# 计算eii
for community in partition:
eii = 0.0
for i in community:
for j in community:
if G.has_edge(i, j):
eii += 1
e += eii / (2 * m)
# 计算aij的平方
for community in partition:
aij = 0.0
for node in community:
aij += len(G.neighbors(node))
a += (aij / (2 * m)) ** 2
q = e - a
return q
# 主类
class newmanFast:
def __init__(self, graph):
self.G = graph
self.nodeList = self.G.nodes()
self.cluList = []
for i in self.nodeList:
self.cluList.append([i])
self.finalClu = []
@fn_timer
def execute(self):
iterTime = 1
# 先将每个节点看作一个社区,然后选择模块度增值最大的进行合并,直到所有社团变成一个社团为止
print(self.cluList)
maxQ = -float('Inf')
# 只要社团列表长度不为1
while len(self.cluList) is not 1:
Q = -float('Inf')
for cluFrom in self.cluList:
thisClu = self.cluList.copy()
thisClu.remove(cluFrom)
for cluTo in thisClu:
if cluHasEdge(cluFrom, cluTo, self.G):
partition = cluAssemble(cluFrom.copy(), cluTo.copy(), self.cluList.copy())
thisQ = cal_Q(partition, self.G)
# print("社团" + str(cluTo) + "q值" + str(thisQ))
# 记录该轮最大Q和目标社团
if thisQ >= Q:
Q = thisQ
finalCluFrom = cluFrom
finalCluTo = cluTo
cluAssemble(finalCluFrom.copy(), finalCluTo.copy(), self.cluList)
print("该轮结束的划分结果:" + str(self.cluList))
print("该轮结束时的模块度Q:" + str(Q))
print("################第" + str(iterTime) + "轮结束##################")
file_object = open('resver2/%sres.txt' % str(graphName), 'a')
file_object.write(str(iterTime) + '|Q:' + str(Q) + '|Result:' + str(self.cluList) + '\n')
file_object.close()
iterTime += 1
if Q > maxQ:
maxQ = Q
iterRound = iterTime - 1
self.finalClu = self.cluList.copy()
writeClu(self.G, self.cluList)
print("最大Q值出现在:第" + str(iterRound) + "轮。最大Q值为:" + str(maxQ))
for clu in self.finalClu:
print(sorted(clu))
if __name__ == "__main__":
graphNameClu = ['club', 'dolphin', 'football', 'power', 'sciencenet', 'test', 'test2', 'test3', 'dept3', 'facebook']
graphName = input("请输入数据集名('club', 'dolphin', 'football', 'power', 'sciencenet', 'test', 'test2', 'test3', "
"'dept3', 'facebook'):")
if graphName not in graphNameClu:
print("error")
else:
G = load_graph('your/path/to/dataset/%s.txt' % str(graphName))
this = newmanFast(G)
this.execute()
nx.write_gml(G, '%sres.gml' % str(graphName))