期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

挖掘不确定频繁子图的改进算法的研究 被引量：2

Research of improved mining frequent subgraph patterns in uncertain graph databases
下载PDF
导出
摘要 鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。 Mining frequent subgraph patterns in graph databases is a popular and important problem which has wide application in lots of domains. At the moment, the MUSE is a typical algorithm for graph mining, but its expected supports computation costs a lot and the time efficiency is so low. So this paper proposes a method that combines classification thought with BFS thought to find frequent subgraph patterns（EDFS）. It uses improved GSpan algorithm to deal with uncertain graphs to reduce the space of subgraph patterns, then integrates classification thought with BFS thought to mine frequent subgraph patterns. The subgraph isomorphism tests and the edge whether existing tests indicate that EDFS is more efficient than MUSE.
作者 胡健 何林波 毛伊敏 杨健
机构地区 江西理工大学应用科学学院 江西理工大学信息工程学院
出处 《计算机工程与应用》 CSCD 北大核心 2015年第3期112-116,共5页 Computer Engineering and Applications
关键词 不确定图 图挖掘 频繁子图集 划分思想 混合策略 uncertain graph graph mining frequent subgraph patterns classification thought mixed algorithm
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献12

  • 1Inokuchi A,Washio T,Motoda H.An apriori-based algorithm for mining frequent substructures from graph data[C]//Zighed D A,Komorowski H J,Zytkow J M.Proc of the4th European Conf on Principles of Data Mining and Knowledge Discovery.Lyon:Springer-Verlag,2000:13-23.
  • 2Kuramochi M,Karypis G.Frequent subgraph discovery[C]//Cercone N,Lin T Y,Wu X.Proc of the 2001 IEEE Int'l Conf on Data Mining.San Jose:IEEE Computer Society,2001:313-320.
  • 3Yan X,Han J.g Span:graph-based substructure pattern mining[C]//Kumar V,Tsumoto S,Zhong N,et al.Proc of the 2002 IEEE Int'l Conf on Data Mining.Maebashi:IEEE Computer Society,2002:721-724.
  • 4Huan J,Wang W,Prins J.Efficient mining of frequent subgraphs in the presence of isomorphism[C]//Kumar V,Tsumoto S,Zhong N,et al.Proc of the 2003 IEEE Int'l Conf on Data Mining.Melbourne:IEEE Computer Society,2002:549-552.
  • 5Nijssen S,Kok J N.A quickstart in frequent structure mining can make a difference[C]//Kim W,Kohavi R,Gehrke J,et al.Proc of the 10th ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining.Seattle:ACM,2004:647-652.
  • 6Yan X,Han J.Closegraph:mining closed frequent graph patterns[C]//Getoor L,Senator T E,Domingos P,et al.Proc of the 9th ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining.Washington DC:ACM,2003:286-295.
  • 7Huan J,Wang W,Prins J,et al.Spin:mining maximal frequent subgraphs from graph databases[C]//Kim W,Kohavi R,Gehrke J,et al.Proc of the 10th ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining.Seattle:ACM,2004:581-586.
  • 8郭凌星,张德同,陈莉,李华.基于gSpan的数据筛选算法研究与应用[J].计算机应用研究,2011,28(6):2070-2072. 被引量：3
  • 9邹兆年,李建中,高宏,张硕.从不确定图中挖掘频繁子图模式[J].软件学报,2009,20(11):2965-2976. 被引量：32
  • 10张海杰,姜守旭,邹兆年.不确定图上的高效top-k近邻查询处理算法[J].计算机学报,2011,34(10):1885-1896. 被引量：8

二级参考文献53

  • 1Inokuchi A,Washio T,Motoda H.An apriori-based algorithm for mining frequent substructures from graph data//Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery(PKDD'00).Freiburg,Germany,2000:13-23.
  • 2Kuramochi M,Karypis G.Frequent subgraph discovery//Proceedings of the 2001 IEEE International Conference on Data Mining(ICDM 2001).San Jose,California,USA,2001:313-320.
  • 3Yan X,Han J.gSpan:Graph-based substructure pattern mining//Proceedings of the 2001 IEEE International Conference on Data Mining(ICDM 2002).Maebashi City,Japan,2002:721-724.
  • 4Tian Y,Hankins R A,Patel J M.Efficient aggregation for graph summarization//Proceedings of the ACM SIGMOD International Conference on Management of Data(SIGMOD 2008).Vancouver,BC,Canada,2008:567-580.
  • 5Chen Chen,Lin Cindy X,Fredrikson Matt,Christodorescu Mihai,Yan Xifeng,Han Jiawei.Mining graph patterns efficiently via randomized summaries//Proceedings of the VLDB09.Lyon,France,2009:742-753.
  • 6Yan X,Han J.Closegraph:Mining closed frequent graph patterns//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD').New York,NY,USA,2003:286-295.
  • 7Zeng Z,Wang J,Zhang J,Zhou L.FOGGER:An algorithm for graph generator discovery//Proceedings of the 12th Inter-national Conference on Extending Database Technology(EDBT 2009).Saint-Petersburg,Russia,2009:517-528.
  • 8Yan X,Cheng H,Han J,Yu P S.Mining significant graph patterns by scalable leap search//Proceedings of the SIGMOD 2008.Vancouver,BC,Canada,2008:433-444.
  • 9Ranu Sayan,Singh Ambuj K.GraphSig:A scalable approach to mining significant subgraphs in large graph databases//Proceedings of the IEEE 25th International Conference on Data Engineering(ICDE'09).Washington,DC,USA:IEEE Computer Society,2009:844-855.
  • 10Huan J,Wang W,Prins J,Yang J.SPIN:Mining maximal frequent subgraphs from graph databases//Proceedings of the SIGKDD.Seattle,WA,USA,2004:581-586.

共引文献49

同被引文献75

引证文献2

二级引证文献153

计算机工程与应用
2015年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部