随着互联网科技的飞速发展,各种社交网站和社交新媒体迅速普及,对社交网络的分析日益受到人们重视。作为社交网络分析的一个重要手段,社区发现近年来一直是一个热门研究领域。传统的社区发现方法大多是非重叠的社区发现,同时也只是针对网络中的单一类型关系进行研究。而现实社交网络的社区结构具有重叠性,一个人可能会属于多个社区。人与人之间也往往存在着多种类型的交流关系,只考虑其中一种关系进行社区发现很可能会因为信息不充分造成发现结果不准确。本文分别对单关系社交网络的重叠社区发现和多关系社交网络的非重叠社区发现做了以下三个方面的工作:1.传统的基于种子扩张的重叠社区发现算法在选取种子节点后直接通过贪婪扩张进行社区发现,其通常不能保证所选种子节点的中心性,同时直接贪婪扩张很可能因首次扩张方向失误造成后续扩张全部出错。本文针对上述两个缺陷,提出了一种新的基于种子节点扩张的重叠社区发现方法OSE。首先,OSE在进行社区发现前引入了随机游走对网络进行预处理来降低网络噪音对社区发现结果准确性的影响。其次结合快速密度峰值聚类计算网络中各节点中心值,并据此进行种子节点选取来确保所选节点的中心性。最后通过计算平均相似度,选取一部分邻节点加入种子节点构成一个中心区域后再进行贪婪扩张,以避免直接贪婪扩张的缺陷。实验结果表明,本方法相对于一些传统的方法,在准确性和抗噪音能力上都有了一定的提升。2.借鉴上述种子扩张思想,本文提出一种基于种子社区扩张的多关系社交网络社区发现方法Multi-SC。Multi-SC首先通过综合网络中各类关系的社区划分信息,选择在所有关系中均处于同一社区的个体组成种子社区集,从中选取包含节点数目最大的社区作为种子社区。之后考虑到网络中两个节点被划分在同一社区的关系数目和公共邻节点间的联系紧密度对二者相似性的影响,对杰卡德相似度函数进行了改进,提出了一个多关系网络中节点相似度计算方法,并以此来计算社区相似度。最后结合改进的相似度函数和一种局部适应度函数完成种子社区的扩张。实验结果表明Multi-SC方法能有效的进行多关系社区发现,并且在中低噪音环境下相对一些现有方法准确率有所提升。3.现有的多关系社交网络社区划分方法大都没有考虑各社交关系之间的差异,在有些社交关系噪音比较大的情况下,会造成综合多种关系进行社区发现反而不如只考虑单个关系的结果准确。针对此问题,本文提出了一种基于多目标进化的多关系社交网络社区发现方法Multi-MOE。方法主要思路是给予各关系不同权重值来反映每个关系在社区划分中的重要性。首先基于模块密度函数D和标准化互信息函数NMI建立目标函数,其次将网络中各种关系的权重作为目标函数的决策变量,通过多目标遗传算法对目标函数进行优化获得各关系的最优权重配比,并据此将多关系网络融合成一个既能有效地综合各种关系社区信息又能同时降低各关系噪音引入的单关系网络,最后通过传统单关系社区发现算法BGLL来对该融合网络进行社区发现。实验表明,相比现有的某些多关系社区发现方法,Multi-MOE提高了社区发现结果的准确性和稳定性。特别是在各关系所含噪音差距比较大的情况下,依然能保持较高的准确性。