面向时态图的频繁社区搜索算法研究

来源 :深圳大学 | 被引量 : 0次 | 上传用户:banbe0602
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
社区挖掘是图数据挖掘的一项基本任务。在现有的图数据中,图中的边上通常都包含时间信息,例如科学家合作网络,电信话务网络,微信社交网络等等。绝大多数现有的社区挖掘算法主要针对传统的不包含时态边信息的图数据,因此无法适用于时态图数据的社区挖掘。本文主要研究时态图数据的频繁社区挖掘问题。我们的目标是找出时态图上所有的频繁社区结构。在传统图数据上已有多种社区模型,譬如k-core、clique、k-truss,k-edge connectedcomponent等。但是这些社区模型都是基于传统图数据上的模型,并不能在时态图上有效的搜索出频繁社区,为了能够在时态图上进行频繁社区搜索,我们提出了全新的频繁社区模型k-star。现实世界的时态图数据通常是极为庞大的,直接在原始的时态图上进行社区搜索是十分耗时的,为了能够高效的在时态图上搜索频繁社区,我们提出了时态图削减算法。该削减算法是通过一种弱核子图的概念来进行剪枝的。实验中该算法存在两方面的技术挑战:(1)频繁节点度的计算和(2)邻居节点的动态更新。我们提出度区间分解算法实现了对频繁节点度的快速计算和邻居节点的动态更新操作。在经过削减后的时态图中,为了进一步提升搜索算法的效率,我们又提出了强邻居剪枝算法和虚度剪枝算法。最后,我们在真实世界的时态图数据集上进行了大量的测试和对比实验。通过引入时态图削减技术和两种剪枝算法实现了在大型时态图上的高效频繁社区搜索。通过比较不同模型下的社区搜索结果,我们发现本文所提出的社区模型在搜索连接紧密的频繁社区方面有着非常好的现实效果。此外,实验结果还验证了我们所提出算法的有效性和可扩展性。
其他文献
种子萌发是植物个体发育中最关键的时期,其成功与否对植物后代繁衍和生存起着决定性作用,种子萌发一直是人们重点研究的问题。水稻种子萌发是一个非常复杂的过程,受多种因素
研究意义:了解南华医院护理人员遭受工作场所暴力现状,并对其影响因素进行分析,为健全关于工作场所暴力防范与处理的管理策略与制度,极大地让护理人员在暴力事件中进行自我保
结核病是一种传染性很强的疾病,对人类健康有严重的危害性。近年来,由于多重耐药结核病,已发生大量结核病和艾滋病病毒感染病例。结核病的爆发引起了快速上升的趋势,严重危害
目的:国内原发性胆汁性胆管炎(primary biliary cholangitis,PBC)继发性骨质疏松症(osteoporosis,OP)的发生率以及唑来膦酸的治疗效果尚无系统研究。本研究旨在通过与同年龄
麻疹是由麻疹病毒引起的一种传染性极强的呼吸道传染病。尽管麻疹在中国的免疫率达到了相当高的水平(99%),但目前仍是全球发病水平最多的几个国家之一,消除麻疹的任务依然艰
免疫系统是一种保护人体免受外来病菌入侵的重要系统之一,主要执行免疫应答及免疫功能。免疫系统具有识别和排除抗原的能力,同时可以维持自身内环境的平衡和稳定。人体肿瘤的
现如今,由于图像及视频分割具有的实用价值和对理论的引导作用,所以它仍然是计算机视觉领域的一个重要研究方向,也是众多基于图像及视频分析的高层视觉应用的基础研究内容,为
高效、准确地从卫星影像中自动获取道路信息是计算机视觉与信息工程研究领域的热点问题之一。以往对卫星影像中道路网的提取主要专注于线状特征的提取,有关道路宽度估计方法
随着互联网的发展,人们可以通过各种爬虫软件、搜索引擎获取大量的纹理素材。理想的纹理素材能够为艺术家提供丰富的创作灵感,帮助设计师绘制更加真实的场景,辅助医生进行科
蜜蜂是一种非常重要的经济昆虫,也是一种重要的真社会性昆虫的模式生物,工蜂的舞蹈语言是社会行为的典型代表性特点。为研究蜜蜂的舞蹈行为的获得机制,本研究通过组成中蜂和