模块度

模块度（modularity）是评价网络某个社群划分的量：比较组内实际边数与一个基准矩阵给出的组内边量。它评价的是“图与划分的配合”，不是每个图只有一个与划分无关的固定分数；较大的模块度也不自动证明发现了唯一真实社群。

两个三角形 $123$ 与 $456$ 由边 $34$ 相连，共七条边。按两个三角形分组，各组内部三条边，组内顶点度数之和都是七。这个例子可以同时展示模块度的实际项、基准项和合并两个组的影响。

度和包括组内边贡献两次和跨组桥贡献一次，因此每组是七而不是六。

双重求和与按组计算

设 $G$ 为有限无向简单图，至少有一条边；邻接矩阵为 $A$，度为 $k_i$，边数为 $m>0$。顶点划分为互不重叠且覆盖全体的组，$c_i$ 为顶点的组号。标准模块度定义为 $$Q=\frac{1}{2m}\sum _{i,j}(A_{ij}-\frac{k_i{k}_j}{2m}){\mathrm{𝟏}}_{\{c_i=c_j\}}.$$ 求和包含 $i=j$；虽然简单图 $A_{ii}=0$，基准对角项仍参与定义。基准矩阵行和为 $k_i$，总和为 $2m$，表达保持度量级的比较。

对组 $C$，记内部边数为 $m_C$、度和为 $D_C=\sum _{i\in C}{k}_i$。组内邻接元素和为 $2m_C$；基准乘积和为 $D_C^2/(2m)$。代回定义，逐组得到 $$Q=\sum _C[\frac{m_C}{m}-{\left(\frac{D_C}{2m}\right)}^2].$$ 这一步说明两种公式为何相同，并解释内边与度和各怎样计数。

主例的两组划分给出 $Q=2[3/7-(7/14{)}^2]=5/14$。把所有顶点放同一组，得到 $1-1=0$；把六点各成一组，得到 $Q=-(2^2+2^2+3^2+3^2+2^2+2^2)/14^2=-17/98$。负值是合法的，表示该划分的组内边量低于所选基准。

合并公式与分辨率限制

若两个现有组为 $C,D$，组间边数为 $e_{CD}$，合并时内部边增加 $e_{CD}$，基准平方从 $D_C^2+D_D^2$ 变成 $(D_C+D_D{)}^2$，故 $$\Delta Q=\frac{e_{CD}}{m}-\frac{D_C{D}_D}{2m^2}.$$ 在双三角例中为 $1/7-49/98=-5/14$，所以合并降低模块度。

变式。 保持这六点和桥不变，在远处再加入二十条彼此分离的边，仍把其他部分的分组固定。此时总边数变成二十七，原两组度和仍为七。合并它们的变化却成为 $$\Delta Q=\frac{1}{27}-\frac{49}{2\cdot 27^2}=\frac{5}{1458}>0.$$ 相同局部结构因全图规模改变而被模块度偏好合并。这是一个可复算的分辨率限制，说明最大化标准模块度可能合并小而清晰的组。

常用推广是在基准项前乘 $\gamma >0$，于是合并公式中的第二项也乘 $\gamma$。改变 $\gamma$ 是改变比较尺度；全体一组的分数相应为 $1-\gamma$，不能继续无条件用零作参照。

基准项 $k_i{k}_j/(2m)$ 不必小于一，不能逐项解释为简单边存在的概率。它也不是有限配置模型中任意两点连边数的精确期望：后者对不同点的精确分母是 $2m-1$。这里采用的是模块度定义中的标准基准。无边图分母为零，须另作约定；有向图和加权图也需要相应度、强度和总量定义。报告结果应保留使用的划分、权重和分辨率，避免只报一个最高数值。