admin管理员组文章数量:1626223
原理介绍
Louvain算法是一种贪婪优化方法,其目的是将网络划分为密集连接的节点群,优化网络的模块化。模块化被定义为“位于社区内的边数减去随机放置边的等价网络中的期望边数”。Louvain算法由两个步骤组成。它首先通过寻找小型社区来局部优化模块化。然后,它聚合每个小社区中的节点,并使用这些聚合的节点构建一个新的网络。它在这两个步骤上迭代,直到模块性最大化。鲁万方法在模块性和计算时间上都优于其他所有的社区检测方法。模块性得分高表明社区内部存在紧密的联系,但社区之间的联系较稀疏,表明找到了最优解。当获得高模块性分数时,社区具有显著的实际意义。
论文来源
Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.
Python 3代码实现
备注:这是我个人使用的版本,大家可以根据自己的需求调用不同模块或改写。不喜勿喷~
'''
Implements the Louvain method.
Input: a weighted undirected graph
Ouput: a (partition, modularity) pair where modularity is maximum
'''
class PyLouvain:
'''
Builds a graph from _path.
_path: a path to a file containing "node_from node_to" edges (one per line)
'''
@classmethod
def from_file(cls, path):
f = open(path, 'r')
lines = f.readlines()
f.close()
nodes = {}
edges = []
for line in lines:
n = line.split()
if not n:
break
nodes[n[0]] = 1
nodes[n[1]] = 1
w = 1
if len(n) == 3:
w = int(n[2])
edges.append(((n[0], n[1]), w))
# rebuild graph with successive identifiers
nodes_, edges_ = in_order(nodes, edges)
print("%d nodes, %d edges" % (len(nodes_), len(edges_)))
return cls(nodes_, edges_)
'''
Builds a graph from _path.
_path: a path to a file following the Graph Modeling Language specification
'''
@classmethod
def from_gml_file(cls, path):
f = open(path, 'r')
lines = f.readlines()
f.close()
nodes = {}
edges = []
current_edge = (-1, -1, 1)
in_edge = 0
for line in lines:
words = line.split()
if not words:
break
if words[0] == 'id':
nodes[int(words[1])] = 1
elif words[0] == 'source':
in_edge = 1
current_edge = (int(words[1]), current_edge[1], current_edge[2])
elif words[0] ==
版权声明:本文标题:Louvain community detection method(社区社区检测算法原理介绍+python版代码实现) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728943799a1181009.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论