论文部分内容阅读
随着互联网在现代生活中的普及,现实世界中的许多事物都以网络的形态存在,重叠社区发现算法可以帮助我们更好地理解网络的结构特征。目前重叠社区发现算法总体可以分为全局划分和局部扩展两大类。本文主要对局部扩展类的重叠社区发现算法进行研究,针对现有算法在划分结果的准确性、稳定性和算法运行时间等方面存在的一些不足进行研究,提出多种改进算法。本文的主要研究工作及贡献如下:(1)针对现有算法划分结果在准确性和稳定性方面的不足,提出了一种基于K-核迭代因子和社区隶属度的重叠社区发现算法(KIMDOC)。首先,该算法引入一种节点重要性评估方法K-核迭代因子,同时引入节点密度的概念得到节点局部影响力的计算公式,利用这两种方法来计算节点影响力,并依据节点影响力选择种子节点,作为初始社区。其次,基于节点影响力提出一种新的社区隶属度函数,利用该社区隶属度函数基础上,以初始社区为核心,逐步进行局部扩展,因不同的社区间会有交集,故KIMDOC算法可以发现重叠社区。最后,对重叠度高的社区和孤立节点进行处理,得到最终的划分结果。(2)为了提高KIMDOC算法的运行效率,提出了一种基于完全图和社区隶属度的重叠社区发现算法(KIMDOC-CG)。该算法是在KIMDOC算法的基础上进行改进。首先,用KIMDOC算法中节点影响力的计算方法,选择种子节点。其次,以种子节点为核心,寻找完全图,形成初始社区。然后,在KIMDOC算法中的社区隶属度函数基础上,以初始社区为核心,进行局部扩展。最后,对孤立节点和重叠度高的社区进行处理,得到最终的划分结果。(3)针对现有算法在时间效率和阈值参数方面的不足,提出了一种基于K-核迭代因子和完全图的重叠社区发现算法(KICGOC)。该算法引入KIMDOC算法中节点影响力的计算方法,并依据节点影响力选择种子节点。其次,以种子节点为核心,按照不断寻找完全图的方式进行局部扩展。在扩展社区时,因为使用完全图代替社区隶属度,避免阈值参数对算法结果的影响;由于没有社区隶属度的计算,提升了算法的速度。最后,对重叠度高的社区进行合并,得到最终的划分结果。(4)在真实网络和人工基准网络上,与现有多种算法进行的对比实验表明:1)KIMDOC算法具有较高的稳定性和准确性,能够得到高质量的重叠社区;2)KIMDOC-CG算法不仅具有较高稳定性和准确性,能够发现高质量的重叠社区,并且在节点数量大于1000的复杂网络上,运行速度高于现有算法和KIMDOC算法;3)KICGOC算法在社区划分结果比现有算法好的情况下,不需要设置阈值参数,同时在节点数量大于1000的复杂网络上,具有更高的时间效率。