自然界中的很多系统都可以表示为复杂网络的形式,即将自然界中的各个实体抽象为网络中的节点,实体与实体之间的关系抽象为网络中的边。复杂网络已经成为一个立足于交叉学科的研究热点。大量研究表明,复杂网络中的节点具有聚集化的特性,即复杂网络的社区结构特征,表现为社区内部节点之间连接稠密,社区之间的节点连接相对稀疏。社区结构有助于理解网络的拓扑结构及功能结构,发现其中隐藏的规律并预测其行为,从而为利用和改造网络提供指导,是进行复杂网络分析的基础和关键,具有极为重要的意义。社区结构在现实世界中往往是“重叠”的,即社区与社区之间有交叉,许多节点同时属于多个社区。复杂网络重叠社区结构更加贴近现实世界的本来面貌,例如,社会的人通常属于多个社会团体,包括家人团体、同事团体、朋友团体和合作伙伴团体等。研究和发现复杂网络中的重叠社区结构具有重要的理论和现实意义。本课题主要围绕复杂网络中的节点重要性计算、重叠节点选择、局部社区扩展以及属性网络社区发现等四个方面存在的问题进行研究,主要包括以下几个方面的内容:1.为了得到稳定的社区发现结果,提出一种基于节点影响值的稳定标签传播算法。该算法以节点影响值降序排列作为每次标签传播过程中节点的顺序,在标签更新过程中,引入标签影响强度的概念,使得每次更新都能得到确定的标签。通过节点影响值和标签影响强度的计算,避免了原算法中的随机因素,不仅能得到稳定的社区发现结果,并且算法的性能优于其他几种代表性的社区发现算法。2.为了在已知非重叠社区结构的基础上继续挖掘,得到重叠社区结构,提高重叠社区发现的效率,提出一种基于非重叠社区结构扩展的重叠社区发现算法。该算法通过计算节点与社区的相似度,划定各个社区的潜在成员节点范围,然后根据节点对社区的影响力,确定最终的重叠节点。该算法能够有效的利用已有的非重叠社区结构,通过潜在成员节点的划定,进一步缩小了重叠节点查找的范围,提高了算法的效率,并且得到的重叠节点的质量也很高。3.针对基于网络全局的社区发现算法时间开销较大,不适用于大规模网络的问题,提出一种基于局部扩展的社区发现算法。该算法通过对网络的局部信息进行分析,挖掘出每条边对应的两个端点及其公共邻接点组成的局部社区,然后对重叠度高的社区进行合并,每次分析只考虑相邻节点或相邻社区的关系,缩小了计算范围,能够适应于大规模网络的社区发现。4.大多数现有的社区发现算法只利用网络的拓扑结构信息,忽略了节点属性这一重要信息,为此,提出一种基于节点耦合相似度的属性网络社区发现算法。该算法充分考虑不同层次的复杂的交互关系,计算节点耦合相似度,然后以两节点的相似度作为对应边的权重,最后利用带权网络社区发现算法得到网络的社区结构。该算法有效利用了网络中的节点属性信息和拓扑结构信息,提高了社区发现的质量。最后,在模拟和真实网络数据集上进行了实验,分别与同类算法中具有代表性的社区发现算法进行比较,实验结果印证了本文所提算法的有效性。