现实世界的大量复杂系统都可用复杂网络进行建模分析,而社区发现是复杂网络分析中的热门问题。社区发现能够帮助挖掘复杂系统内部个体间的聚集结构,分析个体与个体间的关联,掌握复杂系统的发展规律,发现复杂系统的隐藏功能等等,具有重要的研究价值和意义。大量研究表明,复杂系统发展过程中往往伴随着多种群体协同现象,如粒子的自旋现象、气味扩散中的随机游走现象、萤火虫闪光的同步现象等等。因此,基于群体协同现象或相关理论的动态社区发现算法已成为当前社区发现领域的热门研究方向。此外,随着复杂系统的不断发展和扩张,系统内功能的不断增多和个体的不断进化,“多个社区间的重叠性”、“复杂网络的大规模和超大规模特性”给社区发现带来了新的挑战。针对上述挑战,本文以群体协同的同步现象为出发点,分析了同步理论,对比了用于社区发现的两种同步启发动态模型,并以2015年提出的距离动态模型为基础开展研究,主要的研究内容如下:(1)传统基于距离动态模型的算法只能发现网络的非重叠社区结构,为了利用距离动态模型发现复杂网络中重叠的社区结构,提出了基于Link Graph的重叠社区发现算法。算法首先将原始网络转换为新的Link Graph,以原始网络的边作为Link Graph的节点,从而确保原始网络中两节点间拥有多条距离。其次,引入了间接邻居和邻居影响力两个定义,并以此改进了距离动态模型,增加了模型的鲁棒性和交互速度。然后,利用改进的距离动态模型发现Link Graph的非重叠社区结构。最后,将Link Graph的非重叠社区结构还原为原始网络的重叠社区结构,从而发现网络中的重叠节点。多个人工网络和真实网络的实验结果验证了算法的有效性和合理性。在高校朋友网络中的应用分析结果进一步证明了算法能够精确发现网络的重叠社区,检测出社区间的重叠节点。(2)为了进一步增强距离动态模型的鲁棒性,取代模型中的敏感参数λ,提出了基于Ego-Leader的强化距离动态模型和相应的社区发现算法。首先,受自然界同步过程的启发,算法引入了 Ego-Leader的定义,认为节点的邻居集合内存在一些Leader邻居会在同步过程中影响节点的运动方向。其次,在Ego-Leader的基础上设计了强化的距离动态模型,通过判断Ego-Leader集合内是否存在公共Leader,从而决定两个非直连节点在同步过程中是否靠近,进而取代敏感参数λ,增加模型的鲁棒性。最后,为了提升算法发现异常噪音点的精确性,结合Ego-Leader和结构化连通性的思想,提出了两种优化规则,并通过一个后处理过程来优化算法发现的异常噪音点,减少噪音点的数量。多个人工网络和真实网络的实验结果证明了算法有效性和鲁棒性。(3)为了利用距离动态模型高效、精确地发现大规模网络的社区结构,提出了面向大规模网络的快速社区发现算法。算法首先分析了导致无法快速发现大规模网络社区结构的主要原因。其次,设计了内部边预判策略,从节点和边两个角度提出了两种预判规则,快速预判网络中每条边是否为内部边,从而大大减少参加动态交互过程的边的数量,达到提升社区发现速度的目的。然后,通过内部边的预判,进一步减少动态交互过程中每条边需要交互的邻居节点的数量,进而提升了动态交互过程的速度。最后,引入了三角形距离的定义,利用两条真实边的距离来测量两个非直连节点间虚拟边的距离,消除了因计算外部邻居的初始距离而带来的额外开销,克服了“外部邻居的距离永久不变”的缺陷,也进一步提升了动态交互过程的速度。多个真实世界网络和人工测试网络的实验结果证明了算法能够快速且精确地发现大规模网络的社区结构。(4)大量实验表明面向大规模网络的快速社区发现算法依然无法处理边数达到亿级的超大规模网络。为此,提出了面向超大规模网络的并行社区发现算法,以“分而治之”的优化策略,实现了利用距离动态模型快速发现超大规模网络的社区结构的目的。首先,算法根据“分”思想以并行模式将超大规模网络划分为成百上千个小网络。其次,引入了收敛门限和预判系数两个定义,并进一步改进了距离动态模型,通过减少动态交互周期的方式提升了动态交互的速度,解决了动态交互过程中的慢收敛问题。然后,根据“治”思想以并行模式在每个子网络中执行动态交互过程,从而计算子网络中每条边的最终距离。最后,根据“合”思想收集所有子网络中长距离的边形成原始网络的外部边集合,从而发现原始超大规模网络的社区结构。多个真实网络和人工网络的实验结果验证了算法高效性和精确性。