与小世界性[1]、无标度等基本统计特性相并列，Girvan&Newman[2]在2001年发现的网络社区结构(Community Structure)是复杂网络最普遍和最重要的拓扑结构属性之一，具有相同社区节点相互连接密集、不同社区节点相互连接稀疏的特点，如图1所示。复杂网络中的社区发现方法目的在于揭示出复杂网络中真实存在的网络社区结构。

图1 社区结构

对于一个给定的网络$G=(V,E)$，其中$V$为网络的节点集，$E$为网络的边集。将$G$划分为$q$个社区，我们用一个$q\times q$的对称矩阵$\textbf{e}$来表示该划分，$\textbf{e}$中的每个元素表示连接社区$i$与社区$j$的边在$G$的全部边中所占的比例，显然有$\sum_{i,j}e_{ii}=1$。矩阵$\textbf{e}$的迹$Tr(\textbf{e})$表示连接社区内部节点的边的占比，一个好的社区划分应该有一个数值很高的迹。

但研究发现，单独使用迹$Tr(\textbf{e})$在一些情况下无法很好地测度划分质量，例如这样一个平凡划分：将所有点放到同一个社区中。此时$Tr(\boldsymbol{e})$=1为最大值，但该划分在绝大部分情况下显然不具有任何意义。

Newman[3]认为，考虑一个与$G$具有相同社区划分、相同边数但节点间随机连接的随机网络$G’$，若$G$具有社区结构，社区内部边占总边数的比例应该大于随机情况下的该比例的期望。实际社区内部边与期望的差越大，说明网络与随机网络的差异越大，即网络越具有社区结构。则模块度定义为

理论上有$Q\in[-1,1]$，但取值为$\pm1$的情况是极为罕见的。$G$的一个社区划分的模块度为正数时，表明社区结构可能存在。在该定义下，平凡划分(将所有点放到同一个社区中)的模块度为$Q=0$。

上述定义是简单且直接的，但存在一个问题：在构建随机网络$G’$时，没有考虑到原网络$G$的节点度。由于节点的度在一定程度上能够表示该节点被连接的概率，所以Newman[4]于2006年对模块度进行了重新定义。

考虑一个具有$n$个节点的无向无权网络，我们可以用它的邻接矩阵$\textbf{A}$来表示该网络。$\textbf{A}$是一个的$n\times n$对称矩阵，通常来说

一般地，我们约定$A_{ii}=0$。在允许多重边存在的网络中，$A_{ij}$允许取比1大的值。

将网络划分为$q$个不重叠的社区，令$g_{i}$表示节点$i$所在的社区，则$\boldsymbol{g}=(g_{1},...,g_{n})$是对网络的一个划分。对于一个特定的划分$\boldsymbol{g}$，网络的社团内部边的数量为$\frac{1}{2}\sum\limits_{i,j}{{A_{ij}}{\delta_{{g_i}{g_j}}}}$，其中$\delta_{ij}$是一个克罗内克函数(Kronecker delta):

对于随机网络$G’$，保持原网络$G$的边数$m$与各节点的度不变，将这$m$条边随机地重新定位到任意两个节点间。随机化后，令$P_{ij}$表示节点$i$与$j$相连接的概率，则社区内部边数的期望值为$\frac{1}{2}\sum\limits_{i,j} {{P_{ij}}{\delta_{{g_i}{g_j}}}}$。故重新定义的模块度为：

对于一个特定的网络，模块度的大小与$m$不相关，仅与社区划分有关。这一定义使用边数的比例而不是边数的绝对值，这使得不同规模的网络划分的模块度可以进行比较。注意到，此时平凡划分的模块度为：

因为在随机化中，网络中边的数量被视为常数，即$\sum\nolimits_{ij}{{P_{ij}}}=\sum\nolimits_{ij} {{A_{ij}} = 2m}$。

现在需要确定如何计算$P_{ij}$。这个值依赖于我们用来做随机化的方案。一个简单的方案是，对于任意两个节点$i$和$j$，令它们具有相同的连接概率，即对于给定边数$m$、节点数$n$的网络，有：

理论上说，这里$P_{ij}$应该是节点$i$与节点$j$之间的边数的期望而不是$i$与$j$相连接的概率，但由于$m然而实际上，节点间的连接很大程度上依赖于节点的度，但如(6)式表示的$P_{ij}$没有考虑到节点的度。因此，我们需要一个能够保持节点度数的带约束随机化方案。这里，Newman使用了configuration model产生随机图集合[5],[6]。随机化后，两个节点之间的连接概率为 {c_{n}^{2}}$，故期望与概率很接近。

其中${k_i} = \sum\nolimits_j {{A_{ij}}}$是节点i的度。至此，我们得到了重新定义的模块度：

Newman指出，在实践中，好的划分的$Q$值应当取值在0.3~0.7之间，更高的数值是很罕见的。这一重新定义的模块度也是目前使用范围最广的模块度。

根据Fortunato&Barthelemy[7]的研究成果，在对(8)式进行最优化来寻找社团划分时有一个缺点：无法找出那些实际具有许多小社团的网络中的社团划分。特别地，当网络中的社团数大于$\sqrt{2m}$时，通过使(8)最大化找到的社团划分与正确划分可能不符——基于(8)的模块度最优化方法寻找到的社区划分倾向于将一个个小社区合并成更大的社区，这样使得基于模块度最优的方法不能发现网络中较小的社区。

为了解决上述问题，Arenas[8]在2008年基于Reichardt&Bornholdt[9]在2006年对启发式概念与汉密尔顿函数(Hamiltonian)的推导与讨论，提出了一个广义模块度的概念：

显然，(8)定义的模块度为(9)的一个特殊情况($\gamma=1$)。

Q3与Q2的区别在于参数$\gamma$，称为分辨率参数(resolution parameter)。这使得Q3优化法比Q2优化法具有更高的灵活性，能够发现更多结构下的网络社区划分。但即便是这样，模块度优化法也存在一定的问题。

Lancichinetti&Fortunato[10]在2012年证实了多分辨率模块度(Q3)存在着一个问题：当取较小的值时，倾向于将小的社团合并为大社团；当大时，倾向于将大社团分裂在社团大小分布不一的网络中。而我们不可能同时消除这两种偏差，Q3也无法发现正确的社区结构。

Jeub、Sporns&Fortunato[14]等人指出，最佳划分应当对应于分辨率参数取正确值的位置。但是在缺乏关于网络的先验知识的情况下，预先确定是很困难的，尽管Newman[11]于2015年证明了基于Q2优化的社区发现算法在特定情况下与极大似然估计方法等价，将模块度优化法与下列2种模型联系了起来，并提出了一种可能的计算方法。

SBM是一种生成随机图的模型。给定网络的先验信息$m$、$n$、$q$以及$\bf{\Omega}$和$\bf{g}$，将$m$条边随机分配到各节点之间形成一个随机网络。

Newman指出，随机块模型生成随机网络的过程中，连接任意两个节点$i$和$j$的边的数量通常不是随机的，而是服从以为$\omega_{rs}$参数的Poisson分布，其中$r$、$s$分别为节点i和j所在的社团。至此，可以得出随机块模型假设网络$\textbf{A}$的连接的生成过程为：

因此在理论上，在生成的随机网络中，一对节点之间可能存在多条边，并且允许存在节点自己与自己相连接的情况。与其他情况不太一样的是，节点与自身相连边的数量服从以$\frac{1}{2}\omega_{rr}$为参数的Poisson分布。(实际上，还有另一个Bernoulli分布版本的随机块模型，也适用于往下得出的结论，但Newman在文章中仅给出了Poisson分布版本)

上述随机网络的假设在某些情况下是适用的，例如论文引用网络与万维网超链接网络：一篇论文可在另一篇论文中被重复引用，一个网页在另一个网页中也可能被重复引用。在其他大多数情况下，上述随机网络显然不太符合现实。但由于大部分的现实网络是非常稀疏的，这意味着边连接概率$\omega_{rs}$非常小。因此在这种情况下，网络中多重边与自连边的密度很小，通常可以忽略不计。

上述SBM是基于先验信息生成一个随机网络。而社区发现算法则与其相反，是根据给定的观测网络来推断社区划分。具体地，这里希望求出的参数是：边的概率$\omega_{rs}$和社团成员$g_i$。

假定一个邻接矩阵为$\bf{A}$的观测网络由一个参数为$\bf{\Omega}$和$\bf{g}$的Poisson形式的SBM生成，则观测网络由该模型生成的概率为：

如同1.1节中Q1一样，SBM没有考虑到节点度的影响。这导致该模型(无论是Bernoulli形式还是Poisson形式)生成了一个具有Poisson(或Bernoulli)度分布的网络，这与经验网络中的广泛分布非常不同。

为了解决这一问题，Karrer与Newman[12]在2011年提出了DCBM，将连接节点$i$与$j$的边数的期望值由$\omega_{rs}$改为了$\frac{k_{i}k_{j}}{{2m}}\omega_{rs}$，其中自连边的期望保持不变。与1.2节中一样，$\frac{k_{i}k_{j}}{{2m}}$是随机化时节点$i$与$j$的连接概率，$\omega_{rs}$代表两个社团之间相连接的概率。

遵循与2.2中相同的推导思路，忽略那些对极大似然估计值的位置没有影响的因素，得到

至此，社区发现算法转化为:寻找合适的$\bf{\Omega}$与$\bf{g}$使(13)最大化，以寻找出与观测网络最匹配的社区划分。

PPM是SBM的一个特例，其描述社团结构的参数仅取两个值：

这意味着它假设各个社团拥有相同的社团内部、社团间连接概率。根据(14)可得：

将(15)、(16)代入(13)得

其中，$\text{B}$与$C$是仅与$\delta_{in}$和$\delta_{out}$有关、与$\bf{g}$无关的常数，且

为了进行社区发现，现在要将(17)这个关于社区分配$\bf{g}$与参数$\omega_{in}$、$\omega_{out}$的函数最大化。假设我们已知正确参数$\omega_{in}$和$\omega_{out}$，那么当且仅当获得正确的$\bf{g}$时，该值最大。

注意到，式(17)除开两个常数$\text{B}$与$C$外，与(9)式并没有什么不同。由此可知，式(17)与式(9)在相同位置上取到最大值，即已知参数$\omega_{in}$和$\omega_{out}$的PPM的极大似然估计法与以式(18)为参数的广义模块度最优法等价。

要求解正确的$\gamma$，只需求出$\omega_{in}$与$\omega_{out}$，这里使用迭代方法来进行求解。其思想为，先设定一个初始的$\gamma$值，利用模块度最优法获取一个社区划分，对该划分，社团内部边$m_{in}$的期望为：

其中${\kappa_r} = \sum\nolimits_i {{k_i}{\delta_{{g_i},r}}} $表示社团r中所有节点的度的和。由式(19)可得

同理可得

实际计算时，使用所有社团内部边的观测值来表示$m_{in}$。

综上，总结求解解析参数$\gamma$的步骤如下：

模块度最优法与极大似然估计法的等价说明了：

随机块模型统一假设网络具有Poisson度分布，使得拟合网络与真实网络的近似性很差。相比之下，度修正模型适合任何度分布网络。如Bickel和Chen[13]的研究成果显示，在适当的条件下，模块度最优得到的社区结构是正确且无偏的。

$B = m\log \frac{{{\omega_{in}}}}{{{\omega_{out}}}}$的符号取决于$\omega_{in}$和$\omega_{out}$的大小。当${\omega_{in}} > {\omega_{out}}$时，原结论成立；当${\omega_{in}}

Newman假设$\omega_{rs}$仅取两个值：$\omega_{in}$、$\omega_{out}$，这意味着任意社团内部、任意两个社团之间的连接程度相同，这与现实不符。故该指标虽然在理论上有所依托，但实际运用时还存在较大困难。

关于Newman提出的$\gamma$计算方案的疑惑：在2.4节中，Newman令$B = m\log \frac{{{\omega_{in}}}}{{{\omega_{out}}}}$与$C = m\left( {\log {\omega_{out}} - {\omega_{out}}} \right)$时，作出的假设是“$\text{B}$与$C$是仅与$\omega_{in}$和$\omega_{out}$有关，与$\bf{g}$无关的常数”。但在2.5节计算参数时，$\gamma$的取值与$m_{in}$、$\sum\nolimits_r {\kappa_r^2}$两个数有关。其中$\kappa_{r}$代表社团$r$内部节点的度数之和。显然，不同的社团划分方案(即$\bf{g}$)对应着不同的$\sum\nolimits_r {\kappa_r^2}$值，与2.4中作出的结论矛盾。