社区发现（子区划分）：模块度及模块度增量计算公式推导
介绍社区发现（子区划分/网络聚类）的基本概念：模块度以及模块度增量；对其中的重要公式进行推导、证明
社区发现：模块度 Q Q Q及模块度增量 Δ Q \Delta Q ΔQ计算公式
重点参考该文章（基本上是全网最详细的模块度计算说明，非常值得一看）：
Modularity的计算方法——社团检测中模块度计算公式详解 | 雅乐网 (yalewoo.com)
一、模块度计算公式
1.1、相关概念
1.1.1、图
图是一种由节点、边组成的复杂网状结构
-
按照边的有无方向可以分为有向图、无向图；按照边有无权重可以分为有权图、无权图；
-
相邻节点：两个节点通过一条边相连（图中节点1、2相邻）；
-
节点的度：与节点相连的边的数量（图中节点1度为2）
节点邻接矩阵 A A A：
- A i j A_{ij} Aij表示节点 i 、 j i、j i、j是否相连，不相连则 A i j = 0 A_{ij}=0 Aij=0，否则 A i j = 1 A_{ij}=1 Aij=1（如果是加权图，则为权重值）
A i j = { 1 i , j 相邻 0 i , j 不相邻 \begin{equation} A_{ij}=\left\{ \begin{aligned} 1 & \quad i,j相邻\\ 0 & \quad i,j不相邻\\ \end{aligned} \right . \end{equation} Aij={10i,j相邻i,j不相邻
| 节点 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 | 0 | 1 |
| 5 | 1 | 0 | 0 | 1 | 0 |
1.1.2、社区发现
社区：社区是图的普遍属性，一个图中可能有多个社区，同一社区内节点与节点之间关系紧密，社区与社区之间的关系稀疏
社区发现（Community Detection）：可以当作图中结构紧密的节点的聚类，即将各个节点划分为不同的社区，使得社区内节点之间连接紧密，社区间连接稀疏
- 与聚类算法同属非监督学习，核心都是节点间距离度量、节点所属类别判断、“聚类”效果评价；
- 经典社区发现算法以模块度作为社区紧密程度的度量指标，以模块度最大为“聚类”的目标，以模块度增量最大确定节点所属的社区
- 工程应用包括交通领域的控制子区划分：将交叉口作为节点，路段作为边，将包含几十个交叉口的大路网划分为若干个“小区”，分别进行信号控制。
模块度 Q Q Q：是社区内节点紧密程度的度量指标，是衡量社区划分效果最常用的评价指标，值越大表明社区划分效果越好
社区关联矩阵 E E E：
-
e i i e_{ii} eii表示子区 i i i内边数与图中边数的比值；
-
e i j , i ≠ j e_{ij},i\neq j eij,i=j表示子区 i i i与子区 j j j相连的边数与图中边数的比值的 1 / 2 1/2 1/2（因为同一条边会被 e i j 、 e j i e_{ij}、e_{ji} eij、eji重复计算）；
-
a i = ∑ j e i j a_i=\sum_{j}e_{ij} ai=∑jeij，表示子区i内的节点度数和与图中所有节点度数和的比值；
-
图中共6条边（度数和为12），划分为3个子区，其中子区 I I I内有1条边，子区 I 、 I I I、II I、II之间有1条边，子区 I 、 I I I I、III I、III之间有2条边则 e 11 = 1 / 6 = 2 / 12 ， e 22 = 1 / 12 ， e 22 = 2 / 12 ， a 1 = 1 / 6 + 2 / 12 + 1 / 12 = 5 / 12 e_{11}=1/6=2/12，e_{22}=1/12，e_{22}=2/12，a_1=1/6+2/12+1/12=5/12 e11=1/6=2/12，e22=1/12，e22=2/12，a1=1/6+2/12+1/12=5/12
| 子区 | I | II | III |
|---|---|---|---|
| I | 1/6 | 1/12 | 2/12 |
| II | 1/12 | 0 | 1/12 |
| III | 2/12 | 1/12 | 1/6 |
1.2、公式及证明
说明：以无权无向图为例进行证明
1.2.1、公式形式一
Q = ∑ i ( e i i − a i 2 ) = t r ( E ) − ∣ ∣ E 2 ∣ ∣ 其中， e i i 为社区关联矩阵 E 中对角线上的元素，表示子区 i 内边数与图中边数的比值 a i = ∑ j e i j ，表示子区 i 内的节点度数和与图中所有节点度数和的比值 ∣ ∣ E 2 ∣ ∣ 表示矩阵 E 2 的各个元素之和 Q=\sum_{i}({e_{ii}-a_i^2})=tr(E)-||E^2||\\ 其中，e_{ii}为社区关联矩阵E中对角线上的元素，表示子区i内边数与图中边数的比值\\ a_i=\sum_{j}e_{ij}，表示子区i内的节点度数和与图中所有节点度数和的比值\\ ||E^2||表示矩阵E^2的各个元素之和 Q=i∑(eii−ai2)=tr(E)−∣∣E2∣∣其中，eii为社区关联矩阵E中对角线上的元素，表示子区i内边数与图中边数的比值ai=j∑eij，表示子区i内的节点度数和与图中所有节点度数和的比值∣∣E2∣∣表示矩阵E2的各个元素之和
证明：
∑
i
(
e
i
i
−
a
i
2
)
=
t
r
(
E
)
−
∣
∣
E
2
∣
∣
\sum_{i}({e_{ii}-a_i^2})=tr(E)-||E^2||
∑i(eii−ai2)=tr(E)−∣∣E2∣∣
∑
i
(
e
i
i
−
a
i
2
)
=
∑
i
e
i
i
−
∑
i
a
i
2
其中，
∑
i
e
i
i
=
t
r
(
E
)
，仅需证明
∑
i
a
i
2
=
∣
∣
E
2
∣
∣
对于下图所示
E
矩阵，计算
E
2
时：
对于
E
11
,
与第一行的元素相乘形成
3
个多项式，分别为：
e
11
e
11
,
e
11
e
12
,
e
11
e
13
对于
E
21
,
与第二行的元素相乘形成
3
个多项式，分别为：
e
21
e
11
,
e
21
e
12
,
e
21
e
13
对于
E
31
,
与第三行的元素相乘形成
3
个多项式，分别为：
e
31
e
11
,
e
31
e
12
,
e
31
e
13
则
e
11
e
11
+
e
11
e
12
+
e
11
e
13
+
e
21
e
11
+
e
21
e
12
+
e
21
e
13
+
e
31
e
11
+
e
31
e
12
+
e
31
e
13
=
e
11
(
e
11
+
e
12
+
e
13
)
+
e
21
(
e
11
+
e
12
+
e
13
)
+
e
31
(
e
11
+
e
12
+
e
13
)
=
(
e
11
+
e
21
+
e
31
)
(
e
11
+
e
12
+
e
13
)
因为
E
为对称矩阵，所以
(
e
11
+
e
21
+
e
31
)
(
e
11
+
e
12
+
e
13
)
=
(
e
11
+
e
12
+
e
13
)
2
即第一行的元素之和的平方，由此可知
∣
∣
E
2
∣
∣
为各行元素和的平方累加
即，
∣
∣
E
2
∣
∣
=
∑
i
(
∑
j
e
i
j
)
2
=
∑
i
a
i
2
\sum_{i}({e_{ii}-a_i^2})=\sum_{i}e_{ii}-\sum_{i}a_i^2\\ 其中，\sum_{i}e_{ii}=tr(E)，仅需证明\sum_{i}a_i^2=||E^2||\\ 对于下图所示E矩阵，计算E^2时：\\ 对于E_{11},与第一行的元素相乘形成3个多项式，分别为：e_{11}e_{11},e_{11}e_{12},e_{11}e_{13}\\ 对于E_{21},与第二行的元素相乘形成3个多项式，分别为：e_{21}e_{11},e_{21}e_{12},e_{21}e_{13}\\ 对于E_{31},与第三行的元素相乘形成3个多项式，分别为：e_{31}e_{11},e_{31}e_{12},e_{31}e_{13}\\ 则e_{11}e_{11}+e_{11}e_{12}+e_{11}e_{13}+e_{21}e_{11}+e_{21}e_{12}+e_{21}e_{13}+e_{31}e_{11}+e_{31}e_{12}+e_{31}e_{13}\\ =e_{11}(e_{11}+e_{12}+e_{13})+e_{21}(e_{11}+e_{12}+e_{13})+e_{31}(e_{11}+e_{12}+e_{13})\\ =(e_{11}+e_{21}+e_{31})(e_{11}+e_{12}+e_{13})\\ 因为E为对称矩阵，所以(e_{11}+e_{21}+e_{31})(e_{11}+e_{12}+e_{13})=(e_{11}+e_{12}+e_{13})^2\\ 即第一行的元素之和的平方，由此可知||E^2||为各行元素和的平方累加 \\ 即，||E^2||=\sum_{i}(\sum_{j}e_{ij})^2=\sum_{i}a_i^2
i∑(eii−ai2)=i∑eii−i∑ai2其中，i∑eii=tr(E)，仅需证明i∑ai2=∣∣E2∣∣对于下图所示E矩阵，计算E2时：对于E11,与第一行的元素相乘形成3个多项式，分别为：e11e11,e11e12,e11e13对于E21,与第二行的元素相乘形成3个多项式，分别为：e21e11,e21e12,e21e13对于E31,与第三行的元素相乘形成3个多项式，分别为：e31e11,e31e12,e31e13则e11e11+e11e12+e11e13+e21e11+e21e12+e21e13+e31e11+e31e12+e31e13=e11(e11+e12+e13)+e21(e11+e12+e13)+e31(e11+e12+e13)=(e11+e21+e31)(e11+e12+e13)因为E为对称矩阵，所以(e11+e21+e31)(e11+e12+e13)=(e11+e12+e13)2即第一行的元素之和的平方，由此可知∣∣E2∣∣为各行元素和的平方累加即，∣∣E2∣∣=i∑(j∑eij)2=i∑ai2
1.2.2、公式形式二
Q = 1 2 m ∑ i j [ A i j − k i k j 2 m ] δ ( i , j ) 其中， m 为图中边数， A i j 为邻接矩阵 A 中的元素， k i 、 k j 分别为节点 i 、 j 的度 δ ( i , j ) = { 1 i , j 属于同一个社区 0 i , j 不属于同一个社区 Q=\frac{1}{2m}\sum_{ij}[A_{ij}-\frac{k_i k_j}{2m}]\delta(i,j)\\ 其中，m为图中边数，A_{ij}为邻接矩阵A中的元素，k_i、k_j分别为节点i、j的度\\ \begin{equation} \delta(i,j)=\left\{ \begin{aligned} 1 & \quad i,j属于同一个社区\\ 0 & \quad i,j不属于同一个社区\\ \end{aligned} \right . \end{equation} Q=2m1ij∑[Aij−2mkikj]δ(i,j)其中，m为图中边数，Aij为邻接矩阵A中的元素，ki、kj分别为节点i、j的度δ(i,j)={10i,j属于同一个社区i,j不属于同一个社区
对于该公式形式，可以将模块度理解为各个社区内连边数与随机期望的差值之和，当实际的边数越高于随机的期望时，这个图的节点就越集中。
对于图中的节点1、2，实际连边数 A 12 = 1 A_{12}=1 A12=1，期望连边数= k 1 k 2 2 m = 2 3 12 = 1 2 k_1\frac{k_2}{2m}=2\frac{3}{12}=\frac{1}{2} k12mk2=2123=21
即，期望连边数= k 1 k 2 2 m \frac{k_1 k_2}{2m} 2mk1k2，证明详见：Modularity的计算方法——社团检测中模块度计算公式详解 | 雅乐网 (yalewoo.com)
1.2.3、公式等价性
证明： Q = ∑ i ( e i i − a i 2 ) = t r ( E ) − ∣ ∣ E 2 ∣ ∣ = 1 2 m ∑ i j [ A i j − k i k j 2 m ] δ ( i , j ) Q=\sum_{i}({e_{ii}-a_i^2})=tr(E)-||E^2||=\frac{1}{2m}\sum_{ij}[A_{ij}-\frac{k_i k_j}{2m}]\delta(i,j) Q=∑i(eii−ai2)=tr(E)−∣∣E2∣∣=2m1∑ij[Aij−2mkikj]δ(i,j)
其中：
对于左式： ∑ i ( e i i − a i 2 ) = ∑ i e i i − ∑ i a i 2 \sum_{i}({e_{ii}-a_i^2})=\sum_{i}e_{ii}-\sum_{i}a_{i}^2 ∑i(eii−ai2)=∑ieii−∑iai2
对于右式： 1 2 m ∑ i j [ A i j − k i k j 2 m ] δ ( i , j ) = 1 2 m ∑ r ∑ m n A m n r − 1 ( 2 m ) 2 ∑ r ∑ m n k m r k n r \frac{1}{2m}\sum_{ij}[A_{ij}-\frac{k_i k_j}{2m}]\delta(i,j)=\frac{1}{2m}\sum_{r}\sum_{mn}A^r_{mn}-\frac{1}{(2m)^2}\sum_{r}\sum_{mn}k^r_m k^r_n 2m1∑ij[Aij−2mkikj]δ(i,j)=2m1∑r∑mnAmnr−(2m)21∑r∑mnkmrknr
∑ m n \sum_{mn} ∑mn表示计算属于同一子区的节点之间的指标和， ∑ r \sum_r ∑r表示计算各个子区的指标和
分别证明 ∑ i e i i = 1 2 m ∑ r ∑ m n A m n r 以及 ∑ i a i 2 = 1 ( 2 m ) 2 ∑ r ∑ m n k m r k n r \sum_{i}e_{ii}=\frac{1}{2m}\sum_{r}\sum_{mn}A^r_{mn}以及\sum_{i}a_{i}^2=\frac{1}{(2m)^2}\sum_{r}\sum_{mn}k^r_m k^r_n ∑ieii=2m1∑r∑mnAmnr以及∑iai2=(2m)21∑r∑mnkmrknr
- 对于 ∑ i e i i = 1 2 m ∑ r ∑ m n A m n r \sum_{i}e_{ii}=\frac{1}{2m}\sum_{r}\sum_{mn}A^r_{mn} ∑ieii=2m1∑r∑mnAmnr
1 2 m ∑ r ∑ m n A m n r = ∑ r ∑ m n A m n r 2 m 对于子区 r 内的节点 m 、 n , A m n r = A n m r 因此 ∑ r ∑ m n A m n r 2 m = ∑ r 子区内边数 m = ∑ i e i i \frac{1}{2m}\sum_{r}\sum_{mn}A^r_{mn}=\sum_{r}\sum_{mn}\frac{A^r_{mn}}{2m}\\ 对于子区r内的节点m、n,A^r_{mn}=A^r_{nm}\\ 因此\sum_{r}\sum_{mn}\frac{A^r_{mn}}{2m}=\sum_r \frac{子区内边数}{m}=\sum_{i}e_{ii}\\ 2m1r∑mn∑Amnr=r∑mn∑2mAmnr对于子区r内的节点m、n,Amnr=Anmr因此r∑mn∑2mAmnr=r∑m子区内边数=i∑eii
两个表达式都表示各个子区内的边数与总边数的比值之和，因此相等
- 对于 ∑ i a i 2 = 1 ( 2 m ) 2 ∑ r ∑ m n k m r k n r \sum_{i}a_{i}^2=\frac{1}{(2m)^2}\sum_{r}\sum_{mn}k^r_m k^r_n ∑iai2=(2m)21∑r∑mnkmrknr
a i = ∑ j e i j ，表示子区 i 内的节点度数和与图中所有节点度数和的比值 即， a i = 度数 和 i 2 m 因此， ∑ i a i 2 = ∑ i ( 度数 和 i ) 2 ( 2 m ) 2 对于某一个子区， ( 度数 和 i ) 2 = ( k 1 + k 2 + . . . ) 2 = ∑ m n k m r k n r 即子区内任意两点度数乘积之和 因此， ∑ i a i 2 = ∑ i ( 度数 和 i ) 2 ( 2 m ) 2 a_i=\sum_{j}e_{ij}，表示子区i内的节点度数和与图中所有节点度数和的比值\\ 即，a_i=\frac{度数和_i}{2m}\\ 因此，\sum_{i}a_{i}^2=\frac{\sum_i{(度数和_i)^2}}{(2m)^2}\\ 对于某一个子区，(度数和_i)^2=(k_1+k_2+...)^2=\sum_{mn}k^r_m k^r_n\\ 即子区内任意两点度数乘积之和\\ 因此，\sum_{i}a_{i}^2=\frac{\sum_i{(度数和_i)^2}}{(2m)^2} ai=j∑eij，表示子区i内的节点度数和与图中所有节点度数和的比值即，ai=2m度数和i因此，i∑ai2=(2m)2∑i(度数和i)2对于某一个子区，(度数和i)2=(k1+k2+...)2=mn∑kmrknr即子区内任意两点度数乘积之和因此，i∑ai2=(2m)2∑i(度数和i)2
1.3、模块度计算示例
1.3.1、对于公式形式一
e 11 = 1 / 6 ， e 22 = 0 ， e 33 = 1 / 6 a 1 = 1 / 6 + 1 / 12 + 2 / 12 = 5 / 12 ， a 2 = 1 / 12 + 0 + 1 / 12 = 2 / 12 ， a 3 = 2 / 12 + 1 / 12 + 1 / 6 = 5 / 12 Q = ( 1 / 6 + 0 + 1 / 6 ) − ( 5 / 12 ) 2 − ( 2 / 12 ) 2 − ( 5 / 12 ) 2 = − 1 / 24 e_{11}=1/6，e_{22}=0，e_{33}=1/6\\ a_1=1/6+1/12+2/12=5/12，a_2=1/12+0+1/12=2/12，a_3=2/12+1/12+1/6=5/12\\ Q=(1/6+0+1/6)-(5/12)^2-(2/12)^2-(5/12)^2=-1/24 e11=1/6，e22=0，e33=1/6a1=1/6+1/12+2/12=5/12，a2=1/12+0+1/12=2/12，a3=2/12+1/12+1/6=5/12Q=(1/6+0+1/6)−(5/12)2−(2/12)2−(5/12)2=−1/24
1.3.2、对于公式形式二
令 B i j = A i j − k i k j 2 m B_{ij}=A_{ij}-\frac{k_i k_j}{2m} Bij=Aij−2mkikj，矩阵 B B B如下：
| 节点 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | -1/3 | 1/2 | -1/3 | -1/2 | 2/3 |
| 2 | 1/2 | -3/4 | 1/2 | 1/4 | -1/2 |
| 3 | -1/3 | 1/2 | -1/3 | 1/2 | -1/3 |
| 4 | -1/2 | 1/4 | 1/2 | -3/4 | 1/2 |
| 5 | 2/3 | -1/2 | -1/3 | 1/2 | -1/3 |
根据 δ ( i , j ) \delta(i,j) δ(i,j)的含义以及图中各个节点是否相邻确定 δ ( i , j ) \delta(i,j) δ(i,j)的值，如下：
| 节点 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 1 | 1 |
计算得到模块度 Q = − 1 / 24 Q=-1/24 Q=−1/24
二、模块度计算公式的矩阵形式
矩阵形式公式参考该文章，其中原论文中也有类似的公式形式
2.1、证明过程
Q = 1 2 m ∑ i j [ A i j − k i k j 2 m ] δ ( i , j ) = 1 2 m t r ( S T B S ) 其中， B i j = A i j − k i k j 2 m Q=\frac{1}{2m}\sum_{ij}[A_{ij}-\frac{k_i k_j}{2m}]\delta(i,j)=\frac{1}{2m}tr(S^TBS)\\ 其中，B_{ij}=A_{ij}-\frac{k_i k_j}{2m} Q=2m1ij∑[Aij−2mkikj]δ(i,j)=2m1tr(STBS)其中，Bij=Aij−2mkikj
公式推导：
对于左式：
∑ i j δ ( i , j ) B i j \sum_{ij}\delta(i,j)B_{ij} ∑ijδ(i,j)Bij表示对 B B B中所属同一个子区的元素求和（包含对角线上的元素）
对于右式：
- S S S为 N ∗ R N*R N∗R的矩阵，其中的元素 S i j S_i^j Sij表示节点 i i i是否属于子区 j j j
S i j = { 1 i 属于子区 j 0 i 不属于子区 j \begin{equation} \\S_i^j=\left\{ \begin{aligned} 1 & \quad i属于子区j\\ 0 & \quad i不属于子区j\\ \end{aligned} \right . \end{equation} Sij={10i属于子区ji不属于子区j
-
根据矩阵迹的交换律（章节2.2），可知 t r ( S T B S ) = t r ( S S T B ) tr(S^TBS)=tr(SS^TB) tr(STBS)=tr(SSTB)
-
根据矩阵 S S S的特性可知 S S T SS^T SST为 N ∗ N N*N N∗N的矩阵，并且其中的元素 S S i j T SS^T_{ij} SSijT表示节点 i , j i,j i,j是否属于同一个子区
S S i j T = { 1 i , j 属于同一个子区 0 i , j 不属于同一个子区 \begin{equation} \\SS^T_{ij}=\left\{ \begin{aligned} 1 & \quad i,j属于同一个子区\\ 0 & \quad i,j不属于同一个子区\\ \end{aligned} \right . \end{equation} SSijT={10i,j属于同一个子区i,j不属于同一个子区
- S S T B SS^TB SSTB为 N ∗ N N*N N∗N的矩阵
t r ( S S T B ) = ∑ i = 1 N S S T B i i = ∑ i = 1 N ∑ k = 1 N S S i k T B k i 其中， S S i k T B k i = { B k i i , k 属于同一个子区 0 i , k 不属于同一个子区 tr(SS^TB)=\sum_{i=1}^N{SS^TB}_{ii}=\sum_{i=1}^N{\sum_{k=1}^N{SS^T_{ik}B_{ki}}}\\ 其中，\\ \begin{equation} \\SS^T_{ik}B_{ki}=\left\{ \begin{aligned} B_{ki} & \quad i,k属于同一个子区\\ 0 & \quad i,k不属于同一个子区\\ \end{aligned} \right . \end{equation} tr(SSTB)=i=1∑NSSTBii=i=1∑Nk=1∑NSSikTBki其中，SSikTBki={Bki0i,k属于同一个子区i,k不属于同一个子区
则 t r ( S S T B ) tr(SS^TB) tr(SSTB)即为对 B B B中所属同一个子区的元素求和（包含对角线上的元素）
因此， t r ( S S T B ) = ∑ i j δ ( i , j ) B i j tr(SS^TB)=\sum_{ij}\delta(i,j)B_{ij} tr(SSTB)=∑ijδ(i,j)Bij
Q = 1 2 m t r ( S T B S ) Q=\frac{1}{2m}tr(S^TBS) Q=2m1tr(STBS)，得证
2.2、矩阵迹
（1）定义
在线性代数中，一个 N ∗ N N*N N∗N的矩阵 A A A的迹（或迹数），是指 A A A的主对角线（从左上方至右下方的对角线）上各个元素的总和，一般记作 t r ( A ) tr(A) tr(A)或 s p ( A ) sp(A) sp(A)， t r ( A ) = A 11 + A 22 + . . . + A N N = ∑ i = 1 N A i i tr(A)=A_{11}+A_{22}+...+A_{NN}=\sum_{i=1}^{N}A_{ii} tr(A)=A11+A22+...+ANN=∑i=1NAii
（2）示例
A
=
[
3
5
1
0
9
2
7
6
4
]
A=\begin {bmatrix} 3&5&1 \\ 0&9&2 \\ 7&6&4 \end {bmatrix}
A=
307596124
则，
t
r
(
A
)
=
A
11
+
A
22
+
A
33
=
3
+
9
+
4
=
16
tr(A)=A_{11}+A_{22}+A_{33}=3+9+4=16
tr(A)=A11+A22+A33=3+9+4=16
（3）性质
t
r
(
A
+
B
)
=
t
r
(
A
)
+
t
r
(
B
)
t
r
(
k
∗
A
)
=
k
∗
t
r
(
A
)
,
k
为常数
t
r
(
A
)
=
t
r
(
A
T
)
t
r
(
A
B
)
=
t
r
(
B
A
)
tr(A+B)=tr(A)+tr(B)\\ tr(k*A)=k*tr(A),k为常数\\ tr(A)=tr(A^T)\\ tr(AB)=tr(BA)
tr(A+B)=tr(A)+tr(B)tr(k∗A)=k∗tr(A),k为常数tr(A)=tr(AT)tr(AB)=tr(BA)
其中，前3个性质显然成立，同时求解模块度计算公式的矩阵形式时会用到
t
r
(
A
B
)
=
t
r
(
B
A
)
tr(AB)=tr(BA)
tr(AB)=tr(BA)，证明过程见2.3。
2.3、矩阵迹交换律证明
已知 A A A为 N ∗ M N*M N∗M的矩阵， B B B为 M ∗ N M*N M∗N的矩阵，求证 t r ( A B ) = t r ( B A ) tr(AB)=tr(BA) tr(AB)=tr(BA)
证明：
C
=
A
B
,
C
为
N
∗
N
的矩阵
其中，
C
i
j
=
∑
k
=
1
M
A
i
k
B
k
j
则，
t
r
(
C
)
=
C
11
+
C
22
+
.
.
.
+
C
N
N
=
∑
i
=
1
N
∑
k
=
1
M
A
i
k
B
k
i
其中
,
C
11
=
A
11
∗
B
11
+
A
12
∗
B
21
+
A
13
∗
B
31
+
.
.
.
+
A
1
M
∗
B
M
1
C
22
=
A
21
∗
B
12
+
A
22
∗
B
22
+
A
23
∗
B
32
+
.
.
.
+
A
2
M
∗
B
M
2
C
33
=
A
31
∗
B
13
+
A
32
∗
B
23
+
A
33
∗
B
33
+
.
.
.
+
A
3
M
∗
B
M
3
.
.
.
C
N
N
=
A
N
1
∗
B
1
N
+
A
N
2
∗
B
2
N
+
A
N
3
∗
B
3
N
+
.
.
.
+
A
N
M
∗
B
M
N
对以上
N
个式子对应项按列相加，
记
D
11
=
B
11
∗
A
11
+
B
12
∗
A
21
+
B
13
∗
A
31
+
.
.
.
+
B
1
N
∗
A
N
1
=
∑
k
=
1
N
B
1
k
A
k
1
D
22
=
B
21
∗
A
12
+
B
22
∗
A
22
+
B
23
∗
A
32
+
.
.
.
+
B
2
N
∗
A
N
2
=
∑
k
=
1
N
B
2
k
A
k
2
D
33
=
B
31
∗
A
13
+
B
32
∗
A
23
+
B
33
∗
A
33
+
.
.
.
+
B
3
N
∗
A
N
3
=
∑
k
=
1
N
B
3
k
A
k
3
.
.
.
D
M
M
=
B
M
1
∗
A
1
M
+
B
M
2
∗
A
2
M
+
B
M
3
∗
A
3
M
+
.
.
.
+
B
M
N
∗
A
N
M
=
∑
k
=
1
N
B
M
k
A
k
M
则
t
r
(
C
)
=
C
11
+
C
22
+
.
.
.
+
C
N
N
可写作以下形式：
t
r
(
C
)
=
D
11
+
D
22
+
.
.
.
+
D
M
M
=
∑
k
=
1
N
B
1
k
A
k
1
+
∑
k
=
1
N
B
2
k
A
k
2
+
∑
k
=
1
N
B
3
k
A
k
3
+
.
.
.
+
∑
k
=
1
N
B
M
k
A
k
M
=
∑
i
=
1
M
∑
k
=
1
N
B
i
k
A
k
i
=
t
r
(
B
A
)
t
r
(
A
B
)
=
t
r
(
B
A
)
得证
C=AB,C为N*N的矩阵\\ 其中，C_{ij}=\sum_{k=1}^{M}A_{ik}B_{kj}\\ 则，tr(C)=C_{11}+C_{22}+...+C_{NN}=\sum_{i=1}^{N}\sum_{k=1}^{M}A_{ik}B_{ki}\\ 其中,\\ C_{11}=A_{11}*B_{11}+A_{12}*B_{21}+A_{13}*B_{31}+...+A_{1M}*B_{M1}\\ C_{22}=A_{21}*B_{12}+A_{22}*B_{22}+A_{23}*B_{32}+...+A_{2M}*B_{M2}\\ C_{33}=A_{31}*B_{13}+A_{32}*B_{23}+A_{33}*B_{33}+...+A_{3M}*B_{M3}\\ ...\\ C_{NN}=A_{N1}*B_{1N}+A_{N2}*B_{2N}+A_{N3}*B_{3N}+...+A_{NM}*B_{MN}\\ 对以上N个式子对应项按列相加，\\ 记D_{11}=B_{11}*A_{11}+B_{12}*A_{21}+B_{13}*A_{31}+...+B_{1N}*A_{N1}=\sum_{k=1}^{N}B_{1k}A_{k1}\\ D_{22}=B_{21}*A_{12}+B_{22}*A_{22}+B_{23}*A_{32}+...+B_{2N}*A_{N2}=\sum_{k=1}^{N}B_{2k}A_{k2}\\ D_{33}=B_{31}*A_{13}+B_{32}*A_{23}+B_{33}*A_{33}+...+B_{3N}*A_{N3}=\sum_{k=1}^{N}B_{3k}A_{k3}\\ ...\\ D_{MM}=B_{M1}*A_{1M}+B_{M2}*A_{2M}+B_{M3}*A_{3M}+...+B_{MN}*A_{NM}=\sum_{k=1}^{N}B_{Mk}A_{kM}\\ 则tr(C)=C_{11}+C_{22}+...+C_{NN}可写作以下形式：\\ tr(C)=D_{11}+D_{22}+...+D_{MM}=\sum_{k=1}^{N}B_{1k}A_{k1}+\sum_{k=1}^{N}B_{2k}A_{k2}+\sum_{k=1}^{N}B_{3k}A_{k3}+...+\sum_{k=1}^{N}B_{Mk}A_{kM}=\sum_{i=1}^{M}\sum_{k=1}^{N}B_{ik}A_{ki}=tr(BA)\\ tr(AB)=tr(BA)得证
C=AB,C为N∗N的矩阵其中，Cij=k=1∑MAikBkj则，tr(C)=C11+C22+...+CNN=i=1∑Nk=1∑MAikBki其中,C11=A11∗B11+A12∗B21+A13∗B31+...+A1M∗BM1C22=A21∗B12+A22∗B22+A23∗B32+...+A2M∗BM2C33=A31∗B13+A32∗B23+A33∗B33+...+A3M∗BM3...CNN=AN1∗B1N+AN2∗B2N+AN3∗B3N+...+ANM∗BMN对以上N个式子对应项按列相加，记D11=B11∗A11+B12∗A21+B13∗A31+...+B1N∗AN1=k=1∑NB1kAk1D22=B21∗A12+B22∗A22+B23∗A32+...+B2N∗AN2=k=1∑NB2kAk2D33=B31∗A13+B32∗A23+B33∗A33+...+B3N∗AN3=k=1∑NB3kAk3...DMM=BM1∗A1M+BM2∗A2M+BM3∗A3M+...+BMN∗ANM=k=1∑NBMkAkM则tr(C)=C11+C22+...+CNN可写作以下形式：tr(C)=D11+D22+...+DMM=k=1∑NB1kAk1+k=1∑NB2kAk2+k=1∑NB3kAk3+...+k=1∑NBMkAkM=i=1∑Mk=1∑NBikAki=tr(BA)tr(AB)=tr(BA)得证
矩阵迹交换律的证明过程可参考该链接：矩阵迹的交换律以及加和号的交换律 - 鸿羽的文章 - 知乎 https://zhuanlan.zhihu.com/p/452962118
其中该性质似乎可以使用交换求和证明，即 t r ( A B ) = ∑ i = 1 N ∑ k = 1 M A i k B k i = ∑ k = 1 M ∑ i = 1 N B k i A i k = t r ( B A ) tr(AB)=\sum_{i=1}^{N}\sum_{k=1}^{M}A_{ik}B_{ki}=\sum_{k=1}^{M}\sum_{i=1}^{N}B_{ki}A_{ik}=tr(BA) tr(AB)=∑i=1N∑k=1MAikBki=∑k=1M∑i=1NBkiAik=tr(BA)
交换求和的相关内容可参考该链接：恐怖技巧——交换求和 - Westlifer的文章 - 知乎 https://zhuanlan.zhihu.com/p/499839696
三、模块度增量计算
3.1、公式推导
增量公式（子区
i
、
j
i、j
i、j合并的模块度增量）：
Δ
Q
i
j
=
e
i
j
+
e
j
i
−
2
a
i
a
j
\Delta Q_{ij}=e_{ij}+e_{ji}-2a_ia_j
ΔQij=eij+eji−2aiaj
基于模块度计算的公式（形式一）进行推导：
Q = ∑ i ( e i i − a i 2 ) = ∑ i e i i − ∑ i a i 2 Q=\sum_{i}({e_{ii}-a_i^2})=\sum_{i}{e_{ii}}-\sum_{i}{a_i^2} Q=∑i(eii−ai2)=∑ieii−∑iai2
合并前有 R R R个子区，模块度记为 Q = ∑ k = 1 R e k k − ∑ k = 1 R a k 2 Q=\sum_{k=1}^{R}e_{kk}-\sum_{k=1}^{R}{a_k^2} Q=∑k=1Rekk−∑k=1Rak2
合并子区 i 、 j i、j i、j，假设 i < j i<j i<j，则合并后有 R − 1 R-1 R−1个子区（其中第 m m m个子区为合并后的子区），合并后的模块度记为 Q ′ = ∑ k = 1 R − 1 e k k ′ − ∑ k = 1 R − 1 a ′ k 2 Q'=\sum_{k=1}^{R-1}e'_{kk}-\sum_{k=1}^{R-1}{{a'}_k^2} Q′=∑k=1R−1ekk′−∑k=1R−1a′k2
则模块度增量为：
Δ
Q
=
Q
′
−
Q
=
(
∑
k
=
1
R
−
1
e
k
k
′
−
∑
k
=
1
R
e
k
k
)
+
(
∑
k
=
1
R
−
1
a
′
k
2
−
∑
k
=
1
R
a
k
2
)
\Delta{Q}=Q'-Q=(\sum_{k=1}^{R-1}e'_{kk}-\sum_{k=1}^{R}e_{kk})+(\sum_{k=1}^{R-1}{{a'}_k^2}-\sum_{k=1}^{R}{a_k^2})
ΔQ=Q′−Q=(k=1∑R−1ekk′−k=1∑Rekk)+(k=1∑R−1a′k2−k=1∑Rak2)
- 计算 ∑ k = 1 R − 1 e k k ′ − ∑ k = 1 R e k k \sum_{k=1}^{R-1}e'_{kk}-\sum_{k=1}^{R}e_{kk} ∑k=1R−1ekk′−∑k=1Rekk
∑ k = 1 R − 1 e k k ′ = ∑ k ≠ m e k k ′ + e m m ′ 其中， e m m ′ = e i i + e j j + e i j + e j i 则， ∑ k = 1 R − 1 e k k ′ = ∑ k = 1 R e k k + e i j + e j i ∑ k = 1 R − 1 e k k ′ − ∑ k = 1 R e k k = e i j + e j i \sum_{k=1}^{R-1}e'_{kk}=\sum_{k\neq{m}}e'_{kk}+e'_{mm}\\ 其中，e'_{mm}=e_{ii}+e_{jj}+e_{ij}+e_{ji}\\ 则，\sum_{k=1}^{R-1}e'_{kk}=\sum_{k=1}^{R}e_{kk}+e_{ij}+e_{ji}\\ \sum_{k=1}^{R-1}e'_{kk}-\sum_{k=1}^{R}e_{kk}=e_{ij}+e_{ji} k=1∑R−1ekk′=k=m∑ekk′+emm′其中，emm′=eii+ejj+eij+eji则，k=1∑R−1ekk′=k=1∑Rekk+eij+ejik=1∑R−1ekk′−k=1∑Rekk=eij+eji
- 计算 ∑ k = 1 R − 1 a ′ k 2 − ∑ k = 1 R a k 2 \sum_{k=1}^{R-1}{{a'}_k^2}-\sum_{k=1}^{R}{a_k^2} ∑k=1R−1a′k2−∑k=1Rak2
∑ k = 1 R − 1 a ′ k 2 = ∑ k ≠ m a ′ k 2 + a ′ m 2 其中， a ′ 1 2 = ( e 11 + e 12 + . . . + e 1 m + . . . + e 1 ( R − 1 ) ) 2 其中， e 1 m = e 1 i + e 1 j 则， a ′ 1 2 = ( e 11 + e 12 + . . . + e 1 i + . . . + e 1 j + . . . + e 1 ( R − 1 ) ) 2 = a 1 2 ∑ k ≠ m R − 1 a ′ k 2 = ∑ k ≠ i , j R a k 2 此外， a ′ m 2 = ( e m 1 + e m 2 + . . . + e m m + . . . + e m ( R − 1 ) ) 2 = [ ( e i 1 + e i 2 + . . . + e i i + . . . + e i j + . . . + e i ( R − 1 ) ) + ( e j 1 + e j 2 + . . . + e j i + . . . + e j j + . . . + e j ( R − 1 ) ) ] 2 = a i 2 + a j 2 + 2 ∗ a i ∗ a j 则， ∑ k = 1 R − 1 a ′ k 2 = ∑ k ≠ m a ′ k 2 + a ′ m 2 = ∑ k R a k 2 + 2 ∗ a i ∗ a j ∑ k = 1 R − 1 a ′ k 2 − ∑ k = 1 R a k 2 = 2 ∗ a i ∗ a j \sum_{k=1}^{R-1}{{a'}_k^2}=\sum_{k\neq{m}}{a'}_k^2+{a'}_m^2\\ 其中，{a'}_1^2=(e_{11}+e_{12}+...+e_{1m}+...+e_{1(R-1)})^2\\ 其中，e_{1m}=e_{1i}+e_{1j}\\ 则，{a'}_1^2=(e_{11}+e_{12}+...+e_{1i}+...+e_{1j}+...+e_{1(R-1)})^2=a_1^2\\ \sum_{k\neq{m}}^{R-1}{a'}_k^2=\sum_{k\neq{i,j}}^{R}{a}_k^2\\ 此外，{a'}_m^2=(e_{m1}+e_{m2}+...+e_{mm}+...+e_{m(R-1)})^2=\\ [(e_{i1}+e_{i2}+...+e_{ii}+...+e_{ij}+...+e_{i(R-1)})+(e_{j1}+e_{j2}+...+e_{ji}+...+e_{jj}+...+e_{j(R-1)})]^2=\\ a_i^2+a_j^2+2*a_i*a_j\\ 则，\sum_{k=1}^{R-1}{{a'}_k^2}=\sum_{k\neq{m}}{a'}_k^2+{a'}_m^2=\sum_{k}^{R}a_k^2+2*a_i*a_j\\ \sum_{k=1}^{R-1}{{a'}_k^2}-\sum_{k=1}^{R}{a_k^2}=2*a_i*a_j k=1∑R−1a′k2=k=m∑a′k2+a′m2其中，a′12=(e11+e12+...+e1m+...+e1(R−1))2其中，e1m=e1i+e1j则，a′12=(e11+e12+...+e1i+...+e1j+...+e1(R−1))2=a12k=m∑R−1a′k2=k=i,j∑Rak2此外，a′m2=(em1+em2+...+emm+...+em(R−1))2=[(ei1+ei2+...+eii+...+eij+...+ei(R−1))+(ej1+ej2+...+eji+...+ejj+...+ej(R−1))]2=ai2+aj2+2∗ai∗aj则，k=1∑R−1a′k2=k=m∑a′k2+a′m2=k∑Rak2+2∗ai∗ajk=1∑R−1a′k2−k=1∑Rak2=2∗ai∗aj
- 计算 Δ Q \Delta{Q} ΔQ
Δ Q = Q ′ − Q = ( ∑ k = 1 R − 1 e k k ′ − ∑ k = 1 R e k k ) + ( ∑ k = 1 R − 1 a ′ k 2 − ∑ k = 1 R a k 2 ) = e i j + e j i − 2 ∗ a i ∗ a j 其中， e i j = e j i 则， Δ Q = 2 ∗ ( e i j − a i ∗ a j ) \Delta Q=Q'-Q=(\sum_{k=1}^{R-1}e'_{kk}-\sum_{k=1}^{R}e_{kk})+(\sum_{k=1}^{R-1}{{a'}_k^2}-\sum_{k=1}^{R}{a_k^2})=e_{ij}+e_{ji}-2*a_i*a_j\\ 其中，e_{ij}=e_{ji}\\ 则，\Delta Q=2*(e_{ij}-a_i*a_j) ΔQ=Q′−Q=(k=1∑R−1ekk′−k=1∑Rekk)+(k=1∑R−1a′k2−k=1∑Rak2)=eij+eji−2∗ai∗aj其中，eij=eji则，ΔQ=2∗(eij−ai∗aj)
3.2、社区合并示例
合并前：3个子区，模块度 Q Q Q为 − 1 / 24 -1/24 −1/24
合并后：2个子区，模块度 Q ′ = 2 / 6 + 1 / 6 − ( 7 / 12 ) 2 − ( 5 / 12 ) 2 = − 1 / 72 Q'=2/6+1/6-(7/12)^2-(5/12)^2=-1/72 Q′=2/6+1/6−(7/12)2−(5/12)2=−1/72
| 节点 | I | II | a i a_i ai |
|---|---|---|---|
| I | 2/6 | 3/12 | 7/12 |
| II | 3/12 | 1/6 | 5/12 |
模块度增量： Δ Q = Q ′ − Q = − 1 / 72 − ( − 1 / 24 ) = 1 / 36 \Delta Q=Q'-Q=-1/72-(-1/24)=1/36 ΔQ=Q′−Q=−1/72−(−1/24)=1/36
按照公式计算： Δ Q = 2 ( e 12 − a 1 ∗ a 2 ) = 2 ( 1 / 12 − 2 / 12 ∗ 1 / 12 ) = 1 / 36 \Delta Q=2(e_{12}-a_1*a_2)=2(1/12-2/12*1/12)=1/36 ΔQ=2(e12−a1∗a2)=2(1/12−2/12∗1/12)=1/36
四、相关链接
论文：
https://arxiv.org/pdf/cond-mat/0309508.pdf
http://www.pnas.org/content/103/23/8577.full.pdf
模块度计算相关：
Modularity的计算方法——社团检测中模块度计算公式详解 | 雅乐网 (yalewoo.com)
矩阵迹的交换律：
以及加和号的交换律 - 鸿羽的文章 - 知乎 https://zhuanlan.zhihu.com/p/452962118
瓜分20万奖金 获得内推名额 丰厚实物奖励 易参与易上手
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)