复杂网络理论为各学科领域中的复杂系统研究提供了简单而有效的研究方法,在近十多年里得到了学术界的高度关注。不同领域中看似迥异的真实系统在不断变化发展中会自然形成共同的特征,比如节点度的幂律度分布特征、小世界特征和社团结构特征等。由于突破了传统还原论将对象孤立研究的局限性,复杂网络能够准确刻画真实系统中的关键特征,本文研究的出发点就是网络的社团结构特征。一方面复杂网络中的社团结构可以对应于真实系统中自然形成的子系统,比如蛋白质合作网络会形成对应不同器官的功能模块,科学家合作网络会形成不同学科的研究群体,社交网络会形成基于不同兴趣爱好的俱乐部等。另一方面学术界对于复杂网络社团结构的主流认识只停留在直观层面,即把社团结构看作以更高概率相互连接的节点的集合,同时现有的社团结构探测算法也存在很多问题亟待解决,因此复杂网络社团结构研究仍然是一个开放性的课题,研究其探测算法具有重要的理论意义和现实意义。类似于聚类算法,社团结构探测算法也属于无监督学习的范畴,其目标在于把网络中的节点赋值到不同的社团中,因此基于聚类方法的理论框架提出社团结构探测算法是一个有前景的思路。密度聚类相比传统聚类技术有天然的优势,比如DBSCAN相比K-means来说无需类簇个数作为先验参数,不会落入局部最优陷进,抗噪声等,然而DBSCAN的聚类结果对两个参数的取值非常敏感,因此密度聚类的参数选择问题一直是机器学习领域亟待解决的难题。2014年发表在Science的论文中提出了新的密度聚类算法,即快速密度峰值算法(FDP:Fast Density Peak),该算法在保留DBSCAN优点的同时巧妙的克服了其参数敏感问题,为无监督学习提供了新的研究思路。受到这样的启发,本文拟利用FDP算法探测复杂网络中的社团结构。然而本文通过理论分析和数值实验发现,由于网络节点分布在极端高维空间中,导致FDP算法无法识别社团核心节点,从而无法直接应用于社团结构探测任务。除此之外,本文进一步发现当网络结构变得模糊或社团数量过多时FDP算法的决策图机制很难通过人机交互的方式准确识别社团个数。基于以上两点事实,本文提出了基于流形学习框架的ISOFDP算法,该算法有效克服了网络数据维数灾难的问题从而使得社团核心点显著区别于其它成员节点,同时提出了改进的分割密度函数以作为自动识别网络社团个数的依据,最终ISOFDP算法相比经典算法取得了更好的社团结构探测结果。更进一步的,本文将ISOFDP算法框架进行推广,分别提出了能够探测重叠社团结构、有权有向网络社团结构和动态网络社团结构的算法,并取得了优于经典算法的实验结果。本论文的内容包括九章:第1章介绍了本论文的选题背景和研究意义,并说明了本论文的研究框架和创新点。第2章介绍了复杂网络的基本理论和相关概念,然后对几类社团结构探测算法进行了综述。第3章分析了密度聚类算法fdp在探测社团结构时的缺陷,研究了克服其缺陷的方法之后提出了社团结构探测算法isofdp。第4章基于l-isomap、lle、le和lpp四种局部流形学习算法提出了快速社团结构探测算法,克服了isofdp计算性能低下的缺陷。第5章首先定义了非核心节点的社团隶属度测度,根据节点隶属度和阈值η的对比情况识别出网络的重叠节点,以此提出能够探测重叠社团结构的isofdpov算法。第6章基于信号理论的方法计算网络节点的相似度测度,该相似度充分利用了网络结构中连边的权重和方向信息,以此为基础提出了有权有向网络的社团结构探测算法isofdpdw。第7章结合时间维度的信息利用3-阶张量对所有时间点上的网络序列建模得到邻接张量,然后利用非负张量分解模型把邻接张量分解为节点社团隶属度矩阵和社团动态行为矩阵,以此求得动态社团张量,基于其各纵向切片探测各时间点上的社团结构和社团变化规律,最终提出了动态网络社团结构探测算法tenfdp。第8章基于2006年6月16日至2014年7月9日中信行业指数收盘价日数据,计算指数收益率之间的相关系数并以此为连边得到中信行业指数的平面最大过滤图(pmfg)网络,利用isofdpdw算法探测该网络金融危机前中后三个阶段的社团结构,以揭示金融危机对该网络社团结构的影响。第9章对全文进行总结,并给出了本文现阶段提出算法的缺点和不足,同时对本文算法的进一步推广和改进工作进行了展望。本文的主要创新点包括以下几个方面:第一,提出了一种基于密度聚类的社团结构探测算法isofdp。该算法无需社团个数作为先验信息,且在准确度、参数敏感性和稳健性3个方面都优于经典算法。isofdp继承了密度聚类算法fdp的优点同时克服了其缺点。首先通过理论分析和数值实验发现网络节点具备高维数据的特点,即节点之间的距离高度同质化导致fdp无法识别社团核心节点,本文假设存在低维的本征维度可以保存原网络的社团结构特征,提出使用经典流形学习算法isomap推断出网络在其本征维度上的映射,克服同质化距离的问题。本文进一步发现当网络结构变得模糊或社团数量太多时,在fdp的决策图上通过人机交互的方法无法正确识别社团个数,本文提出了改进的分割密度函数以自动识别社团个数,避免人机交互的过程。第二,提出了一种新的重叠社团结构探测算法ISOFDPOV。首先利用ISOFDP算法对网络进行硬分割,可以得到社团核心节点以及每个社团的成员节点。本文定义了成员节点的社团隶属度测度,该隶属度测度可以衡量节点归属于某社团的强度,然后根据各成员节点关于各社团的隶属度与阈值η的对比判断成员节点的社团归属情况,社团归属不唯一的节点为重叠节点,从而找到网络中的重叠社团结构。ISOFDPOV在人工和真实网络上取得了相比经典算法更好的社团探测结果。第三,提出了有权有向网络上的社团结构探测算法ISOFDPDW。首先分析了结构相似度只能利用二值对称邻接矩阵信息描述节点之间相似度的缺陷,提出使用信号相似度。信号相似度可以充分利用有权有向网络中连边的权重和方向信息,客观描述节点之间的相似度。另外使用有权有向模块度函数作为算法的收敛目标。最后在有权无向、无权有向和有权有向网络上验证了ISOFDPDW算法的有效性。第四,提出了基于非负张量分解模型的动态网络社团结构探测算法TenFDP。该算法假设每个时间片上的社团结构不仅与当前网络结构有关,还与上一时刻的社团结构有关。因此提出利用3-阶张量模型对每个时间点上的网络结构进行建模,得到领接张量以更好刻画网络结构随时间的变化。利用非负张量分解模型把领接张量分解为节点社团隶属度矩阵、社团动态行为矩阵,以此求得动态社团张量,基于该张量的每个纵向切片探测各时间点上的社团结构和社团变化规律。在5种类型的动态网络上验证了TenFDP算法的有效性。