【摘 要】
:
频繁子图挖掘算法作为图论研究和算法设计中的重要问题之一,其旨在寻找图中频繁出现的子图结构。频繁子图挖掘已在许多领域得到了广泛的应用,例如在社交网络、生物医学、信息
论文部分内容阅读
频繁子图挖掘算法作为图论研究和算法设计中的重要问题之一,其旨在寻找图中频繁出现的子图结构。频繁子图挖掘已在许多领域得到了广泛的应用,例如在社交网络、生物医学、信息网络等。随着近些年大数据时代的到来,数据规模不断增加,挖掘数据中的有意义的信息变得极为重要,由于频繁子图挖掘算法能挖掘出数据中频繁出现的子图结构,对研究和生产带来了巨大效益。目前由于图数据的频繁变化,传统基于静态图的频繁子图挖掘算法已不再适用,因此,针对动态图的频繁子图挖掘算法应运而生。本文深入研究了各种频繁子图挖掘算法,发现目前现存的频繁子图挖掘算法普遍面向静态图。这些算法需要对数据库进行多次扫描,对于运行时间以及运行空间的要求不高应用环境,算法尚可应用。但对于大规模动态图,算法在时间复杂度和空间复杂度上变得不再适用。针对于此,本文针对动态图上稳定频繁子图挖掘问题,提出一种基于模式增长的稳定频繁子图挖掘算法。算法引入滑动窗口技术,在滑动窗口中保存每一时刻达到的图结构,当窗口中存满图结构时,对窗口中现存的图结构进行频繁子图挖掘。算法将对窗口中的图结构产生一张DS表,根据DS表对其构建一个FP-tree,然后挖掘出所有的频繁项集。对于不连通的频繁项集修剪问题,本文提出一种基于顶点的频繁项集修剪算法,修剪掉不连通的频繁项集并得到频繁子图。对于频繁子图稳定性判断问题,本文提出一种基于连通密度的图稳定性判断方法。方法将图的稳定性判断方法嵌入到频繁子图挖掘的剪枝过程中,在判断图的稳定性时使用连通密度变化量判断图的匹配程度。由于若在各个窗口中挖掘出频繁子图是同一子图,其连通密度不会发生变化,由此得到动态图集中在短时间内稳定不变的频繁子图。通过实验与其他算法进行对比,证明本文提出的稳定频繁子图算法的有效性。
其他文献
兴国必先强师,师资是一切教育之母。当前,职业教育的发展和改革亟需一支素质高、能力强的教师队伍,而面对现实,我国的职业教育师资却存在着数量不足、质量不高,培养体系不健全等问题,成为阻碍职业教育创新发展的一大瓶颈。回溯民国时期的职业教育师资培养状况,不仅可以从历史角度追寻师资培养问题出现的根源,还可以为当代职业教育师资队伍建设提供一定的经验借鉴。清末民国时期,我国的职业教育师资培养处于萌芽阶段,政府和
深度优先搜索(DFS)是一种基本的图操作,它以深度优先的形式遍历整个图,而DFS对图G中所有节点的搜索结果是一棵生成树,称为DFS-Tree。深度优先搜索算法一直是计算机科学技术领
从文本中进行关系抽取一直是信息检索和自然语言处理的重要研究课题,二元关系抽取的研究工作已经有了相当多的成果。而多元关系也广泛存在于文本中,针对多元关系的抽取则是一
目的探讨全自动DNA定量分析检查在肺泡灌洗液中的应用价值。方法收集合格肺泡灌洗液标本386例,同时送检液基细胞学检查及全自动DNA定量分析检查,并随访病检结果、肺癌病理分
“画外求画”是对篆刻艺术领域中“印外求印”这一定义模式的借用。“印从书出”、“印外求印”的篆刻艺术观念最早从清朝中期的邓石如开始提出并且付诸实践,这使得当时从事篆刻艺术创作的人们在“印宗秦汉”之外,又多了一个强大的艺术创作的思想方法。中国历代许多取得非凡成就的画家都或得益于书法的造诣,或因书法上的给养而受益。中国绘画在石涛以后之所以没有彻底衰亡,恰好在于金石书画运动的兴起,这股学术潮流支撑着清中、
互联网+大数据+人工智能时代的到来,飞快地改变着人们的生活方式,相应地,教育也发生了革命性变革。平板电脑为教育革新提供了强大推力,逐渐成为学校现代化教学中大力推广的教
飞地研究是历史政区地理研究中的一项重要内容,历史时期飞地在现有国境内分布广泛,作为一种特殊的人文地理现象,其产生是多种因素综合作用的结果,也因此对社会政治、经济、文
车联网这一概念是物联网在智能交通上一种延伸,一种表现形式,主要是通过车辆以及其上的车载单元,路边单元等相关设备使如车辆位置,速度,ID等自身状态信息以及如交通状况,信号
传媒的飞速发展使得人们无时无刻不在接受着来自大众媒体的信息,大众媒体对人们的生活产生着举足轻重的影响,审美标准便是其中的一方面。媒体的宣传在很大程度上遵循这中国社
20世纪30年代,在《太白》杂志的倡导之下,科学小品的创作逐渐繁荣起来,引起了人们的关注和争论,茅盾、周作人、徐懋庸、傅东华等都撰文表达了自己的看法。不仅如此,30年代的