复杂网络是对复杂系统的一种抽象描述。复杂系统中包含大量的实体,实体可抽象为节点,实体之间的相互关系可抽象为边。例如通过社交系统中的用户及用户间的关系可抽象出社交网络,通过城市道路系统中的路段及路段之间的关系可抽象出城市道路网络。通过研究发现,社团结构是这些网络的主要特征之一。社团由其内部连接紧密、社团间稀疏互连的节点组成,它往往与实际系统中的功能模块相对应。因而,提取网络中的社团可以为理解网络的功能和结构关系提供一种有效的方式。然而某些网络中的社团结构未知,需要通过合适的社团检测算法进行检测,进而对系统的组成部分与系统的功能进行深入的理解。研究人员利用不同的方法提取社团结构,本文也分别基于SOM(Self-Organizing Map,自组织映射网络)和GSA(Gravitational Search Algorithm,引力搜索算法)提出两种社团检测方法。(1)基于SOM的社团检测方法SOMCD。该方法首先移除度为一的节点;然后利用节点间的邻接关系和相似关系构造属性矩阵,随机选择属性矩阵的若干列作为SOM训练的输入向量;本文接着利用竞争学习的方式获取竞争层中与输入向量最相似的获胜神经元,然后采用不同的方式调整获胜神经元和其它神经元的权重向量。多次迭代后,具有相同获胜神经元的输入向量被映射到同一社团。此外,本文将社团检测过程嵌入上述训练过程,每次训练结束后,计算对应的社团结构的模块度,记录最大模块度对应的社团结构。训练过程结束后,最大的模块度对应的社团结构即为最优的结果;最后用一个后处理过程将移除的节点加入到其邻居所属的社团中,并对一些过小的社团进行合并,从而获得高质量的社团结构。(2)基于GSA的社团检测方法GSACD。该方法首先通过移除对社团结构形成贡献很小的节点进行预处理操作;然后通过多次运行LPA(Label Propagation Algorithm,标签传播算法)以及LPA的改进算法得到多个搜索解,并使用离散化编码方式,将每个搜索解表示为离散的向量,向量中每个维度的值代表搜索解中每个节点对应社团的编号,进而获得初始种群。其中,种群中的每个粒子表示一个社团结构。考虑到社团间和节点间的相似性都对社团结构具有一定的影响,本文据此改写引力计算公式。随着粒子间的引力变化,本文不断更新粒子的质量、加速度及速度,并通过社团结构中每一维对应节点的大多数邻居所属的标签改写粒子的位置更新公式,即更新社团结构中节点所属社团的编号;同时,本文采用模块度作为适应度函数,利用模块度计算粒子的质量;多次迭代后,质量最大的粒子对应的位置为最优的社团结构;最后,该方法通过后处理过程将预处理过程中移除的节点划分到其直接邻居所属的社团中,获得最终的社团结构。本文提出的两种方法都可以自动检测社团数量,并且GSACD方法无需设置任何参数。此外,为了验证SOMCD方法和GSACD方法的有效性,本文分别在不同规模的实际网络及合成网络上进行了实验,并与一些影响力较大的算法获取的结果进行了对比,然后使用模块度和标准化互信息量评价社团结构的优劣。实验结果表明,SOMCD方法和GSACD方法都能检测到高质量的社团结构。