论文部分内容阅读
随着复杂网络不断涌现及其实际应用领域不断拓宽,复杂网络的理论研究受到广泛关注。社团结构和中心性特性是复杂网络中典型的结构特征,其中社团结构是指网络中的顶点可自然地形成不同的组,每个组即为一个社团。社团表现出高密度聚拢状态,即社团内部的节点之间联系较为紧密,位于不同社团的节点之间联系则相对稀疏得多。社团结构作为复杂网络的重要结构特征,包含的社团往往对应于网络的功能模块。通过检测网络的社团结构,可以发现网络的功能单元,研究结构与功能的对应关系,通过结构预测网络的功能。此外,已有研究表明,从社团层面往往可以发现单个顶点或整个网络层面未曾表现出来的一些特性。因此,社团检测方法的研究不论是在理论方面还是在实际应用方面都具有重要意义。研究人员已经提出了大量的社团检测算法,但很多算法的时间复杂度较高,无法有效地应用于规模较大的网络。针对这一问题,本文首先将频繁项集挖掘技术与LPA算法相结合,提出了改进算法LPAFI;其次基于局部中心性,提出了CG和CD两个社团检测算法。(1)LPAFI:该算法是基于LPA和频繁项集提出的确定性的社团检测算法。LPAFI算法首先通过多次运行LPA算法,将每次运行检测到的社团结构作为一条事务,从而构造出事务数据库,然后通过挖掘频繁项集的方法挖掘出满足条件的频繁项集,其次合并频繁项集,得到社团的大致结构,即“核心社团”。最后将不在核心社团的顶点作为“单点社团”,与核心社团进行社团合并,得到最终的社团结构。(2)基于中心性特性的社团检测算法:该算法根据社团结构的定义提出了新的局部中心性,即顶点与其邻居构成的社团,其内部边的数目占该社团总边数的比。局部中心性有一个重要的性质:中心性值较小的顶点往往处于社团的“边缘”。中心性增益算法又简称为CG算法,该算法首先通过重复的移除连接到顶点的边使得每个顶点的中心性值达到最大,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构;中心性扰动算法又简称为CD算法,该算法首先通过重复的移除对当前顶点中心性“贡献”较小的顶点之间的边,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构。为了验证本文提出的社团检测方法的性能,本文在7个网络数据集上进行了实验。实验结果表明,本文提出的方法能够快速地从网络中检测出高质量的社团结构。