网络团体结构是现实世界中复杂网络最普遍和最重要的拓扑属性之一。具有团体内节点相互连接紧密,而团体间相互连接稀疏的特点。揭示复杂网络的团体结构对分析网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义和应用价值,在科学研究、计算机科学、社会、生物和万维网等领域中具有广泛应用。图是网络结构建模的主要方法。它将现实世界网络中的实体映射为图的节点,实体间的关系映射为图的边。为了探测和发现大规模网络中的团体结构,人们将图作为其理论模型提出了众多图聚类方法。本文阐述了图聚类方法研究的背景、意义、国内外研究现状以及目前所面临的主要问题,给出了复杂网络团体结构发现方法研究的一般框架,概括性地分析比较了目前具有代表性的发现网络团体结构的图聚类方法的主要优缺点,提出了两种全新的适合不同网络规模的图聚类算法,通过在真实数据集上的验证与检验发现,其聚类效果较其他同类算法有显著提高。论文的主要贡献如下:1.本文给出了复杂社会网络团体结构发现方法研究的一般框架模型。该模型包括网络结构建模、节点相似度定义与计算、聚类算法设计、实验验证与聚类结果分析与评价五个连续步骤。2.引入了结构互联度的概念用以反映节点间的连接强度。相邻节点的结构互连度正比于其公共邻接节点的数目,非相邻节点的结构互联度定义为其间所有各最短路径上的邻接节点对的结构互联度的乘积中的最大者。基于上述定义并结合凝聚方法的基本思想,本文提出了一种新的网络图凝聚聚类方法。使用该方法在若干真实网络数据集上的测试分析表明其精度良好。3.受Girvan-Newman分裂算法思想的启发,引入了边连接系数的概念,提出了基于边连接系数的思想来发现团体结构的分裂聚类算法。该方法的算法复杂度为O(m~2),其中m为网络图的边数,聚类速度明显优于同类GN算法和基于GN算法的一些变种算法,适用于大型复杂网络的快速聚类。在将该方法运用于真实数据集的聚类实验中,取得了令人满意的结果。4.提出了一种优化的初始聚类中心节点的选取方法。该方法在运用最大最小方法求取初始聚类中心节点时同时考虑中心节点间的结构互联度和节点度数两个因素,理论上它比仅考虑距离等单一因素的聚类中心选取方法更具合理性。实际测试表明:这种方法求取的初始聚类中心点比较均匀的分布于不同聚类区块中,从而为提高聚类算法的精度和收敛速度奠定基础。5.设计和实现了上述各算法,并将其应用于空手道俱乐部关系网络(Zachary’s karate club),美国大学足球赛网络(American College football),海豚家族关系网络(Dolphin social network),美国政治性书籍构成的关系网络(Books about US politics)等来自真实世界的网络聚类分析基准测试数据集。实验表明,本文所提出的算法无论在聚类精度和速度还是团体结构模块度分析上都较同类算法有较大的提升。