论文部分内容阅读
复杂网络理论作为研究复杂系统的重要工具得到了各领域学者的广泛关注。它以网络的形式对各类复杂系统进行最本质的抽象,为我们提供了一个研究这些系统的结构特性和动力学特性的跨学科平台。社团结构挖掘是复杂网络研究中的重要内容。已有研究表明,社团结构对复杂网络的特性具有重要的影响,挖掘网络的社团结构对相关理论研究具有重要的意义。此外,挖掘网络的社团结构还可以对复杂网络进行不同尺度地简化,帮助我们理解系统的结构和相应模块的功能。在工程领域中,社团挖掘作为网络聚类技术也具有重要的应用价值。 由于网络的社团结构过于复杂,在社团结构的定义、评判准则、挖掘算法等方面仍有许多问题没有解决。鉴于此,本文系统地研究了复杂网络社团结构的定义、数学模型、评判准则以及全局社团和局部社团的挖掘方法。 社团结构的形成是网络中的节点根据它们之间的联系强度进行自组织的结果。从该角度可知社团内每个节点的内部联系强度大于或等于该节点与其它任意一个社团的联系强度,该特征体现了社团边界的封闭性,可称为社团的边界特征。本文基于该特征推导出了社团结构的一个约束条件(diff值),该约束条件能够较准确地识别社团的边界,并能识别出那些划分错误的节点,是一个比较有效的社团挖掘评判准则。此外,社团结构还具备一个内部特征,即社团内部节点的平均相似度大于社团之间节点的平均相似度。边界特征反映了社团结构的自组织特性和边界的封闭性,内部特征反映了社团内部的节点平均来说联系更紧密。基于这两个特征,本文对现有的社团结构定义进行了改进,并基于定义建立了社团结构的数学模型,同时给出了一种具有线性时间复杂度的近似求解算法。 研究表明模块度Q值存在分辨率问题(欠分割),同时又存在过分割问题。这说明从最大化内部连边的角度研究社团挖掘评价准则可能存在误差。本文从相似度的角度,提出了一种密度对比割模型(Density Comparative Cut,DC-Cut)。分析表明,该图割准则受社团规模和形状的影响较小,其性能较稳定,社团挖掘结果也具有较好的可解释性。在DC-Cut的基础上,提出了一种社团挖掘评价准则S值,并建立了相应的社团结构优化模型。通过遗传算法对模型进行求解,并在多个基准图上进行测试,表明评价准则S值和优化模型具有较高的精度。 提出了一种快速的全局社团挖掘算法框架,将无权无向网络、加权网络和有向网络的社团挖掘问题统一到了同一个框架中。算法框架基于层次聚类的思想,首先通过节点相似度模型对网络进行初始化,将网络预处理为小规模的初始节点簇,在此基础上采用本文的簇相似度模型对这些初始节点簇进一步聚类,并根据评价准则S值选择最优的社团划分。在预处理阶段和节点簇聚类的过程中,借助于一个三元组和两个数学公式,使算法的效率得到较大幅度地提高,整个过程的时间复杂度仅为O(n2)。理论分析以及在各种无权、加权和有向基准图上的测试结果表明该方法性能较高,要优于现有的主流方法,如CNM算法和谱聚类算法等。 针对现有的局部社团挖掘算法存在精度和稳定性欠佳、对起始节点位置敏感等问题,提出了一种思路新颖的“内外夹推”算法(Shell Interception and Core Expansion,SICE)。算法首先利用本文推导出的“基于累积k步单向型随机游走的节点相似度模型”得到核心子图和邻居子图,并采用“一次一个子图”的方式扩展核心子图。该方式很好地解决了以往算法的一个缺陷(以往算法采用“一次一个节点”的方式容易受周围邻居子图的影响,导致节点误划分)。此外,在核心子图“外推”的过程中,邻居子图则对核心子图“内夹”,该方式可使SICE算法摆脱缺乏网络全局信息的困扰,能够识别出完整的社团结构,使算法具有较高的精度和稳定性(这里说的稳定性主要指从社团内任何一个节点出发,都能返回稳定准确的结果)。另外,这种“内外夹推”的机制还可以使SICE算法具备识别重叠社团的能力。理论分析以及实验表明SICE算法要明显好于当前的同类算法,其性能接近主流的全局社团挖掘算法。 文章最后对相关工作以及取得的成果进行了总结,并进一步指出了未来的研究方向。