二、模块度最大化算法

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

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

算法流程：

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

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

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

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

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

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

论文题目：

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

论文地址：

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

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

四、相关资源推荐

集智推文

Nature通讯：科学家兴趣转移愈发频繁，但对科研生涯可能不利

社团结构分析——基于模块度优化的快速展开算法（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

五、百科项目志愿者招募

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

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

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

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

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