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

《稳定频繁子图挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、：分类号单位代码：１０１４０密级：公开学号：４０３１５３１８９０Ａ聲（￡￥ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ中文题目：稳定频繁子图挖掘算法研究英文题目：ＳｔｕｄｙｏｎＳｔｅａｄｙＦｒｅｑｕｅｎｔＳｕｂｇｒａｐｈＭｉｎｉｎｇＡｌｇｏｒｉｔｈｍ论文作者：闫靓指导教师：李晓光教授专业：计算机软件与理论完成时间二○一八年五月：０申请辽宁大学硕士学位论文稳定频繁子图挖掘算法研究Studyonsteadyfrequentsubgraphminingalgorithm作者：闫

2、靓指导教师：李晓光教授专业：计算机软件与理论答辩日期：2018年5月22日二○一八年五月·中国辽宁辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体己经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研宄做出重要贡献的个人和集体均己在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承Ｊ学位论文作者签名：丨年Ｘ月曰＾学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关

3、部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权辽宁大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以釆用影印、缩印或扫描等复制手段保存和汇编学位论文Ｄ同时授权中国学术期刊（光盘版《）电子杂志社将本学位论文收录到中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理。（）：保密，在年后解密适用本授权书。（保密请在括号＿“内划厂）授权人签名：指导教师签名：Ｉ尊？■曰期？Ｗ年＾曰曰期．

4、＃年Ｔ月曰＾＾摘要摘要频繁子图挖掘算法作为图论研究和算法设计中的重要问题之一，其旨在寻找图中频繁出现的子图结构。频繁子图挖掘已在许多领域得到了广泛的应用，例如在社交网络、生物医学、信息网络等。随着近些年大数据时代的到来，数据规模不断增加，挖掘数据中的有意义的信息变得极为重要，由于频繁子图挖掘算法能挖掘出数据中频繁出现的子图结构，对研究和生产带来了巨大效益。目前由于图数据的频繁变化，传统基于静态图的频繁子图挖掘算法已不再适用，因此，针对动态图的频繁子图挖掘算法应运而生。本文深入研究了各种频繁子图挖掘算法，发现目前现存的频繁子图挖掘算法普遍面向静态图。这些算法需要对数据库进行多次扫描，

5、对于运行时间以及运行空间的要求不高应用环境，算法尚可应用。但对于大规模动态图，算法在时间复杂度和空间复杂度上变得不再适用。针对于此，本文针对动态图上稳定频繁子图挖掘问题，提出一种基于模式增长的稳定频繁子图挖掘算法。算法引入滑动窗口技术，在滑动窗口中保存每一时刻达到的图结构，当窗口中存满图结构时，对窗口中现存的图结构进行频繁子图挖掘。算法将对窗口中的图结构产生一张DS表，根据DS表对其构建一个FP-tree，然后挖掘出所有的频繁项集。对于不连通的频繁项集修剪问题，本文提出一种基于顶点的频繁项集修剪算法，修剪掉不连通的频繁项集并得到频繁子图。对于频繁子图稳定性判断问题，本文提出一种基于连通密

6、度的图稳定性判断方法。方法将图的稳定性判断方法嵌入到频繁子图挖掘的剪枝过程中，在判断图的稳定性时使用连通密度变化量判断图的匹配程度。由于若在各个窗口中挖掘出频繁子图是同一子图，其连通密度不会发生变化，由此得到动态图集中在短时间内稳定不变的频繁子图。通过实验与其他算法进行对比，证明本文提出的稳定频繁子图算法的有效性。关键字：动态图，频繁子图挖掘算法，滑动窗口，图稳定性IAbstractABSTRACTFrequentsubgraphminingalgorithmisoneoftheimportantproblemsingraphtheoryresearchandalgorithmdesig

7、n,whichisaimedtofindthesubgraphstructurefrequentlyappearinginthegraph.Frequentsubgraphmininghasbeenwidelyusedinmanyfields,suchassocialnetwork,biomedicine,informationnetwork,etc.Withthearrivaloftheeraofbigdatainrecentye