现实世界中的很多事物都是以网络形态存在的,例如在线社交,人际关系,人体蛋白质模型等。随着人们对复杂网络研究的深入,社区结构作为复杂网络中的一个重要特性被逐渐重视起来。社区能够有效地反应网络中节点之间的关系,对于复杂网络中社区结构的研究有助于人们更加深入的了解网络系统的结构特性及其演化规律,以便人们更好的改善现实生活。这也正是近年来社区发现问题成为复杂网络领域研究热点的原因。而重叠社区的发现可以更为准确的理解网络内部的拓扑结构信息,在近些年的研究中得到了越来越多的关注。针对重叠社区的发现问题,目前已出现了许多研究成果,总体上可以分为全局优化和局部优化两大类。基于全局优化的社区发现方法主要从全局的角度划分整个网络,需要整个网络结构信息,目前主要包括图划分、层次聚类、模块度优化、谱聚类及基于模型的方法等。基于局部扩展的方法一般根据定义的社区局部度量,从给定的初始节点逐步合并引起最大的社区度量增量的近邻节点,如局部扩展优化、标签传播、派系过滤、局部边聚类优化等,并在社交网络分析中有广泛的应用。本文围绕局部拓展优化中的代表算法LFM,针对其在社区划分过程中存在的划分速度较慢和结果不够稳定两大问题开展研究,提出针对性的解决方案。本文主要研究工作包括如下:首先,针对LFM算法划分速度较慢的情况,提出了一种基于“核心区域”的改进LFM算法,在改进算法中提出了“核心区域”的概念,并论证在社区的拓展阶段,如果一个邻接点属于该节点的核心区域则可以不必再次重复计算适应度函数值,从而减少计算时间,达到提高社区划分速度的目的。其次,针对LFM算法得到的社区划分结果不够稳定的问题,提出了一种基于种子节点筛选的改进LFM算法。主要思路是:借鉴GCE算法和CPM算法的思想,在算法开始时选择较为优质的节点作为种子节点即对初始的种子节点进行筛选。具体做法是:引入临节点度阈值k,对于邻接点度达不到阈值的节点不会被加入种子节点库,从而对达到筛选优质节点作为种子节点的目的,进而优化社区划分结果。最后,对上述提出的两种改进算法,分别在真实网络数据集和人工合成网络数据集中进行实验验证。对于真实网络数据集,我们选取的是认同度较高的Zachary’s karate club,American College football,Dolphin social network等五组公开数据集,使用模块度函数作为评价指标。人工合成网络数据集则是采用LFR基准程序进行构造,使用NMI作为评价指标。同时与LFM算法,CPM算法及Copra算法进行比较。实验结果显示,本文提出的改进算法能够提高社区划分速度,并提升划分结果的稳定性。