单图中子图大小相关的近似频繁子图挖掘

发布时间：2020-05-17 21:09

【摘要】：图数据是大数据时代中十分重要的角色,其在各种场景中有着十分广泛的应用,如社交网络、蛋白质交互网络、合作关系网络等。本文主要研究的是图数据上的模式挖掘,研究目的是实现从图数据中挖掘频繁近似子图。目前在频繁子图挖掘领域的工作已经有很多,然而已有的工作要么没有考虑子图与其出现的相似程度,要么在考虑相似程度时忽略了候选子图大小对相似程度的影响。然而,根据人的感知,不同大小的图应具有不同程度的容错性,类似的,子图的大小对计算子图与其出现的相似程度也会有十分重要的影响。因此,本文设计了子图大小相关的频繁近似子图挖掘策略,提出了一种新的、快速的频繁近似子图挖掘算法。算法不仅在计算子图的频繁程度时考虑与子图的近似出现,同时在计算子图与其出现的相似程度时,考虑子图的大小对近似程度的影响。首先,对于候选频繁近似子图的生成,本文设计了一种不遗漏的遍历方式,遍历给定单图的全部子图。为了提高遍历的效率,降低候选频繁近似子图的数量,对频繁近似子图的大小上限进行了估算,并利用大小上限过滤遍历中的子图,对遍历过程进行剪枝。实验证明了子图的上限对遍历效率具有提升效果。其次,为提高算法效率,本文归纳出对于所有的频繁近似子图,其支持度符合“局部反单调性”,且在文中给出了证明。并利用该性质,设计了对候选频繁近似子图进行剪枝的策略,降低了需要进行近似匹配的候选子图的数量。实验证明,该性质对可以显著提升算法效率。再次,对于候选频繁近似子图的近似子图生成,本文设计了基于点和边的删除策略的近似子图生成算法。并通过理论证明,仅通过统计该算法产生的近似子图在给定图中的匹配,并计算这些匹配的支持度,可以得到与统计候选频繁近似子图的所有近似匹配相同的支持度。接着,通过与已有算法的实验对比,证明本文算法在效率上具有明显优势,同时,通过简单案例说明,本文算法能发现传统频繁子图挖掘算法无法发现的频繁子图,进一步表明在挖掘频繁子图时考虑近似关系,与子图大小对近似程度的影响的必要性。最后,修改本文算法,提出了针对频繁闭合近似子图和频繁极大近似子图的挖掘算法,提高了本文研究的完整性,扩展了算法应用场景,并通过实验证明了两种算法的有效性。
【图文】：

华东师范大学硕士学位论文殊性，用于表达实体间的关系十分方便，因此实体间的关系的表达通常用图结构表示。如图 1-1 所示的 PPI(Protein-ProteinInteraction)[8]，其中每个点表示一种蛋白质，每条边表示蛋白质之间的交互关系，从中挖掘频繁的蛋白质交互关系网络就是频繁子图挖掘的一种。图数据又分为不同的种类，如不确定图，标签图等，本文的主要研究对象为点和边都具有标签的标签图，其中点和边上的标签表示的

为证明本文候选子图剪枝策略的有效性，本文设计实验，对 DP、DP-L 以-LT 三种生成算法进行对比。实验设置频繁程度阈值 7，近似程度阈值，结果如下：由于算法效率差距过大，，因此我们将效率对比展示在两个图中，图中横坐示给定图数据中点的数量，纵坐标表示算法消耗的时间，两个图中横坐标的为 250 的点表示的是算法在真实数据中的效率，图 6-1 展示了 DP-L 算法-LT 算法的效率对比，可以看出，随着图规模的增大，两种算法的效率都在，消耗的时间上升，同时，DP-L 算法与 DP-LT 算法消耗的时间差距也逐渐，表示随着图规模的增大，DP-L 算法时间成本上升更快。这是因为随着图的增大，子图数量呈指数上升，由于 DP-LT 算法采用了基于频繁近似子图上限的早停机制，降低了产生的候选子图的数量，同时，随着自图数量的上升图 6-1 DP-L 与 DP-LT 算法效果对比
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O157.5;TP311.13

【相似文献】

相关期刊论文 前10条

1 苑春佼;;《吉祥多子图》临摹[J];大众文艺;2018年10期

2 鲁宗贵;;吉祥多子图页[J];中国书画;2018年09期

3 印安涛;钱钢;施欢欢;;在复杂网络中查找k个有限重叠的密集子图[J];计算机应用与软件;2016年12期

4 鲁宗贵;;吉祥多子图[J];文艺研究;2017年03期

5 梁瑶;;吉祥多子图[J];美与时代(中);2017年06期

6 鲁宗贵;;《吉祥多子图》[J];老年教育(书画艺术);2016年01期

7 王苗苗;;《吉祥多子图》[J];明日风尚;2016年08期

8 周姗;;《吉祥多子图》[J];参花(上);2016年06期

9 杨利民;图K_n~k和C_n~t的理想子图的计数[J];大理师专学报(自然科学版);1995年01期

10 陈赐平;;带亏数的[1,n]-子图[J];北京农业工程大学学报;1987年03期

相关会议论文 前9条

1 刘桂珍;徐周波;;最大公共子图问题的约束符号求解技术[A];广西计算机学会2016年学术年会论文集[C];2016年

2 徐以凡;;层分解和子图识别问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

3 吴卫江;李国和;;Apriori算法思想在频繁子图挖掘中应用的研究[A];第六届全国信息获取与处理学术会议论文集（2）[C];2008年

4 陶剑文;丁佩芬;赵杰煜;;csgIndex:一种可扩展的对比子图索引模型[A];第二十七届中国控制会议论文集[C];2008年

5 陈荣斯;;非正则冠状系统[A];面向21世纪的科技进步与社会经济发展（上册）[C];1999年

6 吴颖华;周皓峰;袁晴晴;洪铭胜;汪卫;施伯乐;;Topology:一个快速的频繁连通子图的挖掘算法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

7 韩璐;王朝坤;阮文静;欧晓平;仇萍;;基于MapReduce的不确定子图查询处理[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

8 周杨;王峰;;FSM——基于子图同构和结构同构的频繁子图挖掘算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

9 张丽丽;殷兆麟;张爱娟;王竹晓;;以结点为中心的WordNet子图的可视化[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

相关重要报纸文章 前1条

1 王圣立;“五子图”罐再现成化风彩[N];中国商报;2003年

相关博士学位论文 前10条

1 买吐肉孜·买司地克（Metrose Metsidik）;带子图及其部分对偶若干性质的刻画[D];厦门大学;2017年

2 蔺厚元;禁用子图与图的哈密尔顿性[D];华中师范大学;2012年

3 李斌龙;重子图条件下图的Hamilton性及相关问题[D];西北工业大学;2016年

4 毛玲;基于层次因子图的心电图自动诊断方法研究[D];国防科学技术大学;2009年

5 崔庆;Tutte子图方法及其应用[D];南开大学;2009年

6 邹磊;图数据库中的子图查询算法研究[D];华中科技大学;2009年

7 崔耀祖;基于复杂网络边的密度探索社团结构算法研究[D];大连理工大学;2016年

8 吴云建;一致星因子图与笼的连通性[D];南开大学;2009年

9 马登举;曲面的极小禁用子图与图的亏格[D];华东师范大学;2011年

10 石海佳;基于复杂网络的产业生态系统结构复杂性研究[D];清华大学;2015年

相关硕士学位论文 前10条

1 黄子扬;图在点度数限制下的大导出子图[D];中国科学技术大学;2019年

2 窦建凯;单图中子图大小相关的近似频繁子图挖掘[D];华东师范大学;2019年

3 黄睿智;不确定图下的稠密子图挖掘研究[D];浙江工业大学;2018年

4 闫靓;稳定频繁子图挖掘算法研究[D];辽宁大学;2018年

5 刘钟凌;顶点加权图的最密集子图算法设计与实现[D];广州大学;2018年

6 邹艳梅;关于图的Hamilton性的禁用子图条件[D];华东师范大学;2018年

7 姜丽雁;大规模动态有向标签图子图查询方法研究[D];辽宁大学;2018年

8 陈科第;基于频繁子图模式挖掘的群体性抗议事件检测技术研究[D];国防科学技术大学;2016年

9 李新锋;知识图谱中子图查询技术研究[D];华中科技大学;2017年

10 张迎;面向大图数据的子图相似匹配算法研究与实现[D];东北大学;2015年

本文编号：2669184