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

最大频繁子图挖掘算法研究 被引量：2

Research on the Mining Algorithms for Maximal Frequent Subgraphs
下载PDF
导出
摘要 随着图的广泛应用,图的规模不断扩大,因此提高频繁子图挖掘效率势在必行。本文针对频繁子图挖掘所产生的庞大的结果集,提出了一个最大频繁子图挖掘算法MFME,从而极大地减少了结果集的数量。MFME使用了映射的思想将图集中的边映射到边表中并在此表上进行子图挖掘,有效地提高了算法的效率。实验结果表明,MFME的效率较经典算法SPIN有明显提高。 With the extensive application of graphs, their sizes are expanding unceasingly. Therefore it is imperative to improve the efficiency of mining the frequent subgraphs. According to the huge number of possible subgraphs, this paper proposes an algorithm MFME for mining maximal frequent subgraphs, which greatly reduces the number of the subgraph sets. The algorithm MFME which is based on the idea of mapping focuses on mapping the edge from the graph set to the edge table and it improves the efficiency of the algorithm effectively. The experimental results show that MFME is more efficient than algorithm SPIN.
作者 李继腾 骆志刚 丁凡 田文颖 赵琦
机构地区 国防科技大学计算机学院
出处 《计算机工程与科学》 CSCD 北大核心 2009年第12期67-70,共4页 Computer Engineering & Science
基金 国家863计划资助项目(2007AA01Z106) 国家自然科学基金资助项目(60673018)
关键词 数据挖掘 频繁子图 子图同构 映射树 data mining frequent subgraphs subgraphs isomorphism mapping tree
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献10

  • 1李先通,李建中,高宏.一种高效频繁子图挖掘算法[J].软件学报,2007,18(10):2469-2480. 被引量：35
  • 2Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules[C]//Proc of VLDB' 94,1994 : 487-499.
  • 3Inokuchi A, Washio T, Okada T. An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data [C] //Proc of PKDD'00,2000 : 13-23.
  • 4Inokuchi A, Washio T, Okada T, et al. Applying Algebraic Mining Method of Graph Substructures to Mutageniesis Data Analysis[C]//Proc of PAKDD' 00,2000 : 87-92.
  • 5Kuramochi M, Karypis G. Frequent Subgraph Discovery[C] //Proc of ICDM' 01,2001 : 313-320.
  • 6Yah Y, Han J. gSpan: Graph--Based Substructure Pattern Mining[C]//Proc of ICDM'02,2002.
  • 7Yan X, Han J. CloSeGraph:Mining Closed Frequent Graph Patterns[C]//Proc of the 9th ACM SIGKDD Int' l Conf on Knowledge Discovery and Data Mining, 2003 : 286-295.
  • 8Han J, Wang W, Prins J. Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism[C]//Proc of the IEEE Int'l Conf on Data Mining, 2003:549-552.
  • 9Huan J, Wang W, Prins J, et al. Spin: Mining Maximal Frequent Subgraphs from Graph Databases [C] // Proc of KDD' 04, 2004 : 581-586.
  • 10Thomas L, Valluri S, Karlapalem K. MARGIN.. Maximal Frequent Subgraph Mining [C]//Proc of ICMD ' 06,2006 : 109-1101.

二级参考文献17

  • 1Borgelt C, Berhold MR. Mining molecular fragments: Finding relevant substructures of molecules. In: Proc. of the ICDM 2002. 2002. http://www.wi-lab.condicdm02/
  • 2Holder LB, Cook D J, Djoko S. Substructures discovery in the subdue system. In: Proc. of the AAAI'94 Workshop Knowledge Discovery in Databases. 1994. 169-180.
  • 3Inokuchi A, Washio T, Okada T, Motoda H. Applying algebraic mining method of graph substructures to mutageniesis data analysis. In: Proc. of the PAKDD. 2000. http://www.informatik.nni-trier.de/-ley/db/conf/pakdd/pakdd2000.html
  • 4Inokuchi A, Washio T, Okada T. An apriori-based algorithm for mining frequent substructures from graph data. In: Proc. of the PKDD 2000. LNAI 1910, 2000. 13-23. http://eric.univ-lyon2.fr/-pkdd2000/
  • 5Kuramochi M, Karypis G. Frequent subgraph discovery. In: Proc. of the ICDM 2001. 2001. http://www.cs.york.ac.uk/arch/neural/ Conferences/ICDM2001 .html
  • 6Yan Y, Han J. gSpan: Graph-Based substructure pattern mining. In: Proc. of the 2002 Int'l Conf. on Data Mining (ICDM 2002). Maebashi, 2002. http://www.wi-lab.com/icdm02/
  • 7Washio T, Motoda H. State of the art of graph-based data mining. In: Proc. of the SIGKDD 2003. http://www.sigkdd.org/kdd2003/
  • 8Yan X, Han J. CloseGraph: Mining closed frequent graph patterns. In: Proc. of the 9th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD2003). Washington, 2003. http,://www.sigkdd.org/kdd2003/
  • 9Han J, Wang W, Prins J. Efficient mining of frequent subgraphs in the presence of isomorphism. In: Proc. of the IEEE Int'l Conf. on Data Mining (ICDM 2003), 2003. http://www.cs.sjsu,edu/faculty/tylirdicdm2003_workshop.htm
  • 10Jin R, Wang C, Polshakov D, Parthasarathy S, Agrawal G. Discovering frequent topological structures from graph datasets. In: Proc. of the KDD 2005. Chicago, 2005. 606-611. http://www.sigkdd.org/kdd2005/

共引文献34

同被引文献83

  • 1第32次中国互联网络发展状况统计报告[R].中国互联网络信息中心,2013(7).
  • 2Giugno R, Shasha D. GraphGrep:a fast and universal method for querying graphs [ C ]//Proc of 16th international confer- ence on pattern recognition. [ s. 1. ] : IEEE,2002 : 112-115.
  • 3Yau Xifeng, Yu P S, Han Jiawei. Graph indexing: a frequent structure-based approach [ C ]//Proc of the 2004 ACM SIG- MOD international conference on management of data. New York, NY, USA: ACM,2004:335-346.
  • 4Agrawal R, Borgida A, Jagadish H V. Efficient management of transitive relationships in large data and knowledge bases [C]//Proc of the ACM SIGMOD international conference on management of data. [ s. 1. ] : [ s. n. ], 1989:253-262.
  • 5Tri[31 S, Loser U. Fast and practical indexing and querying of very large graphs [ C ]//Proc of the ACM SIGMOD internation- al conference on management of data. [ s. 1. ] : [ s. n. ] ,2007 : 845 -856.
  • 6Samet H, Sankaranarayanan J, Alborzi H. Sealable network distance browsing in spatial databases [ C ]//Proe of the ACM SIGMOD international conference on management of data. Vaneouver: [ s. n. ] ,2008:43-54.
  • 7Xiao Yanghua, Wu Wentao, Pei Jian, et al. Efficiently indexing shortest paths by exploiting symmetry in graphs [ C ]//Proe of 12th international conference on extending database technolo- gy. Saint Petersburg : [s. n. ] ,2009:493-504.
  • 8Zou Lei, Chen Lei, Ozsu M T. Distance-join: pattern match query in a large graph database [ C ]//Proc of VLDB. [ s. 1. ] : [ s. n. ] ,2009:886-897.
  • 9Shang Haichuan, Zhang Ying, Lin Xuemin, et al. Taming veri- fication hardness :an efficient algorithm for testing sub-graph isomorphism[ C]//Proc of VLDB. [ s. 1. ]: [ s. n. ] ,2008:364 -375.
  • 10Chen C, Lin C X, Fredrikson M, et al. Mining graph patterns efficiently via randomized summaries [ C ]//Proc of VLDB. [ s. 1. ] : [ s. n. ] ,2009:742-753.

引证文献2

二级引证文献8

计算机工程与科学
2009年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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