社团发现一只是复杂网络研究中一个比较火热的话题,本文根据国防科大骆志刚教授的论文 [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.