概率图上Top-K极大团枚举问题研究

来源 :东华大学 | 被引量 : 0次 | 上传用户:a370298894
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
极大团是稠密子图的一种,极大团枚举用于从给定图中挖掘不被其他团包含的完全子图,其中Top-K极大团枚举用于返回规模最大的K个极大团,在生物医疗、社交网络等应用中找到关系密切的顶点集合用于辅助分析。相较于确定图,实际应用中的数据图往往带有概率信息,用以刻画数据不完整或不精确的程度或者可能性。现有方法在概率图上求解Top-K极大团时,返回的是概率最大的前K个极大团。由于极大团的概率会随着顶点规模的变大而不断减小,这种方式会丢掉顶点规模大而概率较小的极大团,而这些被丢掉的极大团规模较大,在实际中具有重要的应用价值。本文研究概率图上的Top-K极大团枚举问题,具体研究内容如下。首先,本文重新定义了概率图上的Top-K极大团枚举问题,用于返回概率值大于给定阈值的前K个规模最大的极大团。在此基础上,提出了一种在概率图上枚举Top-K极大团的基础算法Top-KC。该算法通过维护一个大小为K的结果集来保存当前的Top-K极大团,并在枚举极大团的过程中不断对其进行更新,保证结果集中团的顶点规模尽可能大。针对基础算法存在的冗余计算问题,本文提出了两种优化策略来加快Top-KC算法枚举极大团的速度。分别是基于顶点的度和核心值进行排序和剪枝,以此来减少需要枚举的极大团数量,避免不必要的计算。其次,提出了基于边的三角形数量的预处理策略来化简数据图的规模,从而减小极大团枚举算法的计算代价。其基本思想是在枚举之前计算每条边能被多少个三角形包含,如果数量小于2,则说明该边对应的两个顶点能参与的最大团规模是三个顶点,因此可以将该边删除,以减小图的规模。基于这种策略对图进行简化之后,再应用以上两种优化策略,可显著提升Top-K极大团的求解效率。最后,基于15个真实数据集进行了实验,以Top-K极大团求解过程中所枚举极大团的数量和计算总时间为指标,对本文提出的算法的高效性进行了验证。实验结果证明,基于度的优化策略和基于核心值的优化策略能够有效提高枚举极大团的效率,基于边的三角形数量的删边策略能在前两种优化的基础上进一步减少计算时间。
其他文献
对于服装图像的实例分割是解决服装的三维重建,实现三维虚拟试衣的前提。获取边缘分割效果好,分割后噪声小的服装图像可以使得虚拟试衣的效果更加真实。但是由于服装本身复杂的边缘形状以及服装中存在多种不同结构的部件(如衣领、袖口、口袋等部位),传统的分割算法并不能完成细粒度的分割,因此本文设计了一种基于深度学习的服装图像的分割算法,并考察与探究其分割性能及实际应用。首先,对于图像分割任务,现在的方法大多是基
二维纳米材料MXene,因特殊的结构和丰富的表面官能团使其具有高电导率、高电子迁移率、良好的生物相容性、以及多样化的形貌,在力敏传感领域具有很大的研究前景。同时,MXene属于常温光热转换远红外高辐射材料,光热转换率高,具有可吸收环境热量以远红外能量形式输出的特点,可应用于多功能可穿戴器件。基于此,本论文从织物基底出发,使用不同的织物基底负载具有单、少层的结构的MXene材料,对比并选择MXene
工业机器人可以降低工人的劳动强度,减少劳动成本,提高生产效率,在工业生产中得到了广泛应用。但是随着生产规模的不断扩大,不同厂家机器人间没有统一标准化协议的问题越来越突出。本文为了实现对多种类型机器人的系统集成,对不同厂家机器人的通讯控制协议进行了研究,确定了多机器人集成系统的架构和通信方案,完成了集成控制软件的开发以及任务调度算法的设计,并对软件和算法进行测试,验证了可行性。本文的研究内容包括如下
近些年,柔性织物传感器因其舒适性、可穿戴性而受到极大的关注。通过织物传感器可以用来记录、监测人体活动和生理信号,包括心跳、关节运动、身体状况、睡眠质量等。其中,导电纤维作为织物传感器的核心组成部分,在本文中对其进行了细致的研究。为了批量化、低成本的制备弹性导电纤维,本文设计了一种包括纤维成形、牵伸、干燥、收集的一步式湿法纺丝装置;通过实验装置制备了不同工艺参数的芯部为纯聚氨酯、鞘部为炭黑/聚氨酯复
随着现代设计和空气动力学的深入发展,加工零件的几何构造变得个性化、复杂化。由于光学测量的不断发展,激光三维扫描技术在精度和效率上均有很大提高。本文以典型的汽轮机叶片为对象,通过对自行搭建三维激光扫描系统所采集点云的处理实验分析,得出各种去噪算法的原理及效果,提出针对散乱点云的排序算法和多幅点云快速拼接合并算法,研究散乱点云的曲面重建算法和孔洞修复,同时编写软件实例化验证分析。具体研究内容和主要研究
随着中国水下航行器的进步,水下图像处理技术在国际上引起了广泛的关注。由于水下环境的复杂性,水下拍摄得到的图像与视频往往质量较低,需要进行鲁棒的质量增强。在图像处理技术飞速发展的今天,如何根据大数据时代大量水下图像应用的需求,从众多增强算法中高效准确地为水下成像应用场景挑选出一种性能优异的质量增强算法是个颇具探究价值的科学问题。水下图像集的质量评价通常需要从原始图像集中选取一定数量的图像子集,通过质
中小学的校园安全作为维系千家万户的严肃问题,与每位师生、家长都有着紧密的关系。近年来,校园安全事故频发,尤其是5至12岁学龄儿童的意外伤害事故接连不断,校园安全问题俨然成为全社会讨论的焦点。为方便家长和学校教师及时掌握学生的出入校情况,本文以中小学的校园安全接送作为研究背景,针对成本昂贵的硬件设备和单人逐个检测的缺陷,提出了使用普通摄像头的人脸识别技术,能够准确识别接送人员的身份,制止不明身份者混
纺织鞋面特征点冲孔是高端制鞋流程中的关键步骤之一,冲孔质量的好坏将直接决定了后续鞋样原料是否能与转印纸精确匹配。目前,我国大多数制鞋企业在该环节所采用的方式仍为人工冲孔,与发达国家的自动化冲孔相比仍有较大的差距。近年来,随着国内计算机信息技术的不断创新发展,机器视觉技术在工业领域的应用越来越广泛,采用机器视觉技术实现鞋面特征点自动化冲孔势在必行,在大幅度提高鞋企的生产效率的同时,降低了企业的生产成
近年来随着国家对零排放的核电等清洁能源的重视,核电站对反应堆运行检测的自动化、智能化提出了更高的要求,其中三维水下测量技术是核电工程领域安全检测的重要一环。结构光三维测量方法在高精度检测领域有广泛的应用,而三维测量技术中基于光栅投影的面结构光测量方法成像效率高,实时性强,且精度满足多数测量需求。本文对基于光栅投影的三维水下测量技术进行了深入研究,并结合图像、点云处理等技术开发了用于核燃料组件的三维
当吊车等施工机械在架设高压电缆线的区域中工作时,由于缺少精确的测量设备,司机对施工机械顶端与高压电缆线之间距离估算可能会出现不准确的预测,从而造成较大的安全隐患。双目视觉作为计算机视觉的一个分支,在识别与测距领域有着较为广泛的应用。双目视觉采用模拟人眼的方式,通过比较左右图像的目标区域,寻找左右图像之间的匹配点,从而获取计算视差并实现对目标的测距。本文提出一种以嵌入式设备为平台,基于目标识别、图像