模块度Q(Modularity)

2018-04-07

科研训练项目需要一个指标来度量网络数据聚类结果的好坏，查阅资料了解到有Q、ARI、NMI三个指标可行。
先用Python实现了Q值的求解，所需Python库：networkx、numpy。

正文

关于模块度的介绍，在英文版的维基百科中有很好的解释：Modularity

Modularity is one measure of the structure of networks or graphs. It was designed to measure the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity.

模块度是网络或图形结构的一种度量。它旨在衡量将网络划分为模块（也称为组，团体或社区）的强度。具有高模块性的网络在模块内的节点之间具有密集的连接，但是在不同模块中的节点之间的稀疏连接。模块化经常用于检测网络中社区结构的优化方法。然而，已经表明，模块化遭受了解决方案的限制，因此它无法检测到小型社区。生物网络，包括动物脑，表现出高度的模块性。

1、传统定义

$Q1$

公式参数说明：

m为节点与节点之间的连接个数，通俗点就是图中的边数。

A_vw为邻接矩阵的元素。若节点v和w之间有边，则A_vw = 1，否则A_vw = 0 。

k_v为v节点的度。（图论中的基础知识）

δ(c_v,c_w) 是用来判断节点v和w是否在同一个社区内，在同一个社区内δ(c_v,c_w) = 1，否则δ(c_v,c_w) = 0。

弄清参数之后代码就好写了,下面是Python代码示范：

def Q(G, labels):
	'''
	参数说明：
		G为Graph对象，labels为每一个节点的聚类结果
	'''
	A = nx.adjacency_matrix(G)
	A = A.todense()
	A = np.array(A)
	n = len(G.nodes)
	e = len(G.edges)
	sum = 0
	for i,d_i in enumerate(G.degree()):
		for j,d_j in enumerate(G.degree()):
			if labels[i] == labels[j]:
				sum += A[i][j] - d_i[1]*d_j[1]/(2*e)
	Q = sum/(2*e)
	return Q

2、矩阵公式（Matrix formulation）

$Q2$

$B$

公式参数说明：

**Tr()**为矩阵的迹，在Python中调用numpy.trace()即可求出。

S 为n×k的矩阵（n为节点数，k为聚类组数），如果节点v属于组r，则定义S_vr = 1 ，否则S_vr = 0。

公式B中的参数与传统定义中的参数相同

Python代码实现：

def Q(G, labels, n_clusters):
	'''
	参数说明：
		G为Graph对象，labels为每一个节点的聚类结果,n_clusters为聚类个数
	'''
	A = nx.adjacency_matrix(G)
	A = A.todense()
	A = np.array(A)
	n = len(G.nodes)
	e = len(G.edges)
	
	S = np.zeros((n, n_clusters))
	for index, value in enumerate(G.nodes):
		S[index][labels[index]] = 1

	B = np.zeros((n, n))
	for i,v_i in enumerate(G.nodes):
		for j,v_j in enumerate(G.nodes):
			B[i][j] = A[i][j] - G.degree(v_i)*G.degree(v_j)/(2*e)

	Q = 1/(2*e) * np.trace(S.T @ B @ S)
	return Q

测试

利用Network data的K-Means聚类实现中的代码进行测试，调用两个不同的方法，结果如下：

0.508448009282
0.508448009282

完美