论文部分内容阅读
随着互联网技术的迅速发展,各种社交应用改变了人们的生活方式。人们在虚拟的互联网中交流合作,形成了大规模社会网络。在社会网络中普遍存在社区结构的特征,挖掘大规模社会网络中的社区结构能帮助人们了解网络中的内部结构和关系,从而更好的应用这些网络。因此,社区检测具有重要的现实意义。目前,研究者们提出了很多社区检测算法,但面对大规模社会网络中成千上万的节点,社区检测仍然是困难的。提升检测社区的时间效率,在有效的时间内,找出大规模社会网络中的社区结构,对于人们更好的应用网络是有意义的。合作博弈的层次聚类社区检测算法(GAMEHC算法)是我们在前期工作中的研究成果,该算法能够揭示网络社区的层次结构,但是由于该算法的时间复杂性较高且具有层次聚类固有的缺点,即无法预知网络最终应该划分成多少社区,因此该算法在大规模社会网络中很难得到应用。针对GAMEHC算法的不足,本文将在前期研究的基础上,深入研究能自动确定最终社区划分个数及提升社区检测效率的合作博弈算法,并将算法应用到大规模社会网络中。本文改变了GAMEHC算法中根据联盟Shapley值增量考虑联盟之间合作的策略;提出了以个体理性为核心策略的合作博弈社区检测算法。个体理性指以单个节点获取最大Shapley值来决策节点与联盟之间合作的策略。该算法包括初步检测和社区调整两个部分。初步检测是本文算法的核心,社区调整是在初步检测结果的基础上,将初步检测中产生的不合理的且规模较小的社区进行调整,最终得到社区检测结果。为了更好地提高算法的效率,本文根据合作博弈模型及算法执行策略,定义了无贡献节点以及已归属节点。无贡献节点为与当前联盟无任何边连接的节点,不会对联盟产生贡献。已归属节点为在算法执行过程中该节点的度已经全部贡献给了某个联盟,即已经确认联盟归属,无需参加下一次博弈。根据定义,设计了无贡献节点剪枝及已归属节点剪枝,有效的减少了算法中冗余的计算步骤,提高了社区检测效率。本文首先采用已知确定社区的小规模模拟基准网络及小规模真实的基准网络数据集,验证了本文算法划分社区的有效性;然后采用大规模真实社会网络数据集以及LFR基准随机网络进行实验,验证了本文算法具有较好的时间效率。