论文部分内容阅读
复杂网络是指具有复杂拓扑结构和复杂节点行为的网络系统,它是对现实世界中各种各样的大规模复杂系统的抽象。复杂网络的节点可以是任意具有特定动力和信息内涵的系统的基本实体,而边则表示这些基本实体之间的关系。复杂网络以展现出能够在节点和边的水平上被获取的丰富、低阶连接模式著称,社团结构是其中最重要的一种模式。当前,复杂网络中的社团结构研究已然成为了现代复杂网络科学中最热门的研究课题之一。研究复杂网络中社团结构能够帮助人们更加清晰的认识复杂网络中蕴含的拓扑结构,促进复杂网络科学研究从宏观到微观的高速发展,具有重要的理论意义和现实的应用价值。目前,随着真实网络规模的不断增大,大量的全局社团检测算法因过高的时间和空间复杂度已经无法满足时代的需求,如何设计针对大型复杂网络的全局社团检测算法是当前亟待解决的重要问题。另一方面,针对大型复杂网络,局部社团结构的挖掘显得尤为必要,如何设计快速的局部社团检测算法是近几年兴起的又一研究热点。针对以上问题,基于局部谱逼近设计了针对大型复杂网络的全局重叠社团检测算法和局部社团检测算法,主要工作及创新点如下:（1）针对大型复杂网络的全局重叠社团检测问题,提出了一种基于二次优化的团扩张（Quadratic Optimization-based Clique Expansion,QOCE）的全局重叠社团检测算法。QOCE算法包含四个关键步骤:极大团枚举、随机游走采样、二次优化和社团检测。首先,由于经典的Bron-Kerbosch（BK）极大团枚举算法对大型复杂网络的适用性,采用BK算法高效地找出复杂网络中至少包含3个节点的所有极大团。将所有极大团按其节点个数进行降序排列,然后依次删除与前一个极大团至少重叠75%节点数的所有极大团。其次,为了降低QOCE算法的计算复杂度,采用快速的随机游走策略以极大团为初始节点进行局部子图采样,使得该采样子图尽可能覆盖了极大团近邻的所有节点。然后,基于Cheeger割最小化,在采样子图上设计带l1正则项的二次目标函数并采用数值算法进行优化求解。最后,根据二次目标函数的优化解向量进行极大团所属社团的截断选取。由于不同的极大团扩张过程存在重叠现象,QOCE算法不仅适用于大型复杂网络还能检测重叠社团结构。大量的实验结果表明,QOCE算法在合成数据和真实网络上的社团检测准确度高于作为对比的几种基准算法。（2）针对大型复杂网络的局部社团检测问题,提出了一种基于Krylov子空间谱逼近（Krylov Subspace Spectral Approximation,KSSA）的局部社团检测算法。KSSA算法包含三个关键步骤:宽度优先搜索（Breadth First Search,BFS）采样、Krylov子空间谱逼近和局部社团检测。首先,为了降低KSSA算法的计算复杂度,从极少量带标签的种子集出发,通过BFS扩张技术获取包含种子集的局部采样子图,使得该采样子图尽可能覆盖了种子集所在目标社团的所有节点。其次,基于谱图理论,在采样子图上利用Krylov子空间局部逼近特征子空间,通过最小化一范式求解Krylov子空间中以种子集为支撑的稀疏标识向量。该稀疏标识向量中的元素值表示对应节点属于目标社团的概率。最后,对稀疏标识向量中元素值对应的节点进行局部社团截断。由于不同种子集的扩张过程存在重叠现象,KSSA算法可用来检测重叠社团结构。大量的实验结果表明,KSSA算法在合成数据和大型真实网络上的社团检测准确度高于当前流行的几种基准算法。（3）针对大型复杂网络的局部社团检测问题,提出了一种基于Lanczos迭代谱逼近（Lanczos Iteration Spectral Approximation,LISA）的局部社团检测算法。LISA算法包含三个关键步骤:热核（Heat Kernel）采样、Lanczos迭代谱逼近和局部社团边界截断。首先,为了降低LISA算法的计算复杂度,从极少量带标签的种子集出发,首次采用快速的热核扩散技术进行种子集的局部子图采样,使得该采样子图尽可能覆盖了种子集所在目标社团的所有节点。其次,基于Rayleigh熵最小化,在采样子图上设计快速的Lanczos迭代方法局部逼近转移矩阵最大特征值所对应的特征向量,并给出了Lanczos迭代方法的收敛性分析。最后,对Lanczos迭代逼近获得的局部特征向量中的元素对应的节点进行截断,从而获得具有局部最小电导（Conductance）的社团。由于不同种子集的扩张过程存在重叠现象,LISA算法可用来检测重叠社团结构。大量的实验结果表明,LISA算法在合成数据和大型真实网络上的社团检测准确度高于对比的几种基准算法。综上所述,针对大型复杂网络分别设计了全局重叠社团检测算法QOCE与局部社团检测算法KSSA和LISA。大量的实验结果表明,三种算法在合成数据和真实网络上的社团检测准确度高于各自对比的几种基准算法。