论文部分内容阅读
复杂网络存在于世界上各个角落,深入研究复杂网络的结构特性具有十分重要的应用前景。社团结构是复杂网络的重要性质之一,近年来,划分复杂网络中的社团结构受到了各个领域学者们的广泛关注,并迅速成为了热门研究方向之一。本文针对基于节点覆盖的社团划分(Community Detection Based On Node Coverage,NCA)算法存在的不足,主要做了以下工作: (1)首先介绍了复杂网络的研究背景和意义,阐述了研究复杂网络的重要性,然后介绍了复杂网络的国内外研究现状和复杂网络相关的理论知识,并详细分析了一些经典的复杂网络社团划分算法的优缺点。 (2)研究基于层次覆盖的社团发现算法,针对NCA算法需要预知网络全局拓扑结构的问题,本文算法采用了随机挑选初始节点的方法,降低了算法的复杂度:针对网络中没有直接相连节点之间的相似性问题,本文算法引入了RA(Resource Allocation)算法,RA算法是一种基于资源分配的算法,该算法能够更准确的计算节点间的相似度,预测节点之间隐藏的规律。 (3)针对NCA算法会遇到异常节点的问题,本文算法增加了判断条件,通过比较节点之间的拓扑结构信息来判断节点是否能增加社团的紧密性,在划分过程中,会将异常节点找出,并对它们做出准确判断。 实验结果表明,相比经典算法和NCA算法,基于层次覆盖的社团发现算法不用预知网络中的聚类核心,使得本文算法能够应用于大规模网络中。另外,RA算法的引入和判断条件的增加,都提高了社团划分的准确性,使得到的社团结构更加紧密。