复杂网络中的重叠社团发现问题研究

近年来,复杂网络的研究受到了越来越广泛的关注,在计算机科学、物理学、生物学、数学乃至社会学和管理学等领域都产生了重大的意义和深远的影响。过去由于技术上的限制,科学家的研究往往都停留在只有几十、几百个节点的小网络上,研究方法大多是比较直观的图论方法。然而,随着信息技术的高速发展,科学家所面临的网络数据规模呈现爆炸式的增长,获取上亿规模的网络已经变得非常容易。在大规模网络数据的驱动下,网络科学得到了长足的发展,并在未来拥有更大的发展潜力。 社团结构是复杂网络所特有的一种中观结构,在真实世界中,它往往对应着不同网络的不同功能或结构单元。由于社团结构不仅是网络的一种压缩表示形式,更为网络的其他分析挖掘提供了中观尺度的分析视角,因而在大规模复杂网络的各项研究中,社团结构研究是一项非常重要而基础的工作。 社团的重叠是真实世界网络中常见的一种现象,例如一个人可以属于多个兴趣小组、一个蛋白质可以属于多个蛋白复合体等等,因此发现网络中的重叠社团结构更能准确地获取网络中真实的中观结构信息。但是,目前常见的各种重叠社团发现算法往往面临着复杂度较高或准确率较低等问题。此外,重叠社团发现中重叠程度的控制及结果的稳定性等问题也仍然有待解决。 因此,本文的主要工作及创新点包括以下几个方面： (1)提出一种可控重叠程度的重叠社团发现算法。利用边图发现重叠社团是一种重要的研究思路,然而简单的边图重叠社团发现方法并不能保证高质量的结果。本文在边图重叠社团发现思想的基础上,进一步发现,尽管每条边都可以通过边图下社团发现获得社团标签,但是处于社团之间的边用于标识节点的社团标签时可能带来噪音干扰。由此,我们提出一种在边图社团发现结果的基础上迭代删除社团间边标签的算法——CDAEO算法,一方面可以实现重叠社团发现结果准确率的提升,另一方面利用算法中的参数可以在一定范围内调节社区团间的交叉重叠程度。 (2)提出一种基于非重叠社团的节点中介度指标——社团中介度(community betweenness),并利用该指标设计了一种基于节点分裂的重叠社团发现算法——CBS算法。在社会网络分析的研究中具有高中介度的边被认为是网络中具有“桥”属性的边,著名的GN算法通过反复割断中介度高的边而达到非重叠社团发现的目的。之后有学者将GN算法延伸到分裂中介度较高的节点,从而发现重叠社团。尽管这些方法可以在许多真实网络中得到有意义的社团结构,但是由于中介度指标的计算复杂度太高从而限制了它们在大网络上的应用。针对这一问题,提出一种基于非重叠社团结构的局部中介度指标,即仅在一对社团的范围内计算社团间节点的中介度,从而将中介度的计算限制在一个有意义的局部网络之内,大幅降低了中介度计算的时间复杂度,进而得到一种高效的重叠社团发现算法。 (3)提出一种基于重叠节点条件的重叠社团发现算法——CONA算法。本文认为一个节点从非重叠节点变为重叠节点应该满足社团结构的模块化程度不被破坏这一基本条件,即社团结构的模块化函数值至少不会降低。基于这一发现,在选取EQ函数为重叠社团模块度量函数的基础上,我们通过理论推导得出了非重叠社团间及社团内的潜在重叠节点应满足的条件,并利用该推导结果设计了一种高效的重叠社团发现算法。实验表明,该方法在巨型网络上具有明显的速度优势,而结果质量方面也往往优于或至少近似于同类其他算法。 (4)提出一种基于均衡多标签传播的重叠社团发现算法(BMLPA)。标签传播算法(LPA)是一个著名的接近线性时间复杂度的快速非重叠社团发现算法,其算法过程非常简单明了。Steve将LPA延伸为可发现重叠社团结构的COPRA算法,继承了LPA快速的优良特性,但是也遗传了LPA结果稳定性差的问题。本文提出一种均衡多标签传播算法,不仅可以在某些情况下大幅提升算法的准确率,同时也在一定程度上增加了算法的稳定性。为了进一步提高算法的稳定性,本文还提出了一种粗糙核快速提取算法,以利用预先提取的粗糙核来对节点标签进行初始化。实验结果表明该标签初始化算法可以大幅提升多标签传播算法的稳定性。