稳定频繁子图挖掘算法研究

发布时间：2020-04-12 03:12

【摘要】：频繁子图挖掘算法作为图论研究和算法设计中的重要问题之一,其旨在寻找图中频繁出现的子图结构。频繁子图挖掘已在许多领域得到了广泛的应用,例如在社交网络、生物医学、信息网络等。随着近些年大数据时代的到来,数据规模不断增加,挖掘数据中的有意义的信息变得极为重要,由于频繁子图挖掘算法能挖掘出数据中频繁出现的子图结构,对研究和生产带来了巨大效益。目前由于图数据的频繁变化,传统基于静态图的频繁子图挖掘算法已不再适用,因此,针对动态图的频繁子图挖掘算法应运而生。本文深入研究了各种频繁子图挖掘算法,发现目前现存的频繁子图挖掘算法普遍面向静态图。这些算法需要对数据库进行多次扫描,对于运行时间以及运行空间的要求不高应用环境,算法尚可应用。但对于大规模动态图,算法在时间复杂度和空间复杂度上变得不再适用。针对于此,本文针对动态图上稳定频繁子图挖掘问题,提出一种基于模式增长的稳定频繁子图挖掘算法。算法引入滑动窗口技术,在滑动窗口中保存每一时刻达到的图结构,当窗口中存满图结构时,对窗口中现存的图结构进行频繁子图挖掘。算法将对窗口中的图结构产生一张DS表,根据DS表对其构建一个FP-tree,然后挖掘出所有的频繁项集。对于不连通的频繁项集修剪问题,本文提出一种基于顶点的频繁项集修剪算法,修剪掉不连通的频繁项集并得到频繁子图。对于频繁子图稳定性判断问题,本文提出一种基于连通密度的图稳定性判断方法。方法将图的稳定性判断方法嵌入到频繁子图挖掘的剪枝过程中,在判断图的稳定性时使用连通密度变化量判断图的匹配程度。由于若在各个窗口中挖掘出频繁子图是同一子图,其连通密度不会发生变化,由此得到动态图集中在短时间内稳定不变的频繁子图。通过实验与其他算法进行对比,证明本文提出的稳定频繁子图算法的有效性。
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13;O157.5

【参考文献】

相关期刊论文 前7条

1 李亮;陈莉;李华;王珊珊;张敏超;;一种改进的频繁子图挖掘算法[J];计算机与应用化学;2014年02期

2 于戈;谷峪;鲍玉斌;王志刚;;云计算环境下的大规模图数据处理技术[J];计算机学报;2011年10期

3 杨路明;刘立新;毛伊敏;谢东;;数据流中基于滑动窗口的最大频繁项集挖掘算法[J];计算机应用研究;2010年02期

4 李继腾;骆志刚;丁凡;田文颖;赵琦;;最大频繁子图挖掘算法研究[J];计算机工程与科学;2009年12期

5 邹兆年;李建中;高宏;张硕;;从不确定图中挖掘频繁子图模式[J];软件学报;2009年11期

6 唐懿芳;穆志纯;张师超;钟达夫;;挖掘数据流频繁模式的相关技术和算法研究综述[J];计算机工程与应用;2009年26期

7 刘学军;徐宏炳;董逸生;钱江波;王永利;;基于滑动窗口的数据流闭合频繁模式的挖掘[J];计算机研究与发展;2006年10期

相关博士学位论文 前2条

1 杨雅君;动态图数据挖掘与查询算法的研究[D];哈尔滨工业大学;2013年

2 曹永昌;图的稳定性的相关研究[D];中国科学技术大学;2009年

相关硕士学位论文 前1条

1 齐彩霞;基于图编辑距离的图匹配算法研究[D];西安建筑科技大学;2013年

，

本文编号：2624204