networkx学习（八）社区_networkx.cluster

networkx学习（八）社区

参考：参考来源，《巴拉巴西网络科学》

比利时似乎是典型的双文化社会： 59%的公民是说荷兰语的弗拉芒人， 40%的公民是说法语的瓦隆人。 随着全世界的多民族国家纷纷分裂， 我们不禁要问： 比利时如何促进了两个民族自1830年以来的和平共处？ 这是不是一个无论弗拉芒人还是瓦隆人都同样紧密相连的社会？ 抑或在这个国家里存在彼此联系不多的两个小国家？

文森特· 布隆代尔（Vincent Blondel） 和他的学生在2007年给出了答案。 他们发明了一种算法来识别这个国家的社区结构。 他们从手机通话网络开始， 把频繁打电话的个体放在一起[2]。 算法表明， 比利时的社交网络分裂为两个大的社群， 每个社群内部的个体极少与另一个社群中的个体通话（图8-1） 。 他们给每个个体节点标注了其所使用的语言后， 这一分裂的原因便显而易见： 其中一个群体（cluster） 几乎只包括说法语的人， 另一个群体中则都是说荷兰语的人。

在网络科学中， 如果一组节点内部链接紧密， 外部链接稀疏， 那么我们称这组节点为一个社区（community） 。 接下来我们讨论社区发挥重要作用的两个场景， 以便直观地理解社区的意义。

1.社区基础

最大团

关于社区结构的早期论文之一（发表于1949年）将一个所有成员都相互认识的群体定义为社区[5]。用图论的术语来讲，社区是一个完全子图，或者说一个团。团自然满足H2：是连通子图且有最大的链接密度。然而，若将社区视为团，会有如下缺陷：
● 虽然网络中存在大量三角形，但更大的团很少出现。
● 要求社区是完全子图可能太严苛了，很多合理的社区都不满足这一条件。例如，图8-2和图8-3中的社区无一是完全子图。

强社区和弱社区

社区数目

有多少种方式将网络中的节点组织成社区？若想回答这个问题，我们需要考虑最简单的社区识别问题，即图的二划分（graph bisection）问题：将一个网络分成两个不重叠的子图，使得两部分节点之间的链接数（被称为割集的大小）最小。

2.层次聚类

若想识别大型真实网络的社区结构，我们需要运行时间为N多项式的算法。本节的主题层次聚类（hierarchical clustering）能帮助我们达到这一目标。

层次聚类首先计算相似度矩阵（similarty matrix），矩阵的每个元素xij表示节点i
和节点j之间的距离。在社区识别中，相似度刻画了节点i和j在网络中的相对位置。

当我们计算好xij之后，层次聚类迭代地将高相似度的节点识别为节点组。我们有两种不同的程序：凝聚算法（agglomerative algorithms）将高相似度的节点合并到同一社区，而分裂算法（divisive algorithms）会删除社区之间的低相似度链接以将社区彼此分离。两种程序都会生成一棵表示可能的社区划分的层次树，我们称之为树状图。接下来我们讨论凝聚算法和分裂算法的使用，以识别网络中的社区。

凝聚算法

分裂算法