重叠社团的划分算法及其节点影响力的研究

来源 :内蒙古大学 | 被引量 : 0次 | 上传用户:qwerdfhkotfd
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
社团是复杂网络广泛存在的拓扑特性之一,发现网络中的社团结构是复杂网络研究的基础性问题,也是热点问题。社团划分算法按划分结果可以分为重叠和非重叠社团划分算法两类。在社交网络中,与非重叠社团相比,重叠社团更接近于现实的网络结构,因此,本文选择研究重叠社团划分算法。同时,考虑到社团结构的变化可能会对依赖社团的应用产生负面影响,故本文也研究节点对社团结构稳定性的影响,用于辅助分析这类应用的易损性,而这也是近来研究者关注的一个热点问题。针对这两个问题,本文提出如下两种算法:  (1)提出一种重叠社团划分算法ESCA(Edge Strength Conductance Algorithm),该算法是针对Conductance算法存在的不足改进后的算法。Conductance算法是一个划分结果相对可靠的有权重叠社团划分算法,但在选择初始社团时没有考虑节点与邻居节点的关系,导致初始社团选择不合理,因而不能更准确地发现网络真实的社团结构,另外算法还存在节点遗漏的问题。针对这一不足,ESCA算法分别从边强度和隶属度的角度解决了这两个问题。实验结果表明:在LFR基准合成的有权和无权网络中,ESCA算法不存在节点遗漏,与Conductance和COPRA(Community Overlap PRopagation Algorithm)算法相比,该算法能够更准确地发现网络存在的社团数,且划分出的社团结构更接近于网络真实的社团结构。  (2)提出一种评估节点对网络社团结构影响力的算法BCA(Break Community Algorithm)。BCA首先从网络中识别对社团结构影响最大的子结构,然后评估所有子结构的全局影响力,最后从子结构挑选出对社团结构影响最大的前K个节点。实验结果表明:在LFR基准合成的有权和无权网络中,与传统的节点影响力评估指标相比,BCA能够更准确地发现对社团结构影响最大的节点集。
其他文献
人脸分析是近年来计算机视觉与模式识别领域里的热点研究问题之一,因为它在身份认证、视觉监控、人机交互、娱乐动画、以及多媒体等领域有着广泛的应用前景。人脸分析的研究
随着软件技术的发展,软件测试受到越来越多的重视。在软件测试中,测试数据的选择是进行结构测试的一个难题,测试数据直接关系到错误能否被预期测出。对于测试数据自动化生成
随着计算机和网络的普及,越来越多的人们通过网络进行交流,即时通讯软件已经成为网民最常用的网络工具之一。目前比较流行的即时通讯软件如:QQ,MSN和雅虎通等,这些主流的即时通讯
对于遍布全球各地的各类企业而言,企业应用数量与规模的增长总是伴随着旨在提供信息交换渠道的计算与网络础架构的不断扩建。企业内部会有多种为了不同目的而建置的信息系统,
在模式识别领域中,如何利用已有样本进行训练并提取特征,使各类样本具有异于它类样本的特征成为迫切需要解决的问题。目前虽有许多成熟的特征提取方法,但在某些情况下这些方
资源共享成为网络生活的主题,随之而来的多媒体数据安全问题成为目前一个相当重要而又富有挑战性的研究课题。密码学方法加密了多媒体对象的内容,使之变成密文,在一定范围内
随着无线通信技术的发展和便携设备的不断普及,人们对于低成本、易用的无线网络的期望与日俱增。而无线自组网络(Ad Hoc Network)以其优越的自组织特性成为最理想的候选技术之一
交互式电子白板技术自上世纪90年代出现以来,至今已经有20多年的历史,它广泛的应用于教学、办公、商务等领域,并且都取得了非常好的效果。由于传统的电子白板技术一直以来都需要
随着计算机技术和Internet网络的高速发展,从互联网上下载所需要的资料已经成为人们工作、生活中的重要组成部分。如何实现又快又好的下载是倍受关注的技术难题。当前大多使
分散在互联网上的信息资源极其丰富,但表现形式却各不相同,如何全面准确地从中查找特定信息一直是网络应用服务的重要研究内容。传统的搜索引擎使用简单的关键词匹配查找信息,尽