Community Detection – Modularity的概念

modularity是Community Detection的paper中很常见的一个概念。简单说,modularity是用来衡量一个网络切分的好坏。

It was designed to measure the strength of division of a network into modules (also called groups, clusters or communities)

要理解modularity的定义,首先需要理解community。目前比较广泛的认识,community是指网络中的一组节点,它们之间的link/connection要比和外界的link/connection更多。modularity正是基于这个定义,通过比较community内部和外部connection来衡量切分的优劣。

2003年,Newman在文献《1》中给出了Modularity最早的定义:

假设网络被切分成了k个community,定义eij是community i 和community j 之间的边的数量占总边数的比例,那么 image  就是这次切分所有存在于community的内部的边的占比。按照之前community的定义,应该尽可能的使得这个值最大,那么自然community的划分就是最好的。

但是上述公式存在着不足之处,例如,如果将整个网络都划分到一个community中,那么自然上述公式的值是最大的(因为所有的边都在community的内部,占比=1)。

为了解决这个问题,重新定义了一个公式:

image

图中的Q就是modularity的定义。(公式的最后其实变成了一个矩阵运算)

文献《1》中提到,一般网络的Q值在0.3 ~ 0.7之间,能够说明很好的community structure。

回过头来看看Modularity的计算方式,会发现它对于community的衡量比早期的一些标准(例如k-clique)要简单很多。它并没有要求community内部具有某种结构,也不要求community中的每个node达到某种标准,而只统计community中内部和外部的边的总数。从计算上,这是很容易做到的,所以后来基于Modularity的算法,在复杂度上都比早期的算法要提高很多。

2006年,还是Newman,在文献《2》中重新定义了Modularity (reformulation of the modularity):

假设有两个node i 和 j,它们的度数分别是 Ki 和 Kj,那么如果随机的话,两个节点间有一条边的概率是(ki * kj)/2m。其中2m是所有节点的度数之和。理解这个公式是理解后续定义的关键。(我一开始怎么都算不对,后来发现,这个概率公式的前提是允许节点的边自己连接自己,允许self-loop,了解这点就很容易看懂这个公式。还不明白的话看wiki

image

Q就是modulariy新版的定义。

The leading factor of 1/4m is merely conventional: it is included for compatibility with the previous definition of modularity

Newman之所以要修改modularity的定义,其实是为了能够将modularity用于spectral optimization algorithms。具体的解释见Wiki

其它

当modularity这个度量被认可后,后续很多算法的思路就是如何找到一个partitioning的方法,使得modularity最大。将community detection转化成了最优化的问题。而因为查找全局最优的modularity是一个NP-hard问题,所以算法都是采用greedy的方法进行搜索。

modularity在large-scale network中有一个缺陷:resolution limit。在large network中,基于modularity的方法找不到那些small community,即便这些small community的结构都很明显。具体的参见文献《3》

最后赞美一下Newman老师。他的paper很简洁,不凑字数,不写废话。这点很赞。

reference

1. Finding and evaluating community structure in networks
2. Modularity and community structure in networks
3. Resolution limit in community detection

— END. —

Advertisements
相册 | 此条目发表在Community Detection, Paper笔记, Social Network分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s