论文部分内容阅读
现实生活中很多复杂系统都可以建模成复杂网络从而进行深入研究。社团结构是复杂网络的一个基本性质。寻找复杂网络中隐藏的社团有助于了解网络的功能和网络上其他任务的完成。本文主要研究不同类型网络上的社团检测算法,涉及的网络主要是简单网络、多层网络和二分网络。本文的工作如下所示:1.社团检测可以被建模成优化问题继而进行求解。模块度是简单网络上使用最广泛的目标,我们可以通过最大化模块度来获得划分。然而,模块度受到分辨率的限制,即当网络足够大的时候,通过最大化模块度找不到网络中小的、自然的社团。因此,Aldecoa等人提出了另一个全局优化目标surprise(S),并且通过实验验证了S不受分辨率限制的影响。我们在密母算法的基础上提出了一个通过最大化S来寻找简单网络中社团的算法MA_S-CD。通过实验我们发现,得到的社团拥有很高的社团密度。同时,最大化S在部分网络上会导致不平衡的划分。我们于是提出了一个简单的社团合并算法MA_S-CD_revised来对实验结果进行校正。在大量网络上,校正前后实验结果的对比说明了MA_S-CD_revised的有效性。2.多层网络上的社团检测算法强调的是综合各个图层的信息继而得到一个相对鲁棒的划分。然而,大部分的社团检测算法都是针对简单网络而设计的,很少有算法是针对多层网络而设计的。我们基于图层合并的思想提出了一个多层网络上的社团检测算法LRCD-BNs。其基本思路是将多层网络上的社团检测问题转化成图层合并问题继而进行解决。首先,我们改进了一个图层合并算法neighaggre。其次,使用neighaggre去寻找多层网络中存在的社团。实际网络上的实验结果说明了相比较于其他图层合并算法,neighaggre可以获得更高的相对熵。此外,我们将LRCD-BNs应用到实际网络和人工网络上。实验结果表明,LRCD-MNs获得的实验结果在模块度上优势很小,然而却有很高的S值。3.二分网络上与社团检测相关的目标很多,但是很少有工作对这些目标进行实验上的比较。二分网络上的社团有两种不同的定义。因此,这些目标可以分为两类。我们希望在标准网络上对比这些目标的性能。我们在密母算法的基础上,针对不同的情况设计了不同的算法,继而在大量的网络上对不同类别的目标进行了实验。通过结果的比较我们找到了在大部分情况下表现最好的目标,同时发现了一些目标的优点和缺点。