Louvain是什么？
Louvain是一个用于社区发现的传统算法。这个算法出现于2008年，那么什么是社区发现呢？举个例子：假设我们有一个图，在这个图中的节点是某个镇的所有的人，图中的每一条边代表的是两个人之间的说话的数量。（现实生活中这个可能难以统计）而社区发现就是在这个图中我们需要确定哪些人之间是一个团体，这个所谓的团体可能是同一个小学，也可能是同一个家庭或者是同一个小区等等。论文的原文全称是：Fast unfolding of communities in large networks 作者：Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte and Etienne Lefebvre。
算法思路
社区划分的合理性
公式如下：
m：如果是无向图，图中所有边的权值和。如果是有向图就是图中所有边的权值和的一半。论文中原本的写法是：
表面上看是图中所有边的一半。但是对于无向图而言需要把每一条边当作两条有向边来看。
Aij:代表的是节点i和节点j之间的边的权值。
ki:是所有指向节点i的边的权值和。注意：就是这一个定义当我们在处理自环的时候就需要注意一个细节。假设有一个节点的图案如下图所示：
其中权值为4的边是一个自环需要当作两条边来看，就上图的i点而言其中的ki的值是28。
δ(ci,cj)：就是判断i节点和j节点是否是同一个社区。如果是那么值就是1否则就是0。
算法流程
其算法流程一共有两个大步骤，不断的迭代往复：
- 我们先要把每一个单一的节点都看作是一个单独的社区。对于每一个单一的节点，先要把它从它所在的社区中取出来。然后，再尝试依次加入到它相邻的社区中计算其收益ΔQ。ΔQ的计算方法之后在详细说，本文给出了三种不同的计算方法。）如果，最大的ΔQ小于0则将它放回到原先的社区中，否则就加入到收益最大的那一个社区中。对所有的节点都不断的循环反复的进行这一操作。直到所有节点的所处社区都不再发生变化。
- 通过第一步我们已经对图有了一个新的社区划分。于是在这一步中我们会对每一个社区都要把其中的对应的那些节点都缩成一个超节点，而这个超节点就代表了这一个社区中的若干个结点。而边的处理方式与咱们的逻辑十分相符。如果一条边连接的是同一个社区就把它变成对应超节点的一条自环边，如果一条边连接的是两个不同的社区就让这条边连接两个对应的超节点。然后计算一个新的全局Q值。如果这个Q值与之前的Q值相同那么就结束整个算法。（如果是第一次迭代那就不用考虑结束的事了）
表述更清晰的说法：
- 初始时将每个顶点当作一个社区，社区个数与顶点个数相同。
- 依次将每个顶点与之相邻顶点合并在一起，计算它们的模块度增益是否大于0，如果大于0，就将该结点放入该相邻结点所在社区。
- 迭代第二步，直至算法稳定，即所有顶点所属社区不再变化。
- 将各个社区所有节点压缩成为一个结点，社区内点的权重转化为新结点环的权重，社区间权重转化为新结点边的权重。
- 重复步骤1-3，直至算法稳定。
ΔQ的计算方式
在这一部分中我会一共会放两种不同的计算方式，这两种方式都是基于一个大前提——我们需要尝试将一个节点加入到社区C中。其中第一种是论文中给出的，第二种是其它的一些代码中使用的版，（据说论文的初稿用的也是这个版本）
第一种
∑in：社区C的内部的所有边的权值和，注意：如果是无向图则需要每一条边看作是两条有向边，所以，是所有边的权值和的两倍。
ki,in：所有从节点i指向区域C的边的权值和。
m：如果是无向图，图中所有边的权值和。如果是有向图就是图中所有边的权值和的一半。
∑tot：所有指向区域C中的节点的边的权值和。
ki：指向节点i的所有边的权值和。
在接下了我们就在这个公式的基础上进行划简：
第二种
这个公式对应的上一个公式就是在ki,in前多了一个系数2，据说，作者刚发布的第一个版本的论文中用的就是这个后来修改了系数。同时用用使用这个公式作为ΔQ的计算分割效果要更好一点。同时在karate的数据集中使用这个方法的效果确实比上一个公式的效果要更好一点。
代码实现
'''
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): #从txt中读取一个net
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 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): #从gml中读取一个net
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] == 'target' and in_edge:
current_edge = (current_edge[0], int(words[1]), current_edge[2])
elif words[0] == 'value' and in_edge:
current_edge = (current_edge[0], current_edge[1], int(words[1]))
elif words[0] == ']' and in_edge:
edges.append(((current_edge[0], current_edge[1]), 1))
current_edge = (-1, -1, 1)
in_edge = 0
nodes, edges = in_order(nodes, edges)
print("%d nodes, %d edges" % (len(nodes), len(edges)))
return nodes, edges #此处作了一点修改
'''
Initializes the method.
_nodes: a list of ints
_edges: a list of ((int, int), weight) pairs
'''
def __init__(self, nodes, edges):
self.nodes = nodes
self.edges = edges
# precompute m (sum of the weights of all links in network)
# k_i (sum of the weights of the links incident to node i)
self.m = 0
self.k_i = [0 for n in nodes]
self.edges_of_node = {}
self.w = [0 for n in nodes]
self.orginer_network = []
self.orginer_k_i = []
for e in edges:
self.m += e[1]
self.k_i[e[0][0]] += e[1]
self.k_i[e[0][1]] += e[1] # there's no self-loop initially
# save edges by node
if e[0][0] not in self.edges_of_node:
self.edges_of_node[e[0][0]] = [e]
else:
self.edges_of_node[e[0][0]].append(e)
if e[0][1] not in self.edges_of_node:
self.edges_of_node[e[0][1]] = [e]
elif e[0][0] != e[0][1]:
self.edges_of_node[e[0][1]].append(e)
# access community of a node in O(1) time
self.communities = [n for n in nodes]
self.actual_partition = []
self.orginer_k_i = []
for k in self.k_i:
self.orginer_k_i.append(k)
'''
Applies the Louvain method.
'''
def findRoot(self,node):
for i,community in enumerate(self.actual_partition):
if(node in community):
return i
def my_compute_modularity(self):
sum_Q = 0
for edge in self.orginer_network[1]:
u,v = edge[0]
w = edge[1]
if(self.findRoot(u) == self.findRoot(v)):
sum_Q = (w - (self.orginer_k_i[u]*self.orginer_k_i[v])/(2*self.m))/(2*self.m)
return sum_Q
def apply_method(self):
network = (self.nodes, self.edges)
self.orginer_network = network
best_partition = [[node] for node in network[0]]
best_q = -1
i = 1
while 1:
# print("pass #%d" % i)
i += 1
partition = self.first_phase(network)
#q = self.compute_modularity(partition)
q = self.my_compute_modularity()
partition = [c for c in partition if c]
# print("%s (%.8f)" % (partition, q))
# clustering initial nodes with partition
if self.actual_partition:
actual = []
for p in partition:
part = []
for n in p:
part.extend(self.actual_partition[n])
actual.append(part)
self.actual_partition = actual
else:
self.actual_partition = partition
print(q)
if q == best_q:
break
network = self.second_phase(network, partition)
best_partition = partition
best_q = q
return (self.actual_partition, best_q)
'''
Computes the modularity of the current network.
_partition: a list of lists of nodes
'''
def compute_modularity(self, partition):
q = 0
m2 = self.m * 2
for i in range(len(partition)):
q += self.s_in[i] / m2 - (self.s_tot[i] / m2) ** 2
return q
'''
Computes the modularity gain of having node in community _c.
_node: an int
_c: an int
_k_i_in: the sum of the weights of the links from _node to nodes in _c
'''
def compute_modularity_gain(self, node, c, k_i_in):
return 2 * k_i_in - self.s_tot[c] * self.k_i[node] / self.m
'''
Performs the first phase of the method.
_network: a (nodes, edges) pair
'''
def first_phase(self, network):
# make initial partition
best_partition = self.make_initial_partition(network)
while 1:
improvement = 0
for node in network[0]:
node_community = self.communities[node]
# default best community is its own
best_community = node_community
best_gain = 0
# remove _node from its community
best_partition[node_community].remove(node)
best_shared_links = 0
for e in self.edges_of_node[node]:
if e[0][0] == e[0][1]:
continue
if e[0][0] == node and self.communities[e[0][1]] == node_community or e[0][1] == node and \
self.communities[e[0][0]] == node_community:
best_shared_links += e[1]
self.s_in[node_community] -= 2*(best_shared_links + self.w[node])
#self.s_tot[node_community] -= self.k_i[node]
self.s_tot[node_community] -= (self.k_i[node] - 2*best_shared_links)
self.communities[node] = -1
communities = {} # only consider neighbors of different communities
for neighbor in self.get_neighbors(node):
community = self.communities[neighbor]
if community in communities:
continue
communities[community] = 1
shared_links = 0
for e in self.edges_of_node[node]:
if e[0][0] == e[0][1]:
continue
if e[0][0] == node and self.communities[e[0][1]] == community or e[0][1] == node and \
self.communities[e[0][0]] == community:
shared_links += e[1]
# compute modularity gain obtained by moving _node to the community of _neighbor
gain = self.compute_modularity_gain(node, community, shared_links)
if gain > best_gain:
best_community = community
best_gain = gain
best_shared_links = shared_links
# insert _node into the community maximizing the modularity gain
best_partition[best_community].append(node)
self.communities[node] = best_community
self.s_in[best_community] += 2*( best_shared_links + self.w[node])
#self.s_tot[best_community] += (self.k_i[node])
self.s_tot[best_community] += (self.k_i[node] - 2*best_shared_links)
if node_community != best_community:
improvement = 1
if not improvement:
break
return best_partition
'''
Yields the nodes adjacent to _node.
_node: an int
'''
def get_neighbors(self, node):
for e in self.edges_of_node[node]:
if e[0][0] == e[0][1]: # a node is not neighbor with itself
continue
if e[0][0] == node:
yield e[0][1]
if e[0][1] == node:
yield e[0][0]
'''
Builds the initial partition from _network.
_network: a (nodes, edges) pair
'''
def make_initial_partition(self, network):
partition = [[node] for node in network[0]]
self.s_in = [0 for node in network[0]]
self.s_tot = [self.k_i[node] for node in network[0]]
for e in network[1]:
if e[0][0] == e[0][1]: # only self-loops
self.s_in[e[0][0]] += e[1]
self.s_in[e[0][1]] += e[1]
return partition
'''
Performs the second phase of the method.
_network: a (nodes, edges) pair
_partition: a list of lists of nodes
'''
def second_phase(self, network, partition):
nodes_ = [i for i in range(len(partition))]
# relabelling communities
communities_ = []
d = {}
i = 0
for community in self.communities:
if community in d:
communities_.append(d[community])
else:
d[community] = i
communities_.append(i)
i += 1
self.communities = communities_
# building relabelled edges
edges_ = {}
for e in network[1]:
ci = self.communities[e[0][0]]
cj = self.communities[e[0][1]]
try:
edges_[(ci, cj)] += e[1]
except KeyError:
edges_[(ci, cj)] = e[1]
edges_ = [(k, v) for k, v in edges_.items()]
# recomputing k_i vector and storing edges by node
self.k_i = [0 for n in nodes_]
self.edges_of_node = {}
self.w = [0 for n in nodes_]
for e in edges_:
self.k_i[e[0][0]] += e[1]
self.k_i[e[0][1]] += e[1]
if e[0][0] == e[0][1]:
self.w[e[0][0]] += e[1]
if e[0][0] not in self.edges_of_node:
self.edges_of_node[e[0][0]] = [e]
else:
self.edges_of_node[e[0][0]].append(e)
if e[0][1] not in self.edges_of_node:
self.edges_of_node[e[0][1]] = [e]
elif e[0][0] != e[0][1]:
self.edges_of_node[e[0][1]].append(e)
# resetting communities
self.communities = [n for n in nodes_]
return (nodes_, edges_)
'''
Rebuilds a graph with successive nodes' ids.
_nodes: a dict of int
_edges: a list of ((int, int), weight) pairs
'''
def in_order(nodes, edges):
# rebuild graph with successive identifiers
nodes = list(nodes.keys())
nodes.sort()
i = 0
nodes_ = []
d = {}
for n in nodes:
nodes_.append(i)
d[n] = i
i += 1
edges_ = []
for e in edges:
edges_.append(((d[e[0][0]], d[e[0][1]]), e[1]))
return (nodes_, edges_)
###################******************---下面是使用方法的一个例子---******************###################
#下面是Louvain的使用方式
import argparse
import networkx as nx
import random
import matplotlib.pyplot as plt
def getRandomColor():
'''
这是随机获取一种颜色。但是，不能保证获取的颜色差距一定很大。
所以，如果想要直观的看到结果。有时候需要多运行几次。
'''
return random.randint(0,255)
def drawNet_Louvain(G,part_list):
'''
将社区划分完成的图进行直观的展示。
'''
for i in range(len(part_list)):
for j in range(len(part_list[i])):
part_list[i][j] += 1
print(part_list)
color_list = []
for part in part_list:
color = getRandomColor()
for node in part:
color_list.append((node,color))
color_list.sort(key = lambda x: x[0])
print(color_list)
color_list = [x[1] for x in color_list]
plt.figure(figsize=(5, 5))
print("finish")
print(len(G.nodes()))
print(len(color_list))
pos = nx.spring_layout(G)
nx.draw(G, with_labels=True, node_color=color_list, pos=pos)
plt.show()
plt.savefig(r"filename.png")
def main(option):
data_path = option.data_path#此处需要修改对应的数据文件的路径
if (data_path[-3:] == "txt"): #如果文件是在txt中的读取方式
net_G_nodes,net_G_edges = PyLouvain.from_file(data_path) #使他的方法进行数据读取，返回的是点集和边集
net_G = nx.read_edgelist(data_path) #因为他使用的是完全自己实现的代码，无法进行画图展示。所以，需要自己在读入一个networkx的
elif (data_path[-3:] == "gml"): #如果文件是在gml中的读取方式
net_G_nodes,net_G_edges = PyLouvain.from_gml_file(data_path)#使他的方法进行数据读取，返回的是点集和边集
net_G = nx.read_gml(data_path,label="id") #因为他使用的是完全自己实现的代码，无法进行画图展示。所以，需要自己在读入一个networkx的
new_G = PyLouvain(net_G_nodes,net_G_edges) #使用它的方法构造成一个类，传入的参数依次是点集和边集
t,d = new_G.apply_method() #应用其中的方法，对社区进行分割。返回值分别是最佳的社区划分，以及对应的Q值。
drawNet_Louvain(net_G, t) #对分割完成的图进行展示。
if __name__ == "__main__":
parser = argparse.ArgumentParser()
parser.add_argument("--data_path", type=str, default="karate.gml",
help="data_path is the path of the net")
opt = parser.parse_args()
main(opt)
数据集下载
下载 “Louvain算法数据集”
karate.zip – 已下载201次 – 970.00 B
