过去几十年间,以Internet为代表的信息技术的迅猛发展使人类社会迈入了网络时代.将数学中的图论应用到各种领域中的问题后,形成了以研究某种实际节点和节点之间关系的学科—网络科学.从网络科学的角度来看,无论是自然界还是人类社会,网络都无处不在,比如社交网络、交通网络、万维网、生物网络以及工程网络等等,这些网络相互交叉,深刻且广泛地影响着人们的日常生活和科学技术等各种活动.因此,利用网络科学,可以探讨自然界和人类社会的各种各样的复杂系统.在网络科学的思想、理论和方法的大框架下,无论从微观上还是宏观上,人们都可以从全新的网络的角度、观点和方法来探讨世界万物的复杂性问题.复杂网络作为网络科学的表现形式,为人们研究网络科学提供了一条路径.随着对网络的研究,人们发现许多实际网络都有一个共同的性质,即为社团结构,也就是说整个网络是由若干个“群”或“团”构成的,每一个社团内部的节点之间连接相对非常紧密,但是各个社团之间的连接相对比较稀疏.复杂网络社团结构的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为不仅有十分重要的理论意义,而且有广泛的应用前景.尽管网络是系统高度抽象的离散数学描述,但是因为其规模的庞大和系统连接的多样性也使得研究其结构和功能变得复杂.社团化是一种揭示系统结构和功能之间对应关系、降低对复杂系统认识难度的方法.考虑网络G的子网络V中的节点i,则ki(V)=kiin(V)+kiaut(V),其中kiin(Ⅴ)表示节点i连接子网络V内其它节点的边的条数,kiout(Ⅴ)表示节点i连接子网络V外其它节点的边的条数.在此基础上给出社团结构的两种量的定义：(1)强社团结构.如果对任意节点i,子网络V满足kiin(V)>knout(V),(?)i∈V.即该社团内任何一个节点与这个社团内部其他所有节点的连接数目,比它与该社团外部的所有节点的连接数目要多,那么称V为该网络的强社团结构.(2)弱社团结构.如果子网络V满足∑kiin(V)>∑kiout(V)即该社团内节点间的相互连接比这些节点与社团外部的节点的联系更加紧密,也就是说,社团内部的边数之和大于社团边界上的边数之和,那么称V为该网络的弱社团结构.社团结构的划分方法主要分为两类：全局方法与局部方法.全局方法包含谱方法、模块度方法以及密度子图方法等等；局部方法主要采用局部聚类的方式来划分社团结构.这些方法主要是基于统计物理的方法和启发式算法,我们从图论的角度出发,提出了新的社团划分方法.二分图又称作二部图,是图论中的一种特殊模型.设G(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(U,K),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈U,j∈E),则称图G为一个二分图.我们根据一个一般的网络G(V,E)建立与之相关的二分网络G(V,V’,E),把原始网络中G的节点分别作为二分网络的两部分节点(V，V’),根据原来的边集E在两部分节点之间连边,这样就建立了一个二分网络.最大流问题是在网络中求源点到汇点的最大流值的问题,在二分网络中,把点集V作为源点集合,并建立k个汇点集合,每条边上的流值为1,最后统计汇点上的最大流值.k个汇点就可以看成k个社团,流向这些汇点的源点就是这个社团内的点,称这种方法为基于改进最大流问题的社团划分方法.图的均匀染色是一种特殊的点染色.如果图G(V,E)的点集V可以划分成k个独立的子集V1,V2,…,Vk,使得||Vi|—|Vj||≤1(1≤i,j≤k),则称图G是均匀k-可染的.由此我们同样可以定义网络的均匀社团划分,并且根据不同的指标就能划分不同的社团结构.我们主要研究了两种均匀社团结构的划分,一种是全均匀社团划分,各个社团内部的节点数目差值小于1；第二种是密度均匀的社团结构,各个社团之间的划分密度,也就是边数与点数的比值,保持一致.结合这两个定义在文章中介绍了对应的社团划分方法以及意义,说明了网络的均匀社团划分具有广泛的应用价值.挖掘网络中的重要节点是网络中很重要的一类问题,也就是对于网络中节点的重要性进行排序.在探索网络的社团结构时,一般的社团划分方法并不能真正反应节点和社团的实际关系,重叠社团发现更符合真实世界的社团组织规律,这种现象普遍存在于各种真实网络之中,如社会网络中的人属于多个集体、网络中的网页属于多个主题等.因此,位于网络中重叠区域的节点就尤为重要.在网络中,通过比较疾病在相同条件下的传播范围,来确定节点的重要性,范围越广,影响力越高.文中分别分析了具有最大度数的点,最大介数的点,最大聚类系数的点以及位于重叠区域节点的传播范围,确认处于重叠区域的点的影响力相较于其它的节点要高.因此,在疾病传播过程中,应优先对这些点进行免疫或者隔离,而在新闻传播中应重点宣传.为了更好地了解复杂网络的拓扑结构,人们建立了各种网络演化模型,比如随机网络模型,小世界网络以及无标度网络.这些模型很好的匹配了网络演化过程中的某些性质.任意两个质点之间都存在引力,与质点的质量成正比,而与质点间的距离的平方成反比,这是万有引力定律的基本内容,文中认为这一定律同样适用于复杂网络的演化过程.把节点的度数看成质量,再加上节点间的距离,就建立了适用于网络演化的引力网络模型.利用这一模型建立的网络具有更多的实际网络的性质,而且包含明显的社团结构.社团与社团之间的结构也是不同的,文中揭示了两种社团结构,一种是领导者社团,社团内部存在一个或者几个具有较大度数的节点；另一种是自组织社团,社团内部的所有节点的度数相差不大.文中综合探讨了这两种社团结构.此外,引力网络模型中也包含这两种社团结构.本文主要研究的是复杂网络中的社团结构划分,以及与社团结构相关的复杂网络问题,全文共分为五章.第一章给出了一个相对完整的简介.首先介绍一些复杂网络的历史和概念,然后给出了关于社团结构划分方法以及社团结构的评价指标的相对完整的综述,最后,给出了本文的主要结果.第二章我们首先研究了基于改进的最大流问题的社团划分方法,并给出了几个实际网络的划分情况.然后讨论了网络中的均匀社团划分,我们揭示了两种均匀社团结构,并结合一个真实网络说明了均匀社团划分的意义.第三章主要讨论网络中重叠节点的重要作用.在这一章里,我们首先给出了对于节点重要性的介绍.之后,在实际网络中,我们对比验证了网络中重叠节点的重要作用.第四章主要讨论了社团结构的分类以及引力网络模型.首先介绍了一些基本知识,然后解释了如何给社团结构分类以及引力网络模型的建立过程,最后讨论分析了引力网络的拓扑结构特征.第五章给出了本文的主要结论,并展望了这一方向有待解决的问题.