论文部分内容阅读
复杂网络是研究复杂性科学的重要模型和工具之一,随着对复杂网络的研究,人们发现了复杂网络的许多重要的性质,其中社团结构是复杂网络最普遍最重要的拓扑性质之一。发现复杂网络中的社团结构对分析复杂网络的拓扑结构、功能和隐含模式,预测复杂网络的行为都具有重要的意义,在万维网、社会网、和生物网中具有广泛应用。 近年来,人们从不同的角度,针对不同类型的复杂网络,提出了很多挖掘社团结构的算法。本文首先介绍了复杂网络的基本理论,对复杂网络社团发现算法进行了综述,重点阐述了层次重叠社团的挖掘方法,这是当前复杂网络研究的热点之一。然后对层次重叠社团挖掘的经典算法LFM进行了分析,并基于该算法的三个缺陷,提出了一种改进的LFM算法。最后将最近的一个复杂网络社团结构整数规划模型和通用的模块度标准结合起来,得到了复杂网络社团结构的一个多目标模型,并针对该模型提出一种新的层次重叠社团挖掘算法。 本文主要工作如下: (1)简单介绍了复杂网络的基本理论,综述了复杂网络社团结构的典型挖掘算法以及评价这些算法的一般方法。 (2)针对经典的层次重叠社团挖掘算法LFM的三个缺陷,提出了一种改进的LFM算法,并通过在几个现实基准网络上的实验表明新算法能够克服原LFM算法的缺陷。 (3)将复杂网经络社团结构的一个整数规划模型和通用的模块度标准结合起来,得到了一个多目标整数规划模型,由此提出一种新的层次重叠社团挖掘算法。新算法不仅弥补了LFM算法没有结合模块度标准的缺憾,而且实验表明它也可克服一些典型的社团挖掘设算法由于模块度指标导致的分辨率不足的缺陷。