社团发现一只是复杂网络研究中一个比较火热的话题，本文根据国防科大骆志刚教授的论文 [1]整理的，主要是对社区发现的一些算法进行简单分析。
一、模块度优化类。
优化模块度值的一部分算法。值是由Newman在2004年的论文[2] 中提出的(也就是FN算法)，通过优化Q值来提高模块度是这类算法的主要思路，在此基础上，本文又划分了三个类别：
- 聚合思想，也就是分层聚类中的自底向上的作法。典型算法有Newman快速算法(FN算法)、CNM算法[3]和MSG-MV算法 [4] 等。
- 分裂思想，也就是分层聚类中自顶向下的方法。代表当然就是Newman的GN算法，但是GN的复杂度实在是高了些（\(O(NM^2)\)），所以Newman之后提出的一种谱方法[5].
- 直接寻优法，代表算法EO[6] 和整数规划方法，但是一些基于遗传算法和蚁群的智能划分方法也属于此类。但是在2007年的论文 [7]中认为基于Q值的优化方法无法处理粒度小于一定程度的网络，虽然后续跟进了一些优化的算法，但是此类方法在处理真实网络时还是很难反映真实的社团结构。Louvain算法 [20]是目前业界widely used的算法，效果稳定，复杂度（\(O(n log(n))\)）也是可接受。
二、基于谱分析的社团发现算法。
这类算法的普遍方法是将节点对应的矩阵特征分量看成空间坐标，将网络节点映射到多维向量空间去，运用传统的聚类算法将它们聚集成社团。这种方法不可避免的要计算矩阵的特征值，开销很大，但是因为能直接使用很多传统的向量聚类的成果，灵活性很高。
三、基于信息论的社团发现算法。
Rosvall的两篇论文，[8]和 [9]分别运用了模拟退火优化算法和随机游走的有效编码方式。09年的论文 [10]已经测试表明该方法是目前非重叠社团发现算法中准确度最高的。
四、基于标签传播的社团发现算法。
Raghavan基于网络的边很多时候代表信息的传播这一思想提出的LPA算法 [11]。LPA算法首先为每个节点指派唯一标号， 在每一步迭代中, 每个节点将自身标号更新为其邻节点出现次数最多的标号，如果存在多个相同的最多标号， 则随机选择一个作为更新值，若干次迭代后密集相连的节点会收敛于同一标号，最终，具有相同标号的节点归为一个社团。该算法时间复杂度为，收敛速度非常快，但是算法存在随机过程，所以每次运行的结果并不稳定。目前有很多针对LPA算法进行改进的工作，如 文献[12] 中改进了标号更新规则，进一步降低了计算开销。
对于非重叠社团的划分算法已经相对成熟，但是真实世界的网络和这种理想状态相去甚远，经常有某些节点同时具有多个社区的特性，属于多个社区，在这种状况之下，对于重叠社区的划分明显更有意义更贴近真实世界，也因此成为近年来新的研究热点。相应的，本文将重叠社区划分算法分为以下几类：
一、基于团渗透改进的重叠社区发现算法。
Palla的论文 [13] 中提出的CPM算法是第一个能发现重叠社区的算法，CPM算法就不展开讨论了，如果是研究重叠社区发现算法的话肯定是看过的。值得一提的是Kumpula在前人基础上提出的SCP算法 [14] 较大的提升了团渗透算法的速度。该类算法的问题这篇文章虽然也是简单的一说，但是比之前某些人简单的用一个K值不好确定来敷衍了事要来的有意义的多：基于团渗透思想的算法需要以团为基本单元来发现重叠，这对于很多真实网络尤其是稀疏网络而言，限制条件过于严格，只能发现少量的重叠社团[15]。
二、基于种子扩散思想的重叠社区发现算法。
此类算法的基本思想是以具有某种特征的子网络为种子，通过合并、扩展等操作向邻接节点扩展，直至获得评价函数最大的社团。Lancichinetti 等提出以若干个节点为种子，通过扩展形成对整个网络的覆盖， 即LMF算法 [16]。
三、基于混合概率模型的重叠社区发现。
前述的很多算法都是自己给出了社团结构的定义然后相应给出算法，但这样的划分必须对社团先做出符合结构定义的假设。针对此问题，Newman等建立了社团结构的混合概率模型 [17]，以概率方法对复杂网络的社团结构进行探索，以求得期望最大的社团结构，从而避开社团定义的问题。通过该算法能够识别重叠社团，并得到隶属程度大小。然而，该方法基于EM算法来估计未知参数，收敛速度较慢，计算复杂度较高, 一定程度上制约了算法的应用规模。
四、基于边聚类的重叠社团发现。
这类方法以边为研究对象，推荐两篇论文：[18]和[19].前者通过转换网络，可以用非重叠社区的方法提示网络的重叠社团，后者解决重叠性与层次性冲突，提出了变社团。遗憾的是，文章没有介绍动态变化的复杂网络。
参考文献：
- 骆志刚, 丁凡, 蒋晓舟, et al. 复杂网络社团发现算法研究新进展[J]. 国防科技大学学报, 2011, 33(1):47-52.
- Newman M E J . Fast algorithm for detecting community structure in networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2003, 69(6 Pt 2):066133.
- Clauset, Aaron. Finding local community structure in networks[J]. Physical Review E, 2005, 72(2):026132.
- Schuetz P , Caflisch A . Multistep greedy algorithm identifies community structure in real-world and computer-generated networks[J]. Physical Review E, 2008, 78(2):026112.
- NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577–8582.
- Duch J , Arenas A . Community detection in complex networks using Extremal Optimization[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2005, 72(2):027104.
- Fortunato S , Barthelemy M . Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1):36-41.
- Rosvall M , Bergstrom C T . An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(18):7327-7331.
- Rosvall M , Bergstrom C T . Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4):1118-1123.
- Lancichinetti A , Fortunato S . Community detection algorithms: A comparative analysis[J]. Physical Review E, 2009, 80(5):056117.
- Raghavan U N , Albert, Réka, Kumara S . Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
- Leung I X Y , Hui P , Lio' P , et al. Towards real-time community detection in large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 79(2):066107.
- Palla G, Derenyi I, Farkas I J, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
- Kumpula J M , Kivela M , Kaski K . A sequential algorithm for fast clique percolation[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):026109.
- Zhang S , Ning X , Zhang X S . Identification of functional modules in a PPI network by clique percolation clustering[J]. Computational Biology and Chemistry, 2006, 30(6):445-451.
- Lancichinetti A , Fortunato S , Kertész, János. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3):033015.
- Newman M E J , Leicht E A . Mixture models and exploratory analysis in networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(23):9564-9569.
- Evans T S , Lambiotte R . Line graphs, link partitions, and overlapping communities[J]. Physical Review E, 2009, 80(1):016105.
- Ahn Y Y , Bagrow J P , Lehmann S . Link communities reveal multiscale complexity in networks[J]. NATURE, 2010, 466(7307):761-764.
- BLONDEL V D, GUILLAUME J-L, LAMBIOTTE R, 等. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.