什么是社团结构 | 集智百科
今天分享网络科学领域里面社团结构这一主题。网络如何连接节点，一个个节点又怎样形成社团，本文将介绍社团结构的基本概念，有哪些好玩的案例，知名的研究者、一些入门的学习资源。
目录
一、什么是社团结构？
二、社团结构应用
三、社团结构发现算法
四、知名学者推介
五、相关资源推介
六、集智百科词条志愿者招募
“物以类聚，人以群分”。在自然界和社会中，具有相似特点的事物往往有更加紧密的联系。比如，具有相同爱好的人更易成为好友等。如果将事物以及他们之间的相互联系表示为网络，那么网络中存在的紧密连接的区域（节点集）称为社团 （Community）。若网络存在社团，则称其具有社团结构（Community structure）。
图1：社团结构示意图
社团结构普遍存在于信息网络、社会网络、生物网络等各类网络中。这些网络中的社团内部连接紧密，常对应某种特点或功能，而社团外部的连接则相对稀疏，即“内紧外松”。根据这个特点，人们可以设计算法来探测网络中的社团结构，从而更好地理解网络中蕴含的信息。
图2：社团结构可视化
二、社团结构应用
二、社团结构应用
社团结构对研究复杂系统有重要价值：在人际关系网络中，社团可表示具有相似特点（如职业、年龄）的群体；在生物网络中，社团与功能模块密切相关；在论文引用网络中，社团代表了某一的研究领域等等。下面介绍几个社团结构应用实例。
领英（Linkedin）职业网络
为了研究劳动力在公司间流动的特点，学者使用领英用户的就业数据构建了一个职业网络，见下图。在网络中，节点为公司，如果职员从一个公司跳槽到另一公司，则在两公司间形成边。图中每个社团对应一种颜色。通过分析社团结构发现，劳动力的流动受地缘位置和行业特点两因素共同影响。
图3：领英职业网络中的社团结构
论文题目：
Global labor flow network reveals the hierarchical organization and dynamics of geo-industrial clusters
论文地址：
https://www.nature.com/articles/s41467-019-11380-w?fbclid=IwAR35Srs8_E5XN2bE0HgY8deFXC2ZCUW0BAkAowbn6A9gGCXtQryiYLbIujc
蛋白质相互作用网络
生物网络中的社团常对应“功能模块”，即参与同一生物过程或具有相似功能的蛋白质集合。例如下图蛋白质相互作用网络中包含多种功能模块（颜色对应模块）。研究发现，通过社团可以识别与与癌症相关的蛋白质，这为预测潜在致病蛋白提供了依据。
图4：蛋白质相互作用网络中的社团结构
论文题目：Community detection in graphs
论文地址：https://arxiv.org/abs/0906.0612
在科学研究中，思想交流非常重要。为了描述科学家之间交流的痕迹，可以观察期刊论文之间的相互引用，构建论文引用网络。为突出论文所属的科学领域，可围绕论文引用网络中的社团构建如下科学图谱。图谱中，节点代表社团所属的领域，边为领域间的引用，箭头代表引用方向（即谁引用谁）。根据图谱，应用领域论文大多引用基础科学领域论文。
图5：基于论文引用的图谱
论文题目：Community detection in graphs
论文地址：https://arxiv.org/abs/0906.0612
三、社团结构发现算法
检测社团结构是个相对困难的任务， 因为网络中的社团数目通常是未知的，且社团的大小、密度不尽相同。尽管如此，还是不断有学者发明了大量检测社团的方法，使这个领域取得了长足发展。下面列举一些经典社团检测算法。
层次聚类（Hierarchical clustering）
层次聚类是一种传统且有效的方法。它通过一种相似性度量（如欧氏距离），来计算节点间拓扑结构的相似性。然后每次找到距离最短的两个社团，然后进行合并成一个大的社团，直到全部合并为一个社团，形成一个树结构。根据需要可自行决定社团数目，得到最终结果。
Girvan-Newman 社团检测算法
另一个常见的社团检测算法是 Girvan-Newman 算法：识别各社团之间连接的边，然后去除这些边，留下的就是社团。该方法利用图论中的介数中心性 （Betweenness centrality）来识别要去除的边。Girvan-Newman算法返回的结果具有较好的质量，得到广泛应用。但其运行较缓慢，不适用于上千节点的网络。
模块度最大值法 （Modularity maximization）
模板度最大值法是用于使用最为广泛的社团检测算法之一。模块度（Modularity） 是一种衡量社团划分质量的标准。模块度最大值法通过搜索所有可能的分组，找到使模块度最大的分组方式作为结果。由于穷举所有可能的分组十分困难，所以实际的算法都采用近似优化方法，如贪婪算法等。
图6：模板度最大值法检测社团结构
注：使用网络科学工具包NetworkX , 可以轻松调用上述三种算法，实现社团检测。
Mark Newman
图7：Mark Newman
在社团检测领域，他提出了模块度最大值算法，是使用最广泛的算法之一。
Santo Fortunato
图8：Santo Forunato
美国印第安纳大学Bloomington分校信息学、计算和工程学院教授。印第安纳大学网络科学研究中心主任。论文总引用量超3万，其中最著名的论文为2010年发表的"Comunity detection in graphs"，引用量超8000，是社团检测领域的经典综述之一。
五、相关资源推荐
五、相关资源推荐
经典文献
S. Fortunato (2010). "Community detection in graphs". Phys. Rep. 486 (3–5): 75–174. arXiv:0906.0612.
M. Girvan; M. E. J. Newman (2002). "Community structure in social and biological networks". Proc. Natl. Acad. Sci. USA. 99(12): 7821–7826. arXiv:cond-mat/0112110.
M E J. Newman (2006). Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, 103(23): 8577-8582.https://www.pnas.org/content/pnas/103/23/8577.full.pdf
复杂网络中的社团结构https://campus.swarma.org/course/1197
算法讲解
Github上热门分享 (收藏超1.2k) - 社团检测相关论文及代码实现集：
https://github.com/benedekrozemberczki/awesome-community-detection
模块度（Modularity）与Fast Newman算法讲解与代码实现：
http://rrd.me/gDT2S
该文章主要介绍了模块度的产生、原理和实现过程。作者利用矩阵形式减少计算时长，最后使用matlab进行计算。
注：以上算法代码均可以实现，更多详情查看词条链接
社团结构:
https://wiki.swarma.org/index.php?title=社团结构
六、百科项目志愿者招募
六、百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由李欣儒、刘佩佩、刘世康、李媛翯参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页:
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
欢迎扫描下方二维码添加负责人加入集智百科团队！
参考资料：
[1]社团结构 集智百科 :
https://wiki.swarma.org/index.php?title=社团结构
[2]社团结构 维基百科:
https://en.wikipedia.org/wiki/Community_structure
[3]社团结构 百度百科 :
https://baike.baidu.com/item/社团结构/19479493?fr=aladdin
[4]CSDN相关算法页面
http://rrd.me/gDT2S
[5]GitHub相关算法页面
https://github.com/benedekrozemberczki/awesome-community-detection
[6]集智学园课程
https://campus.swarma.org/course/1197
来源：集智百科编辑：曾祥轩
推荐阅读
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！
👇点击“阅读原文”，阅读集智百科更多内容：算法代码实现，参与集智百科建设！