论文部分内容阅读
伴随着互联网技术的发展,大量的复杂网络和社会结构正源源不断的产生。人们对复杂网络的研究,已经从早期的简单图论阶段进入到了现在的大批网络模型与算法并现的繁荣阶段。社区结构是复杂网络的一种中观结构,是对复杂网络某种程度的压缩,对了解网络结构与功能具有重要意义。传统的社区发现算法大都只能发现非重叠社区,对于重叠社区的发现算法的研究,目前还处于早期探索阶段。现实网络中存在大量的重叠社区,如一个人可以参加多个兴趣小组、一篇学术论文可以横跨多个学术领域、一个单词可以具有多个词性等等,因此发现网络中具有重叠性的社区结构往往具有更加实际的意义。针对当前各种应用的需要,本文在探索各种更加有效的重叠社区发现算法上进行了较系统和深入的研究,并形成了以下主要研究成果:(1)针对当前基于局部扩展类算法的不稳定性,提出了一种DOCNR算法。首先,新算法针对PageRank均匀分配策略进行改进,形成一种更适应于无向图处理的NodeRank算法,利用Node Rank算法计算所有网络节点的重要性,并依据节点的重要性选取种子节点。其次,一个没有外部链接的无向网络,经过NodeRank算法处理后,所有节点的重要度值之和近似保持不变,基于此提出了一种新的适应度函数,并在该适应度函数基础上,以种子节点为核心,按照广度遍历的思想逐层向外扩展社区,不同的种子节点扩展出的社区间会有交集,因此新算法能够发现重叠社区。最后,对重叠度过高的社区进行合并处理,作为最终计算结果。(2)针对当前LFM算法的时间复杂度过高以及会产生大量孤立节点等不足,提出一种基于贪心策略的快速扩张的重叠社区发现算法(QLFM)和一种基于先扩展后剪枝的重叠社区发现算法(ECLFM)。QLFM算法的特点是在适应度函数的基础上,基于贪心策略逐渐向外扩张形成社区;ECLFM算法则是在适应度函数的基础上,通过随机选取种子节点并以种子节点为核心,按照广度遍历的思想逐层向外扩展社区,当所有节点不能被扩展时,回溯去除已扩展节点集中所有不满足适应度函数的节点。(3)在一组不同公开数据集上将本文算法与现有LFM、CPM和COPRA等算法进行对比,实验表明:1)DOCNR算法具有较高稳定性,并能够更好地发现高质量重叠社区;2)QLFM算法和ECLFM算法不仅具有较高的时间效率,而且在重叠社区发现的质量上也优于现有其他几种算法。