论文部分内容阅读
复杂网络的社团结构挖掘是复杂网络理论和应用领域的热点问题。根据节点是否只属于一个社团，社团结构可分为非重叠社团结构和重叠社团结构。人们普遍认为，重叠社团结构更符合真实的社团组织规律。目前社团结构的挖掘研究主要集中在非重叠社团上，形成了一套较为成熟的理论和方法;而对于重叠社团结构的挖掘研究才刚起步，提出的一些方法还有待完善。本文围绕基于边聚类的挖掘算法展开研究，提出了两种不同聚合方式的算法。 Ahn等最近提出一个基于边聚类的重叠社团挖掘层次算法，它以划分密度D作为优化标准。该算法能有效应用在大规模高度重叠网络中，但在小规模的非高度重叠的网络中效果较差。针对这个特点，本文第三章提出了两种改进策略。其一是直接在合并过程中求划分密度D最优的边森林结构，然后用扩展模块度Q0继续合并得到最终的重叠社团结构。其二是在Ahn等算法中完全用扩展模块度Q0取代划分密度D作为优化标准，得到一个Q0最优的重叠社团结构。在五个经典基准网络上的测试表明，基于这两种改进策略在小规模非高度重叠的网络中能挖掘出重叠社团结构。 第四章基于边聚类提出了一种以最大度的边为中心的种子扩散重叠社团挖掘算法。该算法通过寻找社团和扩散初始社团两个步骤来逐次产生社团结构中的每个社团，从而得到最终的社团结构划分。实验证明这种种子扩散算法能有效地挖掘出五种基准网络中的重叠社团结构。