主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李先通,李建中,高宏.一种高效频繁子图挖掘算法.软件学报,2007,18(10):2469-2480
一种高效频繁子图挖掘算法
An Efficient Frequent Subgraph Mining Algorithm
投稿时间:2006-09-08  修订日期:2006-09-08
DOI:
中文关键词:  频繁模式挖掘  子图同构  子树同构  频繁子树  生成树
英文关键词:frequent pattern mining  subgraph isomorphism  subtree isomorphism  frequent subgraph  spanning tree
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60473075, 60773063 (国家自然科学基金); the Key Program National Natural Science Foundation of China under Grant No.60533110 (国家自然科学基金重点项目); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University (NCET) under Grant No.NCET-05-0333 (新世纪优秀人才支持计划)
作者单位
李先通 哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001 
李建中 哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001 
高宏 哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001 
摘要点击次数: 4011
全文下载次数: 4446
中文摘要:
      由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n3·2n),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2n·n2.5/logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.
英文摘要:
      With the successful development of frequent item set and frequent sequence mining,the technology of data mining is natural to extend its way to solve the problem of structural pattern mining—Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry,biology,computer networks,and World-Wide Web. This paper proposes a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm available,the complexity is O(n3·2n),n is the number of frequent edges in a graph dataset. The complexity of GraphGen is O〔2n·n2.5/logn〕,which is improved O(√n·logn) times than the best one. Experimental results prove this theoretical analysis.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利