很多复杂系统都可以抽象成复杂网络或者图来进行研究,同时,复杂网络科学的发展也极大地促进了人们对复杂系统的理解。在对复杂网络研究过程中,相继有很多重要特性被发现,比如自相似、吸引子、小世界、无标度和社团结构等。其中,社团结构是复杂网络中最重要的特性之一,对研究复杂网络的结构和功能有着举足轻重的作用,在社会学、物理学、生物学和计算机科学等很多领域均具有非常重要的意义。网络聚类就是检测复杂网络中的社团结构,这些社团结构具有内部连接紧密社团之间连接稀疏的特点。随着人们对社团结构持续不断的深入研究,已经涌现出大量优秀的图聚类算法。目前,在快速发展的社交网络和大数据的推动下,网络规模也不断增长,很多网络的规模甚至包含数百万个结点和数十亿条边。如何解决大规模网络聚类已成为该领域内的研究难点。基于此,本文首先简要介绍图聚类的研究背景及意义,并概述该领域重要的研究进展。接着对复杂网络的定义和特性、社团结构的定义以及图聚类的评价指标等相关基础知识作了简单介绍。然后,从优化一般图聚类算法出发,结合最近提出的基于快速发现和搜索密度峰值聚类算法和复杂网络无标度特性,提出基于中心结点快速检测的图聚类算法(CFCN),该算法通过快速搜索和检测聚类中心来实现网络的快速聚类。另一方面,为了改善一般聚类算法可扩展性以适应大规模网络聚类,同时满足实时性需求,本文提出了基于动态规划的大规模网络在线聚类框架(DPOCG),该框架通过构造超级结点和移除边缘结点大大减小了时变网络规模,从而使一般的图聚类算法得以适用。本文的主要研究工作如下:(1)提出了一种基于中心结点快速检测的图聚类算法。该算法首先计算每个结点的局部密度ρ和综合距离β,接着通过由ρ和β画出的决策图来快速确定检测聚类中心的局部密度阈值thrho和综合距离阈值thbeta,并检测出聚类中心,最后将非聚类中心结点分配到与其关系最紧密的聚类中心所在聚类以实现整个网络聚类。我们在真实世界网络上的实验结果表明,基于中心结点快速检测的图聚类算法的聚类效果明显优于对比算法。(2)提出一种基于动态规划的大规模网络在线聚类框架。该框架基于动态规划的思想并结合网络演变的特点,将大规模网络按一定时间段分成若干阶段的子网络。接着通过两种方式来减小每一阶段子网络的规模,分别是根据相邻阶段聚类内部结点状态变化情况对聚类内部状态未改变结点构造超级结点和移除网络边缘结点。最后应用一般图聚类算法?在缩减规模后的网络上进行聚类,并对移除结点按最近邻策略快速聚类,最终实现整个网络聚类。快速高效的DPOCG框架很好的解决了大规模网络聚类,并改善了一般聚类算法的可扩展性,同时满足了实时性要求。通过在合成的BA网络和真实世界网络上实验,结果表明了DPOCG框架的有效性,且聚类效果明显优于其它几种对比的大规模网络聚类算法。