论文部分内容阅读
随着复杂网络研究的兴起,从复杂网络的角度研究复杂系统受到了越来越多的关注。现实世界中大量的复杂系统均可以用复杂网络来描述。社区结构作为复杂网络的重要特性之一,引起了研究者的广泛关注。社区发现即为挖掘复杂网络中的模块化的社区结构的过程,这对于理解复杂网络的功能、发现复杂网络中隐藏的规律和预测复杂网络的行为具有重要的意义。然而,随着网络规模不断扩大,网络结构更加复杂,社区发现也变得异常困难。目前,已有的社区发现算法还存在以下问题:(1)现有的社区发现算法难以准确地发现稳定的重叠社区结构;(2)基于节点的社区发现算法难以发现网络中重叠度较高的社区结构;(3)传统的社区发现算法仅仅关注网络中的模块化社区结构,无法进一步识别社区中的层次关系。本文针对上述问题展开研究,主要工作和研究成果如下:1.提出了一种基于非重叠极大子团的标签传播社区发现算法。该算法在标签传播算法的基础上,对其进行三个方面的改进:在标签初始化阶段,通过查找网络中非重叠的极大子团结构,赋予每个非重叠的极大子团唯一的标签;在标签传播阶段,通过选取具有最大标签传播率的标签来更新节点标签;在社区调整阶段,通过合并相似度较高的社区来提升社区发现的质量。将该算法分别应用于计算机生成网络和真实的社会网络,实验结果表明:该算法很好地解决了标签传播算法的鲁棒性问题,并能准确地发现网络中的重叠社区。2.提出了一种基于核心链路的重叠社区发现算法。相较于当前的基于节点的重叠社区发现算法,该算法从链路的角度出发,通过选取核心链路,并根据链路影响力的强弱不断吸引外层链路进而形成链路社区结构;再将链路社区转化为节点社区,经过节点社区调整后,得到全局最优的重叠社区结构。该算法是一种无监督算法,无需输入额外参数。将该算法分别应用于计算机生成网络和真实的社会网络,实验结果表明,相较于其它算法,该算法能够更好地发现重叠度较高的社区结构。3.提出了一种基于种子节点集的社区层次结构发现算法。该算法通过选取种子节点,并根据余弦相似度的大小添加其最近邻节点共同构成种子节点集;再由种子节点集出发,基于分辨率公式进行社区层次结构探测,根据节点加入社区的度值比来判断是否到达层次边界;最后在已发现完毕的社区外选取新的种子节点集,并由此出发直到全网络的社区层次结构发现完毕。将该算法分别应用于人工网络和真实社会网络,实验表明,相较于其它算法,该算法能够准确地发现网络中全部的社区层次结构。