现实生活中,绝大多数的复杂系统都可以抽象成复杂网络,如生物蛋白质网络、社交网络、无线传感器网络、流行病传播网络等等。学者多年来研究发现,真实网络除了有无标度性质、小世界特征和局部聚集特征外,还具有社区结构特征。社区内部连接密切,社区之间连接稀疏。组成社区的节点通常功能相近或性质相似,因此社区被认为有助于揭示网络结构和功能之间的关系。网络中有些节点可能属于多个社区,于是产生了重叠社区。重叠社区是不同社区之间的纽带,能够更真实地反映网络结构,研究重叠社区具有重要意义。现有社区发现算法的结果和效率都很好,但没有哪个是十分完美的。例如大部分社区发现算法尝试从整个网络角度进行划分,但是基本上所有的真实网络都是无标度的,即大部分节点连接稀疏,这在某种程度上会干扰找到真正的社区;有的算法能够划分一般性的社区结构,却不能识别重叠社区;有的算法对重叠和非重叠社区划分效果都很好,却不适用于大规模的网络等。本文主要对复杂网络中重叠社区发现算法进行研究,分为发现密集社区和大部分社区两方面。根据社区内部节点连接密切,社区之间连接稀疏这个特点,把社区发现问题转化为在图中发现密集子图的问题,提出基于总密度最大的k个有限重叠社区的发现算法,即子图间允许有限重叠,节点集合间Jaccard系数满足给定上限的情况下找到密度总和最大的k个密集子图。提出最小密集子图的概念,设计了最小密集子图的发现算法,并据此提出了重叠社区发现算法MainDS(G,k,?)和FastDS(G,k,?)。为了考查大部分社区,本文提出一种基于图熵聚类的重叠社区发现算法。借鉴信息论中熵的概念,引入图熵作为社区的模块度检验标准。图熵是对聚类节点的内连接和外连接状况的刻画,图熵越低表示图中模块度越高,通过最小化图熵的值进行聚类可以搜索局部最优社区。本质上讲这种算法是一种自底向上的种子生长式算法,种子的选择本文提供随机选择、基于度和基于聚类系数三种解决方案。算法的初始设置种子集,每个种子的生长都是独立的,一个节点可以参与多个种子的生长,使重叠社区的生成成为可能。最后通过实验证明了本文提出算法的有效性。