社团结构是复杂网络的重要特征之一,在同一个社团内的顶点之间连接紧密,而不同社团之间连接相对稀疏。社团结构通常与网络中潜在的功能和组织特征联系在一起,例如新陈代谢网络中的生化过程,科学家合著网络中科学家的研究领域,WWW网络中具有相同主题的网页组或社交网络中真实的社会群体等等。社团检测对于理解与改善不同类型的复杂系统具有重要意义。此外,社团结构可以从结构层面展示网络的不同性质,并描述网络的结构和功能或组织结构之间的关系。因此,社团检测具有重要的理论意义和实践应用价值,受到研究人员的广泛关注,并提出了大量的社团检测算法。本文在对现有的社团检测算法进行了深入研究的基础上,提出了一种基于等价类的非重叠社团检测方法DEC(Disjoint community detection via Equivalence Classes)和一种基于等价类的重叠社团检测方法OEC(Overlapping community detection via Equivalence Classes)。(1)基于等价类的非重叠社团检测方法DEC:该方法是基于顶点的等价类而提出的确定性的非重叠社团检测方法。DEC方法首先为网络中的每一个顶点构建一个连接模式向量,从而构造出整个网络中顶点所对应的连接模式矩阵;然后通过指定约束条件,选择出网络中所有满足约束条件的顶点对,紧接着利用这个顶点对集合构造出网络中满足约束条件的顶点的一个等价类划分,即网络的一个初始社团结构;最后通过对其中一些顶点和小社团进行微调以获得网络最终的非重叠社团结构划分。(2)基于等价类的重叠社团检测方法OEC:该方法首先为网络中的每一个顶点构建一个连接模式向量,然后通过顶点的连接模式矩阵为网络中的每条连边构造一个边连接模式向量;进而通过约束条件选择出网络中所有满足约束条件的边对,并利用边对集合构建满足约束条件的边对所构成的一个等价类划分,再将该划分转化为网络中顶点所构成的一个初始覆盖,即一个初始的重叠社团结构;最后通过对其中一些顶点进行微调获得最终的重叠社团结构。为了验证本文所提社团检测方法的有效性,本文在人工合成网络与实际网络数据集上进行了实验,并与多个算法的实验结果进行对比分析。实验结果表明,本文中所提出的算法能够有效且稳定地从网络中提取高质量的社团结构。