基于合作博弈的社区检测算法研究

来源 :云南大学 | 被引量 : 0次 | 上传用户:liongliong484
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着互联网技术的迅速发展,各种社交应用改变了人们的生活方式。人们在虚拟的互联网中交流合作,形成了大规模社会网络。在社会网络中普遍存在社区结构的特征,挖掘大规模社会网络中的社区结构能帮助人们了解网络中的内部结构和关系,从而更好的应用这些网络。因此,社区检测具有重要的现实意义。目前,研究者们提出了很多社区检测算法,但面对大规模社会网络中成千上万的节点,社区检测仍然是困难的。提升检测社区的时间效率,在有效的时间内,找出大规模社会网络中的社区结构,对于人们更好的应用网络是有意义的。合作博弈的层次聚类社区检测算法(GAMEHC算法)是我们在前期工作中的研究成果,该算法能够揭示网络社区的层次结构,但是由于该算法的时间复杂性较高且具有层次聚类固有的缺点,即无法预知网络最终应该划分成多少社区,因此该算法在大规模社会网络中很难得到应用。针对GAMEHC算法的不足,本文将在前期研究的基础上,深入研究能自动确定最终社区划分个数及提升社区检测效率的合作博弈算法,并将算法应用到大规模社会网络中。本文改变了GAMEHC算法中根据联盟Shapley值增量考虑联盟之间合作的策略;提出了以个体理性为核心策略的合作博弈社区检测算法。个体理性指以单个节点获取最大Shapley值来决策节点与联盟之间合作的策略。该算法包括初步检测和社区调整两个部分。初步检测是本文算法的核心,社区调整是在初步检测结果的基础上,将初步检测中产生的不合理的且规模较小的社区进行调整,最终得到社区检测结果。为了更好地提高算法的效率,本文根据合作博弈模型及算法执行策略,定义了无贡献节点以及已归属节点。无贡献节点为与当前联盟无任何边连接的节点,不会对联盟产生贡献。已归属节点为在算法执行过程中该节点的度已经全部贡献给了某个联盟,即已经确认联盟归属,无需参加下一次博弈。根据定义,设计了无贡献节点剪枝及已归属节点剪枝,有效的减少了算法中冗余的计算步骤,提高了社区检测效率。本文首先采用已知确定社区的小规模模拟基准网络及小规模真实的基准网络数据集,验证了本文算法划分社区的有效性;然后采用大规模真实社会网络数据集以及LFR基准随机网络进行实验,验证了本文算法具有较好的时间效率。
其他文献
该文从数据仓库技术中重要的概念着手,详细介绍了在构建数据仓库过程中几个关键技术:数据抽取、存储管理和数据表现.星型模型是数据仓库的是数据仓库的数据模型.纳税申报的数
该文中讨论的方法——基于设计模板和软构件的软件开发方法——很好的解决了这个难题. 该文首先研究了设计模板和软构件的研究现状,分析了它们的优缺点,然后提出了将二者结合
该文详细描述了一个所设计的面向医疗应用与研究的数据挖掘构件库的结构框架,然后针对目前关于量化关联规则挖掘算法的不足,提出了一个QFP-tree算法,模拟医疗数据的结构和分
视频数字图书馆是数字图书馆的一个重要组成部分.目前在这个方面已经做了大量的工作,并出现了许多原型系统和商用系统.但这些系统都把重点放在视频理解与视频处理上,而在数据
该文的工作主要包括以下六个方面:1)结合当前的网络安全现状,研究了国内外流行的扫描软件,重点研究了它们的实现方式和技术特点.2)TCP/IP协议是网络互联的基础协议模型,是论
该文针对传统的多级分散式采购物流管理存在的问题,通过对汽车行业采购物流模式的研究,提出采用集中式物流中心管理模式.在采购物流管理中,强调供需双方物流信息共享,从而减
首先,该文简要分析了武器系统数据通信的特点和失效模式,然后介绍了一些常用的保证数据通信可靠性的方法.其次,该文针对武器系统中多CPU组成的处理机网络,当数据收发双方在半
如今,互联网在日常生活中越来越普及,人们习惯于通过搜索引擎在大量的网络信息中查找自己需要的信息,随着网络上信息海量地增长,搜索引擎的作用日益重要,赞助商搜索拍卖应运而生。
全文共分8章,主要内容如下:第1章:简要介绍了分布式虚拟环境的概念及特征,回顾了该技术的产生和发展过程,列举了一些典型的分布式虚拟环境系统和应用领域,介绍了分布式虚拟环境
现今商务世界中网络的广泛应用,相互交流各种来源不同的信息越来越重要。然而今天大多数的应用并不是为了共享信息而设计的,甚至是用不同的语言开发的,并在不同的硬件和软件平台