最近在调研社区发现图聚类在区域划分中的应用，将一些编辑汇总的信息记录如下。

社团划分了解

社区是什么

在社交网络中，用户相当于每一个点，用户之间通过互相的关注关系构成了整个网络的结构。在这样的网络中，有的用户之间的连接较为紧密，有的用户之间的连接关系较为稀疏。其中连接较为紧密的部分可以被看成一个社区，其内部的节点之间有较为紧密的连接，而在两个社区间则相对连接较为稀疏。整个整体的结构被称为社团结构。如下图，圆点和方点呈现出社区的结构，

用圆点和方点对其进行标注，整个网络被划分成了两个部分，其中，这两个部分的内部连接较为紧密，而这两个社区之间的连接则较为稀疏。如何去划分上述的社区便称为社区划分的问题。

社区划分的出发点和意图

直观地说，community detection的一般目标是要探测网络中的“块”cluster或是“社团”community。

这么做的目的和效果有许多，比如说机房里机器的连接方式，这里形成了网络结构，那么，哪些机器可以视作一个“块”？进一步地，什么样的连接方式才有比较高的稳定性呢？如果我们想要让这组服务瘫痪，选择什么样的目标呢？

节点间存在连接的抽象本质 - 逻辑拓朴结构

社区的节点间是网络拓朴结构，即节点间是存在拓朴连接结构的，我们不能将其和欧式空间或者P空间中的点向量集合空间混为一谈。

以欧式空间为例，不同的节点向量存在于不同的空间位置中，向量夹角近的点向量彼此距离近，而向量夹角远的向量彼此距离远。但是即使是欧式距离很近的向量点，也不一定就代表着它们之间存在拓朴连接关系，只能说在一定的度量下（例如欧式距离度量），这两个节点很相近。

但是在社区结构中，节点之间没有什么空间位置的概念。相对的，节点间存在的是一种逻辑拓朴结构，即存在一种共有关系。

存在共有关系的节点在逻辑上会聚集为一个社区，而社区之间不存在或者存在很弱的共有关系，则呈现分离的逻辑拓朴结构。

请注意不要用空间结构的概念来试图理解社区结构，不然会陷入理解的困境，社区中的节点只是因为逻辑上的共有关系而聚集在一起而已，彼此之间的位置也没有实际意义，而社区族群之间的分离也是表达一种逻辑上的弱共有关系。

举一些实际的例子：

• 节点代表消费者：节点间的连接代表了它们共同购买了一批书籍，weight代表共同购买的书籍数；
• 节点代表DNS域名：节点间的连接代表了它们拥有一批共同的src client ip（客户端），weight代表了共同的src_ip数量；

什么时候可以使用社区发现算法

我们需要先确定要解决的业务场景中，存在明显的聚集规律，节点（可以是抽象的）之间形成一定的族群结构，而不是呈现无规律的随机分散。同时另一方面，这种聚集的结构是“有意义的”，这里所谓的有意义是指这种聚集本身可以翻译为一定的上层业务场景的表现。

但是很多时候，我们业务场景中的数据集之间的共有关系并不是表现的很明显，即节点之间互相都或多或少存在一些共有关系，这样直接进行社区发现效果肯定是不好的。
所以一个很重要点是，我们在进行社区发现之前，一定要进行数据降噪。

理想情况下，降噪后得到的数据集已经是社区完全内聚，社区间完全零连接，这样pylouvain只要一轮运行就直接得到结果。当然实际场景中不可能有这么好的情况，数据源质量，专家经验的丰富程度等等都会影响降噪的效果，一般情况下，降噪只要能cutoff 90%以上的噪音，pylouvain就基本能通过几轮的迭代完成整体的社区发现过程。

社区划分的评价标准

社区划分的目标是使得划分后的社区内部的连接较为紧密，而在社区之间的连接较为稀疏。

但什么样的结构能成为团呢？一种很直观的想法是，同一团内的节点连接更紧密，即具有更大的density。
接下来的问题是，什么样的metrics可以用来描述这种density？

模块度

背景

Modularity(模块度), 这个概念是2003年一个叫Newman的人提出的。这个人先后发表了很多关于社区划分的论文，包括2002年发表的著名的Girvan-Newman(G-N)算法，和2004发表的Fast Newman(F-B)算法，Modularity就是F-B算法中提出的（03年提出的概念，04年确认发表）。

在2006年的时候Newman重新定义了Modularity，实际上只是对原来的公式做了变换，使其适用于Spectral Optimization Algorithms。

早期的算法不能够很好的确认什么样的社区划分是最优的。Modularity这个概念就是为了定义一个对于社区划分结果优劣的评判。

介绍

模块度$Q$是描述社区内紧密程度的值，是评估一个社区网络划分好坏的度量方法，它的物理含义是网络中社区结构内部节点的边的数量与在同样的社团结构下随机连接两个节点的比例的期望值之差，或者是社区内节点的连边的权重之和与随机情况下的连边的权重之和的差距，它的取值范围是 [-1, 1]，其定义如下：
$$\mathrm{Q}=\frac{1}{2m}\sum _{i,j}[A_{ij}-\frac{k_i{k}_j}{2m}]\delta (c_i,c_j)$$
其中：

• $A$为邻接矩阵，$A_{ij}$代表了节点$i$和节点$j$之间边的权重，网络不是带权图时，所有边的权重可以看做是 1;
• ${\mathrm{k}}_i={\sum }_j{A}_{ij}$是所有与节点$i$相连的边的权重之和（如果是无权图，就是度数），$k_j$也是同样；
• $\mathrm{m}=\frac{1}{2}{\sum }_{i,j}{A}_{ij}$表示所有边的权重之和（边的数目），充当归一化的作用；
• $C_i$表示节点$i$分配到的社区，$\delta (c_i,c_j)$表示的是一个函数，判断节点$i$和节点$j$是否划分到同一个社区，若是，返回1；否则，返回0；这个函数的作用在于自动单独对每一个社区内的节点进行计算，因为当计算不同社区的节点时，这一项为0，整个式子为0，所以其实也可以单独计算每一个社区的Q值然后进行累加即可，类似于一个帮忙分段的函数；

注释：
对于$\mathrm{m}=\frac{1}{2}{\sum }_{i,j}{A}_{ij}$，这里需要注意，$A_{ij}$的计算是重复的，比如我们以node x为当前节点的时候，计算了一次edges的权重之和，例如x和y，x和z，x和k……，当我们以node y为当前节点进行计算的时候，我们的计算是y和x，y和z，y和k……，可以发现x和y这两个nodes进行edges的求和的时候，x-y和y-x实际上是重复计算了，因此实际上计算总的edges的权重之和的时候，每条edge的权重都被重复计算了两次，所以m的公式前面有个1/2；

为了更好的理解这里举一个具体的例子：

如上图，假设我们有一个graph，这个社区graph中有7个nodes，为了方便起见我们假设所有edges的权重均为1（带权重的计算方式是完全一样的），这个时候我们先计算整个graph的边的权重m：

比如假设当前i=1，j=1~7，则$A_{11}$=0（节点和自身之间不存在edge，权重为0），$A_{12}$=1，$A_{13}$=1，$A_{14}$=1，…，$A_{17}$=0（无edge连接，权重也是0），则对于A来说其计算结果为3，同理$A_{21}$=1，$A_{22}$=0，$A_{23}$=1，……，$A_{27}$=0，计算结果是2，则对所有的nodes都进行如上的两轮循环的遍历之后，得到的$A_{ij}$的计算结果是：node 1：3 、 node2：2 、 node3：5、node4：2、node5：1、node6：2、node7：1
则求和之后的结果为：16。
但是实际上我们一共就8条edges，每条edges的权重为1，总权重之和为8，这里计算结果为16就是因为edges之间重复计算的问题，因此m的结果需要在前面加1/2才表示真实的权重。

模块度 = （落在同一社区内的边的比例） - （对这些边进行随机分配所得到的概率期望）
假设网络有$n$个节点，有$m$条边，节点 i 的度表示为$k_i$。
那么上述模块度定义就可以表示为：$$\mathrm{Q}=\frac{1}{2}\frac{{\sum }_{i,j}{A}_{ij}}{m}\delta (c_i,c_j)-(对这些边进行随机分配所得到的概率期望)$$

$\frac{{\sum }_{i,j}{A}_{ij}}{m}\delta (c_i,c_j)$表示在同一社区内的边的数量占所有边数量的比例，乘以$\frac{1}{2}$，上边已经证明过，是因为对每条边计算过两次。那么期望值如何计算呢？这里面用到了Configuration Models，大致是对网络的边进行随机分配，需要将每条边切断一分为二，切断的点我们称作末梢点(stub)，这样$m$条边就会产生$2m$个末梢点，随机的将这 $2m$个末梢点进行连接，包括同一节点拥有的末梢点的自连接，即允许节点的边自己连接自己，允许self-loop。这样可以保持每个节点原有的度不变的条件下，可以得到一个完全随机网络。

假设有两个node i 和 j，它们的度数分别是$k_i$和$k_j$，那么如果随机的话，两个节点之间有一条边的概率是$\frac{k_i{k}_j}{2m}$。同理，将度换成权重，对于某一个节点$i$，其权重为$k_i$，则在随机情况下，节点$i$和节点$j$的权重值的期望值为$k_i\frac{k_j}{2m}$。

模块度的公式定义可以作如下简化：
$\mathrm{Q}=\frac{1}{2m}{\sum }_{i,j}[A_{ij}-\frac{k_i{k}_j}{2m}]\delta (c_i,c_j)$
$=\frac{1}{2m}[{\sum }_{i,j}{A}_{ij}-\frac{{\sum }_i{k}_i{\sum }_j{k}_j}{2m}]\delta (c_i,c_j)$
$=\frac{1}{2m}{\sum }_c[{\sum }_{in}-\frac{({\sum }_{tot}{)}^2}{2m}]$

其中：

• ${\sum }_{in}$表示社区$c$内的边的权重之和，比如nodeA和nodeB相连并且在一个社区，这个社区只有A和B两个nodes，则这个社区的权重就是A->B和B->A的连接的edge的权重之和，注意两个方向都要算.
• ${\sum }_{tot}$表示与社区$c$内的节点相连的所有边的权重之和。

根据上述公式我们可以知道，社区内部权重之和越大，社区与外部连接权重越小，则模块度越大，上面的公式还可以进一步简化成:
$$Q=\sum _c[\frac{{\sum }_{in}}{2m}-(\frac{{\sum }_{tot}}{2m}{)}^2]=\sum _c[e_c-a_c^2]$$

这样模块度也可以理解是：
首先modularity是针对一个社区的所有节点进行了累加计算。
modularity Q的计算公式背后体现了这种思想：社区内部边的权重和减去所有与社区节点相连的边的权重和，对无向图更好理解，即社区内部边的度数减去社区内节点的总度数。
极端情况，如果一个社区节点完全是封闭的（即所有节点都互相内部连接，但是不和社区外部其他节点有连接，则modularity公式的计算结果为1）。

基于模块度的社区发现算法，都是以最大化模块度$Q$为目标。可以看到，这种模型可以支持我们通过策略优化，去不断地构造出一个内部聚集，外部稀疏连接的社区结构。在一轮迭代后，若整个$Q$没有变化，则停止迭代，否则继续迭代，直至收敛。

模块度增量 delta Q

模块增益度是评价本次迭代效果好坏的数值化指标，这是一种启发式的优化过程。类似决策树中的熵增益启发式评价。模块度增益的公式：

分了两部分，前面的这一项表示节点$i$入射社区$c$之后的模块度，这里就是套一个模块度公式而已；后边这一项 表示的是节点$i$入射社区$c$之前，社区$c$和节点$i$分别单独作为一个社区的时候，二者的模块度之和。

进一步化简可以得到：$$=\frac{1}{2m}（k_{i,in}-\frac{{\sum }_{tot}{k}_i}{m}）$$

其中：

• $k_{i,in}$代表由节点$i$入射社区$c$的权重之和，即社区$c$内节点与节点$i$的边权重之和，注意对$k_{i,in}$是对应边权重加起来再乘以2，这点在实现时很容易犯错；
• ${\sum }_{in}$表示社区$c$内所有节点之间的边权重和（社区内边）；
• ${\sum }_{tot}$表示所有与社区$c$中节点有连接的边权重和；
• $k_i$代表入射节点$i$的总权重，即节点$i$连接的所有边的权重和
• $m$是整个网络中的边权重之和

在算法的first phase，判断一个节点加入到哪个社区，需要找到一个delta Q最大的节点 $i$ ，delta Q的作用类似决策树中的信息增益评估的作用，它帮助整个模型向着Modularity不断增大的方向去靠拢。

举例：
如下图，这是初始的graph，A到F一共6个节点。

初始阶段，节点之间的合并，以节点A为例：
A→B：$$Q_{AB}=5-\frac{10\ast 7}{30}=2.667$$
A→C：$$Q_{AC}=4-\frac{10\ast 13}{30}=-0.333$$
A→E：$$Q_{AE}=1-\frac{10\ast 9}{30}=-2$$

以A->B为例，

• 5 为A和B之间的权重；
• 30 是整个graph的权重之和；
• 10 是A和所有和它连接的边的权重之和；
• 7 是其它节点和社区B(初始阶段每一个节点当作一个社区，这里的社区B就是节点B)之间的权重的和；
  对比一下公式：$$\frac{1}{2m}（k_{i,in}-\frac{{\sum }_{tot}{k}_i}{m}）$$

实际上上述的过程就是实现的括号里面的计算，1/2m 是一个常量，在运行的过程中可以忽略；$k_{i,in}$是实际的节点$A$指向社区$B$的权重，$\frac{{\sum }_{tot}{K}_i}{m}$表示的是平均意义之下节点$A$指向社区$B$的期望权重，如果真实权重大于期望权重，则代表了节点$A$和社区$B$的连接关系是存在显著意义的；

此外，如果对graph进行了折叠和重构，则m表示整个graph去除了社区内边的权重之后剩下的边的权重之和，下边会有介绍；且 louvain 和模块度的定义都是针对于无向图的，虽然存在directed louvain这种针对于有向图的louvain算法，但是目前networkx，igraph，neo4j等的实现都是面向无向图的。

社区发现经典算法-Louvain

Louvain是目前市面上提到的和使用过的最常用的社区发现算法之一，除此之外就是infomap，这两种。

Louvain算法是基于模块度的社区发现算法，由Vincent D.Blondel等人在2008年提出（论文地址：Fast unfolding of communities in large networks），该算法在效率和效果上都表现较好，是目前社区发现算法中计算速度最快的算法，并且能够发现层次性的社区结构，其优化目标是最大化整个社区网络的模块度，即让整个社区网络呈现出一种模块聚集的结构。通过模块度可以刻画划分的优劣，模块度越大，则社区划分的效果越好 。

Louvain算法是一种基于多层次（逐轮启发式迭代）优化Modularity的算法。Modularity函数最初被用于衡量社区发现算法结果的质量，它能够刻画发现的社区的紧密程度。
同时，Modularity函数既然能刻画社区的紧密程度，也就能够被用来当作一个优化函数（目标函数），即将结点加入它的某个邻居所在的社区中，如果能够提升当前社区结构的modularity。则说明这次迭代优化是可接受的。

总结基于模块度优化的启发式方法优点：

1. 计算速度快：在计算时间上优于其他所有已知的社区检测方法。
2. 效果好：检测的社区质量很好（通过模块度度量）
   （注：原作者在1.18亿个节点的网络中识别社区只需要152分钟）

LOUVAIN算法策略

Fast Unfolding算法是一种迭代的算法，主要目标是不断划分社区使得划分后的整个网络的模块度不断增大。
Louvain算法主要分为两个阶段：

• 第一阶段称为Modularity Optimization，每个原始节点都看成一个独立的社区，社区内的连边权重为0，算法扫描数据中的所有节点，针对每个节点遍历该节点的所有邻居节点，衡量把该节点加入其邻居节点所在的社区所带来的模块度的收益。并选择对应最大收益的邻居节点，加入其所在的社区。这一过程化重复进行指导每一个节点的社区归属都不在发生变化；
• 第二阶段称为Community Aggregation，对步骤1中形成的社区进行折叠，把每个社区折叠成一个单点，分别计算这些新生成的“社区点”之间的连边权重，以及社区内的所有点之间的连边权重之和。用于下一轮的步骤1。重复以上的过程，直到网络中的结构不再改变为止。

同时需要注意，Louvain算法是一个迭代算法，每一轮迭代都会产出一个当前局部最优的社区结构，所以理论上，假如算法迭代了5次，我们可以得到5个不同粒度层次的社区结构，从业务场景上，这为我们发现不同的社区聚集提供了一个更灵活的视角。

LOUVAIN算法流程

算法形式化描述

1. 初始化。将图中的每个节点看成一个独立的社区，社区的数目与节点个数相同；
2. first phase：社区间节点转移。对每个节点 ，依次尝试把节点 分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化Δ，并记录Δ最大的那个邻居节点，如果Δ>0，则把节点 分配到Δ最大的那个邻居节点所在的社区，否则保持不变；
3. 重复步骤2，直到所有节点的所属社区不再变化；
4. second phase：图重构。对图进行压缩，将所有在同一个社区的节点压缩成一个新节点，社区内节点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节点间的边权重；
5. 重复步骤1，直到整个图的模块度不再发生变化。
   

算法时间复杂度

从流程来看，该算法能够产生层次性的社区结构，其中计算耗时较多的是最底一层的社区划分，节点按社区压缩后，将大大缩小边和节点数目。并且计算节点$i$分配到其邻居$j$时，模块度的变化只与节点$i,j$的社区有关，与其他社区无关，因此计算很快。

first phase的每次迭代的时间复杂度为$O(N)$，$N$为输入数据中的边的数量。second phase的时间复杂度为O(M + N)， $M$为本轮迭代中点的个数。

举例

还是以上述例子为例，初始的graph，A到F一共6个节点。

初始阶段，节点之间的合并，以节点A为例：
A→B：$$Q_{AB}=5-\frac{10\ast 7}{30}=2.667$$
A→C：$$Q_{AC}=4-\frac{10\ast 13}{30}=-0.333$$
A→E：$$Q_{AE}=1-\frac{10\ast 9}{30}=-2$$

同样的，我们可以得到所有节点的最大模块度增益的计算结果：
B→C：$$Q_{BC}=2-\frac{7\ast 13}{30}=-1.033$$
C→D：$$Q_{CD}=7-\frac{13\ast 10}{30}=2.667$$
D→F：$$Q_{DF}=3-\frac{10\ast 11}{30}=-0.667$$
E→F：$$Q_{EF}=8-\frac{9\ast 11}{30}=4.7$$

小于0则不进行社区划分，大于0则取最大的模块度增益对应节点进行合并，合并之后我们得到：

这是初始阶段的合并的结果，然后算法继续运行：
红色→黄色：$$Q_{ry}=6-\frac{7\ast 9}{10}=-0.3$$
红色→绿色：$$Q_{rg}=1-\frac{7\ast 4}{10}=-1.8$$
黄色→绿色：$$Q_{yg}=3-\frac{9\ast 4}{10}=-0.6$$

以红色—>黄色为例，

• 6为红色和黄色社区的连接的边的权重之和；
• 7是红色社区和所有与它连接的边的权重之和 2+4+1=7；
• 9是其它社区和黄色社区的连接的边的权重之和 2+4+3=9；

此外需注意，graph的权重发生了改变，m=10而不是30，因为此时划分出来的社区已经拿走了一部分边的权重，所以实际上整个graph的权重应该去掉社区内的边的权重重新计算！

此时，由上面的计算可以知道模块度增益都是小于0的，迭代停止，此时即为最终的社区划分的结果。

关于启发式/贪婪思想的社区发现优化思考

在社区发现的项目中，很容易遇到的问题是：“社区过大，louvain会有outerlier合并到大群的倾向”。换句话说，社区聚类的过程中没有能及时收敛。这里的outerlier可能为节点，也可能为分离小群。

参照一下模块度增量$deltaQ$的公式$\frac{1}{2m}（k_{i,in}-\frac{{\sum }_{tot}{k}_i}{m}）$ ，举一个极端的例子，假设某个小群$X$和某个大群$B$之间只有一条权重为1的边连接，但是小群除了这一条边之外就没有和任何其它的节点或者社群连接了，此时模块度增量$deltaQ$公式括号里的第二项为0，此时也是满足模块度增益大于0的，会进行小群和大群的合并，但是从业务逻辑上来说，此时大群和小群不应该进行合并；

更形象化的，以下边这张图来说明：

如果按照启发式/贪婪思想进行”one-step one node“的社区聚类，$O_9、O_{10}、O_{11}$会被先加入到社区$D$中，因为在每次这样的迭代中，$D$社区内部的紧密度（不管基于node密度还是edge得modularity评估）都是不断提高，符合算法的check条件，因此，$O_9、O_{10}、O_{11}$会被加入到社区$D$中。

随后，$O_1,...,O_8$也会被逐个被加入到社区D中，加入的原因和$O_9、O_{10}、O_{11}$被加入是一样的。
从局部上来看，这些步骤是合理的，但是如果从全局来看，这种做法导致outerlier被错误的聚类到的社区中，导致precision下降。

解决这个问题的方法有两种：

• 图萃取，先给边设置权重，再通过边权重过滤连接比较弱的边（比如直接将这些连接比较弱的边的权重置为0），然后分群。同时边权重细分可以提升度数较高的节点分群质量；
• 修改模块度增益的公式，设置一个Delta增益的最小阈值，即在每轮的迭代中（社区扩增后紧密度提升的度量）模块度增益必须大于该阈值才会发生合并，如果不超过这个阈值，则判定为收敛成功，停止算法迭代。

从实施难度上来看，第一种方式更简单 第二种需要修改源码逻辑；

如何评价分群质量

Louvain算法采用的是无向图，无向图模块度的理论值范围时[-1,1]。从 Louvain 分群过程看，算法迭代的目标是增加每个模块的模块度，所以可从分完群后图整体的模块度评价分群质量，模块度越大分群质量越高。（提供一个参考值，一般>0.44 就说明该网络图达到了一定的模块化程度 ，图分群后1级群模块度在0.3_{0.7之间，2级群在0.4}0.8之间。）

附录

度：在无向图中，与某节点关联的边的条数称为该节点的度。有向图中，则以节点$X$为弧尾的弧的条数称为节点$X$ 的出度，以节点$X$ 为弧头的弧的条数称为节点$X$ 的入度，而节点$X$ 的度=出度+入度。图中各点度数之和是边（或弧）的条数的2倍。

参考文献

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

Paper:
Louvain算法原文。
Fast unfolding of communities in large networks
模块度定义作者论文1。
Finding and evaluating community structure in networks
模块度定义作者论文2。
Modularity and community structure in networks

Blog:
Community Detection – Modularity的概念
模块度Q——复杂网络社区划分评价标准
社区发现算法——louvain完全指南（更新，仅适用于无向）
【图算法】社区发现算法——Fast unfolding
社区发现算法 - Fast Unfolding（Louvian）算法初探
模块度与Louvain社区发现算法
【社区发现】Fast-Unfolding算法Python实现
Louvain快速社区发现算法（Fast unfolding算法）
【论文笔记】Fast unfolding of communities in large networks