# 网络模块化

Modularity（模块化）是network（网络）或graph（图形）结构的一种度量，用于衡量网络划分为模块（也称为组，集群或社团）的强度。具有高模块化的网络在模块内的节点之间具有密集连接，但在不同模块的节点之间具有稀疏连接。在检测网络中community structure（社团结构）的优化方法中常使用模块化。但是，模块化受到分辨率限制，因此无法检测小社团。生物网络，包括动物的大脑，具有高度的模块化。

## 定义

$\displaystyle{ l_{n}= \sum_{v} k_{v} =2m. \qquad(1) }$

$\displaystyle{ \text{Expectation of full edges between }v \text{ and }w =\frac{\text{ (Full edges between }v\text{ and }w\text{)}}{ \text{(Total number of rewiring possibilities)}}. \qquad(2) }$

$\displaystyle{ \text{Expected number of full edges between }v\text{ and }w = \frac{k_v k_w}{l_n} = \frac{k_v k_w}{2m} }$

$\displaystyle{ A_{vw} - \frac{k_v k_w}{2m} }$

$\displaystyle{ Q = \frac{1}{2m} \sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{2m} \right] \frac{s_{v} s_{w}+1}{2}. \qquad(3) }$

$\displaystyle{ Q = \frac{1}{(2m)}\sum_{vw} \left[ A_{vw} - \frac{k_v k_w}{(2m)} \right] \delta(c_{v}, c_{w}) =\sum_{i=1}^{c} (e_{ii}-a_{i}^2). \qquad(4) }$

$\displaystyle{ e_{ij}= \sum_{vw} \frac{A_{vw}}{2m} 1_{v\in c_i} 1_{w\in c_j} }$

ai是连接到社团i中的顶点的边的末端分数：

$\displaystyle{ a_i=\frac{k_i}{2m} = \sum_{j} e_{ij} }$

## 多社团检测实例

1 0 1 1 0 0 0 0 0 0 1
2 1 0 1 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0
4 0 0 0 0 1 1 0 0 0 1
5 0 0 0 1 0 1 0 0 0 0
6 0 0 0 1 1 0 0 0 0 0
7 0 0 0 0 0 0 0 1 1 1
8 0 0 0 0 0 0 1 0 1 0
9 0 0 0 0 0 0 1 1 0 0
10 1 0 0 1 0 0 1 0 0 0

## 矩阵表述

$\displaystyle{ \delta(c_v,c_w) = \sum_r S_{vr} S_{wr} }$

$\displaystyle{ Q = \frac{1}{2m} \sum_{vw} \sum_r \left[ A_{vw} - \frac{k_v k_w}{2m} \right] S_{vr} S_{wr} = \frac{1}{2m} \mathrm{Tr}(\mathbf{S}^\mathrm{T}\mathbf{BS}), }$

$\displaystyle{ B_{vw} = A_{vw} - \frac{k_v k_w}{2m}. }$

$\displaystyle{ Q = {1\over 4m} \sum_{vw} B_{vw} s_v s_w = {1\over 4m} \mathbf{s}^\mathrm{T}\mathbf{Bs}, }$

## 参考文献

1. Newman, M. E. J. (2006). "Modularity and community structure in networks". Proceedings of the National Academy of Sciences of the United States of America. 103 (23): 8577–8696. arXiv: physics/0602124  .Bibcode:2006PNAS..103.8577N. doi:10.1073/pnas.0601602103. PMC 1482622 . PMID 16723398.
2. Newman, M. E. J. (2007). Palgrave Macmillan, Basingstoke, eds. "Mathematics of networks". The New Palgrave Encyclopedia of Economics (2 ed.).
3. Li, Wenye; Schuurmans, Dale (2011). "Modular Community Detection in Networks". IJCAI Proceedings-International Joint Conference on Artificial Intelligence. 22 (1): 2. doi:10.5591/978-1-57735-516-8/IJCAI11-231.
4. van der Hofstad, Remco (2013). "Chapter 7". Random Graphs and Complex Networks (PDF).
5. Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher (2004). "Finding community structure in very large networks". Phys. Rev. E. 70 (6): 066111. arXiv: cond-mat/0408187 . Bibcode: 2004PhRvE..70f6111C. doi:10.1103/PhysRevE.70.066111.
6. Joerg Reichardt & Stefan Bornholdt (2006). "Statistical mechanics of community detection". Physical Review E. 74 (1): 016110. arXiv:cond-mat/0603718. Bibcode: 2006PhRvE..74a6110R.doi:10.1103/PhysRevE.74.016110.
7. Santo Fortunato & Marc Barthelemy (2007). "Resolution limit in community detection". Proceedings of the National Academy of Sciences of the United States of America. 104 (1): 36–41. arXiv:physics/0607100. Bibcode: 2007PNAS..104...36F.doi:10.1073/pnas.0605965104. PMC 1765466. PMID 17190818.
8. J.M. Kumpula; J. Saramäki; K. Kaski & J. Kertész (2007). "Limited resolution in complex network community detection with Potts model approach". European Physical Journal B. 56 (1): 41–45. arXiv:cond-mat/0610370. Bibcode: 2007EPJB...56...41K.doi:10.1140/epjb/e2007-00088-4.
9. Alex Arenas, Alberto Fernández and Sergio Gómez (2008). "Analysis of the structure of complex networks at different resolution levels". New Journal of Physics. 10 (5): 053039. arXiv:physics/0703218. Bibcode: 2008NJPh...10e3039A.doi:10.1088/1367-2630/10/5/053039.
10. Andrea Lancichinetti & Santo Fortunato (2011). "Limits of modularity maximization in community detection". Physical Review E. 84: 066122. arXiv:1107.1155. Bibcode: 2011PhRvE..84f6122L.doi:10.1103/PhysRevE.84.066122.