近年来,随着移动互联网技术的飞速发展,越来越多的数据开始以复杂网络的形式呈现在人们面前,人们的生活也处于各种各样的复杂网络之中。因此,如何分析研究隐藏在复杂网络背后的特征规律就成为了学术界和工业界普遍关心的热点问题。随着复杂网络分析技术的进步,复杂网络具有的“小世界”特征、无标度特征和社区结构特征被相继发现。其中,社区结构是复杂网络中最为重要的特征之一。一般而言,社区结构是指社区内部节点之间的连接密度较大,而不同社区之间的节点连接密度较小。识别出隐藏在复杂网络中的社区结构有助于人们了解其内部的功能组织及拓扑结构,进而找出其中潜在的演化规律,为解释一些自然现象提供依据。此外,社区发现结果也可以应用到个性化推荐、链接预测、热点挖掘等领域中。因此,社区发现对复杂网络的研究和应用具有非常重要的理论意义和应用价值。社区发现与局部社区发现是目前对复杂网络的规律及特征进行挖掘分析的主要方法。社区发现是指根据复杂网络中节点的拓扑结构或节点的属性信息将其全部节点划分到不同社区中。因此,社区发现需要复杂网络的全局信息。而局部社区发现是指从给定的一个或多个查询节点出发,只需利用复杂网络的局部信息快速发现查询节点所属的社区结构。由于局部社区发现能够有效摒弃社区发现带来的高昂时空开销且更加符合现实需求,已经受到越来越多的关注。本文主要围绕复杂网络中的社区发现和局部社区发现两个问题分别展开研究,其主要工作和创新点如下:1.在社区发现算法鲁棒性研究方面,针对传统动态距离模型对不同类型复杂网络存在参数选取敏感、容易产生异常节点、以及无法有效区分异常节点及枢纽节点等缺陷,提出了一种基于隶属度的鲁棒动态距离模型及相应的社区发现算法Attractor++。Attractor++算法通过动态隶属度来确定外部邻居节点对距离的正负影响,无需设置凝聚阈值进行干预,极大的提高了传统动态距离模型的鲁棒性。此外,Attractor++算法通过三角形结构在复杂网络中的重要特性,根据三角形结构的邻接特性和连接特性,提出了异常节点的优化规则和枢纽节点的发现规则,大大减少了异常节点的数量,与此同时也达到了检测枢纽节点的能力。通过在真实网络数据集和人工测试网络上的反复试验表明了Attractor++算法的有效性,不仅能更加有效的发现社区,而且能更加准确的识别异常节点和枢纽节点。2.在局部社区发现算法动态性研究方面,针对普遍使用的基于目标函数优化的局部社区发现方法存在“搭便车”问题,从而导致最终的局部社区容易陷入局部最优陷阱、易关联大量多跳远节点等缺陷,提出一种基于局部动态距离模型的K跳远局部社区发现算法K-Hop。K-Hop算法不依赖于任何目标函数,K-Hop算法从全新的视角考虑局部社区发现:局部动态距离。K-Hop算法的基本思想是将距离查询节点K跳远的节点作为一个局部动态系统,系统中的每个节点通过网络拓扑结构相互作用。为了模拟这种相互作用,我们设计了一个局部动态距离模型。基于局部动态距离模型,与查询节点连接紧密的节点将逐渐靠近在一起,与查询节点连接稀疏的节点将逐渐远离。随着时间步骤的反复迭代,与查询节点处于同一局部社区中的节点之间的距离缩小至0,而与其它节点的距离增大至1。最终,去除距离为1的边,与查询节点的距离为0的节点即为局部社区成员。在人工测试网络数据集和真实网络数据集进行广泛实验证明了K-Hop算法的有效性和合理性。3.在局部社区发现算法高阶结构研究方面,针对传统的局部社区发现算法都是简单的基于单个节点或边、忽略了复杂网络中的至关重要的高阶结构信息等问题,提出一种基于动态模糊隶属函数的高阶局部社区发现算法FuzLhocd。首先,针对传统的高阶结构电导率导致的全局搜索问题,本文提出了局部高阶结构模块度。然后基于局部高阶结构模块度提出了一种全局模糊隶属函数的高阶局部社区发现算法GloLhocd。为了进一步提高GloLhocd算法的性能,我们系统的分析了高阶局部社区发现的过程,将高阶局部社区分为三个阶段,并为每个阶段设计了不一样的模糊隶属函数进行高阶局部社区扩充,以及提出了相应的高阶局部社区发现算法FuzLhocd。最后,在多个人工测试网络数据集和真实网络数据集上进行大量实验表明了GloLhocd算法和FuzLhocd算法的有效性,不仅能够有效地解决查询节点依赖问题,而且能避免全局搜索引起的时间复杂度过高问题。4.在局部社区发现算法高效性研究方面,针对传统全局聚类算法无法高效进行局部社区发现等问题,本文提出一种基于局部振荡同步模型的局部社区发现算法LSync。为了能在低维向量数据集上进行局部社区发现,本文首先提出局部振荡同步模型。然后,基于局部振荡同步模型提出了局部聚类算法LSync。LSync算法首先根据查询数据对象所在的邻域确定局部振荡范围;然后基于局部振荡同步模型,邻域内的数据对象在耦合作用力的影响下会慢慢趋于同步,最终与查询数据对象聚集在一起的节点即为局部社区成员。此外,为了降低LSync算法的同步时间步骤,本文提出了邻域闭包代替传统的聚类序参,无需等待所有节点达到完全同步即可判断出局部聚类是否已经收敛。在多个人工测试网络数据集和真实网络数据集上评估了LSync算法的性能。实验结果验证了所提出的局部振荡同步模型不仅是正确有效的发现数据对象所在的局部社区,而且大大减少了振荡同步所需的时间步骤。