论文部分内容阅读
随着信息技术的不断发展,复杂的网络社区结构越来越多的被学术界关注,社区发现的相关技术已经成为了当下分析网络社区的重点。因此,社区发现的深入理论研究对于社区网络结构和社区网络特征有着极其深远的意义和目的。目前,社区发现算法的划分主要分为两个方面,一个是非重叠的社区发现算法,另外一个就是重叠的社区发现算法。但是现实情况不像想象的那么简单,它是一个复杂的网络结构,即复杂网络中的单个节点极大可能存在于多个社区网络环境中。因此,本文对重叠社区发现算法的研究,无论从理论依据还是现实情况都有重大的意义。传统的标签传播的社区发现算法是LPA算法,它单独使用网络结构来指导其过程,既不需要任何参数,也不需要优化目标函数。它从每个节点具有不同标签的配置开始,在每个步骤中,一个节点(异步版本)或每个节点(同步版本)都自行决定将其标签更改为最大数量的邻居所携带的标签。若标签有多个,则随机选择其中一个作为标签。通过构建算法函数,随着其不断的迭代和函数的渐渐收敛,每个节点在自己的社区中拥有的邻居数量要多于其他社区中的邻居。更重要的是,它是重叠社区发现算法SLPA和COPRA的基础算法,两个算法都是在此基础之上拓展出的社区发现算法。目前常见的重叠社区发现算法包括派系过滤CPM算法,SLPA和COPRA等。而SLPA和COPRA都是基于标签传播算法LPA改进形成的新算法,它们相比于CPM算法无论是效率和复杂程度上都要更优一些,从而在社区发现的领域内被广泛的应用与研究。其中COPRA算法可以有效的挖掘出重叠社区网络,但是该算法随机性强,鲁棒性差,社区划分的结果极其不稳定。针对上述社区发现算法COPRA所带来的问题,本文提出了基于标签影响值的重叠社区发现算法,主要思想仍是以COPRA算法作为相关基础,在该算法的基础之上提出了标签影响值的概念。由于COPRA算法在标签初始化阶段所带来的效率低,稳定性较差,标签选择阶段所带来的随机性强的问题,本文首先针对效率低,稳定性差的问题提出了一种三角形的标签初始化方法,该方法保证了初始化阶段更新标签的时间复杂度降低,同时资源消耗也较小。然后针对随机强的问题,本文提出了一种标签影响值的概念,该方法从三个方面考虑了标签的选择问题,不会像COPRA那样稳定性得不到保障,从而在此基础之上提出了Label_Inf(l)这一方法。和COPRA算法相对比,本文提出的Label_Inf(l)虽然耗费的时间较长,但是有利的一面是该算法和原有COPRA算法相比,稳定性得到了很大的提高,从而保证在追求稳定性的时候可以划分出优质社区。为了验证Label_Inf(l)的计算准确性,选用了两个基准数据集Zachary karate club和American College football以及一个人工合成网络数据集对本文提出的算法进行测试评估。通过在两个基准数据集上进行重叠社区发现算法COPRA与本文算法对比,本文提出的算法由于在标签初始化阶段和标签选择阶段进行了改进,虽然时间复杂度有所提高,但是模块度Q也有所提高,这就说明了本文提出的算法在社区划分上稳定性提高了,增强了准确率。而使用人工合成网络数据集在SLPA,COPRA和本文算法上进行对比,发现本文算法的NMI值的下降幅度比SLPA和COPRA要少,这间接说明了本文算法在社区网络复杂的情况下,依然可以划分出较优质的社区。