FSM——基于子图同构和结构同构的频繁子图挖掘算法

摘要

图结构挖掘已成为当前数据挖掘的研究重点之一.在文本结构分析、生物信息处理以及网络结构分析等领域图结构挖掘都有着广泛应用.频繁子图的数量通常随图的大小呈指数增长,为此人们提出了很多的解决方法,如FSG,gSpan,Closeraph.通过引入子图同构和结构同构的概念,借助贪婪搜索算法和完全级别搜索算法的思想,结合图论和频繁项目集的挖掘算法,提出了一种新的频繁子图挖掘算法--FSM(frequent subgraph mining). FSM算法降低了寻找频繁子图的复杂度,提高了图结构挖掘的效率.