什么是社团检测中的模块度 | 集智百科

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！
今天分享网络科学领域里面模块度这一主题。如何探寻网络中的社团结构，挖掘更多网络背后的信息。本文将介绍模块度的基本概念，有哪些好玩的案例，知名的研究者、一些入门的学习资源。

目录

一、什么是模块度？

二、模块度最大化算法

三、知名学者推介

四、相关资源推介

五、集智百科词条志愿者招募

一、什么是模块度 ？

信息网络、社会网络、生物网络等各类网络中会存在一些紧密连接的区域。这些区域（节点集）常对应某种功能，称为社团（Community），见下图。社团内部连接紧密，而社团外部的连接则相对稀疏，即“内紧外松”。根据这个特点，人们设计了算法来探测网络中的社团结构，从而更好地理解网络中蕴含的丰富信息。

图1：网络中的社团结构可视化

相关阅读：

“检测网络中的社团”等同于“给节点分组”。模块度（Modularity）是一种常用的衡量节点分组质量的标准。模块度越高说明所检测到的社团越符合“内紧外松”的特征，分组质量越好。

基于模块度的概念，网络科学奠基人之一Mark Newman于2004年提出了一种经典的社团检测方法——模块度最大值法（Modularity maximization）。它通过考虑网络中所有可能的节点分组，找到使得模块度最大的分组方式。基于模块度的社团检测算法至今仍被广泛使用。

图2：在网络中划分模块

要计算一个网络的模块度，需要构造一个具有相同节点度分布的随机网络作为参照。通俗地来说，模块度的物理含义是：在社团内，实际的边数与随机情况下的边数的差距。如果差距比较大，说明社团内部密集程度显著高于随机情况，社团划分的质量较好。模块度取值范围在[-0.5,1]之间。如果节点组中的连边数量超过了随机分配时所得到的期望连边数量，模块度为正数。没有超过，则为负数。

注：模块度的公式推导，请点击文末“阅读原文”，查阅集智百科原文。

二、模块度最大化算法

模板度最大值法是使用最为广泛的社团检测方法之一。该方法的目标是从所有可能的分组中找到使得模块度最大的分组。由于穷举所有可能的分组十分困难，所以实际的算法都采用近似优化方法。例如，Mark Newman 提出了模块度最大化的贪婪算法 Fast NewMan (FN)。贪婪算法的原理是找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。

图3：模块度最大化算法检测社团示意图

算法流程：

1. 初始时将网络中的每个节点都看成独立的小社团。

2. 考虑所有相连社团两两合并的情况，计算每种合并带来的模块度的增量。

3. 基于贪婪原则，选取使模块度增长最大的两个社团，将它们合并成一个社团。

4. 如此循环迭代。随着迭代的进行，模块度不断变化，其最大值时对应最优社团划分。 

后来，Vincent Blondel等人运用模板度最大值法的基本原理，提出了Louvain算法，大大降低了算法的时间复杂度。十分适合社会网络等超大规模网络的社团检测。也成为应用最广的算法之一。使用Python的网络科学工具包NetworkX , 可以轻松调用该算法，实现社团检测。

NetworkX：是Python在复杂网络分析领域的软件包，网络分析的必备神器，谁用谁知道。它功能强大，几乎覆盖复杂网络分析中的所有可计算的概念。小伙伴们只要会使用Python进行基本编程，就可以用起来。

官网地址：

https://networkx.github.io

图4：运用模块度最大值算法检测出的社团。节点为公司，边为公司间职员的流动。蓝色为线上为主的公司、黄色为线下为主的公司、红色为线上线下兼顾的公司。

论文题目：

Global labor flow network reveals the hierarchical organization and dynamics of geo-industrial clusters

论文地址：

https://www.nature.com/articles/s41467-019-11380-w

三、 相关学者推荐

Mark Newman

图5：Mark Newman

美国密歇根大学物理系和复杂系统研究中心特聘教授。同时也是圣塔菲研究所 （Santa Fe Institue）外聘教授。网络科学的先驱者之一，2014年被授予拉格朗日奖。他的论文总引用量超过18万，著有网络科学经典著作《Networks: An Introduction》。

在社团检测领域，他提出了模块度最大值算法，是使用最广泛的算法之一。

四、相关资源推荐

集智推文

社团结构分析——基于模块度优化的快速展开算法（fast unfolding algorithm）通过快速展开算法识别科学家的社团结构。

研究人员还用模块最大化社群发现算法 ，找到了几个主要的、内部联系紧密的社群

文献

在大型网络中检测社团结构

论文题目：

Finding community structure in very large networks

论文地址：

http://ece-research.unm.edu/ifis/papers/community-moore.pdf

定义模块度的作者Newman and M. Girvan 论文——网络社团结构的发现与评价

论文题目：

Finding and evaluating community structure in networks

论文地址：

https://arxiv.org/pdf/cond-mat/0308217.pdf

网络中的模块度和社团结构

论文题目：Modularity and community structure in networks论文地址：
https://www.pnas.org/content/pnas/103/23/8577.full.pdf

五、百科项目志愿者招募

作为集智百科项目团队的成员，本文内容由李欣儒、刘佩佩、刘世康、宋多多参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页:

以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。

在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。

欢迎扫描下方二维码添加负责人加入集智百科团队！

参考资料：

模块度  集智百科：

https://wiki.swarma.org/index.php?title=模块度

模块度 百度百科：

https://baike.baidu.com/item/模块度/17556345?fr=aladdin

模块度  维基百科：

https://en.wikipedia.org/wiki/Modularity_(networks)

来源：集智百科编辑：曾祥轩

推荐阅读

---

集智俱乐部QQ群｜877391004

商务合作及投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！

👇点击“阅读原文”，阅读更多关于模块度的内容。