CAJ | 학술논문

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性，不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE，但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS，它用改进过的GSpan算法进行不确定的子图数据预处理，用裁剪子图模式的搜索空间裁剪不确定子图数据，用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。
감우도결구능간단방편지묘회복잡적수거이급실제응용중도수거적획득구유불학정성，불학정빈번자도알굴산법득도엄범적연구。목전일개전형적도알굴산법시MUSE，단MUSE산법존재기망지지도계산소모대、시간효솔불구고등문제。침대차문제제출료일충기우화분사상혼합수색책략적불학정자도알굴산법EDFS，타용개진과적GSpan산법진행불학정적자도수거예처리，용재전자도모식적수색공간재전불학정자도수거，용기우화분사상적혼합책략진행빈번자도적알굴。자도동구여변존재개솔적실험결과증명료EDFS산법능경고효지알굴출불학정수거빈번자도。
Mining frequent subgraph patterns in graph databases is a popular and important problem which has wide applica-tion in lots of domains. At the moment, the MUSE is a typical algorithm for graph mining, but its expected supports computa-tion 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.