一种有效的在不确定图数据库中挖掘频繁子图模式的MUSIC算法

摘要

近年来，如何在不确定图数据库中挖掘频繁子图模式得到了越来越多的关注。该问题的主要难点在于，不仅存在着海量的可能子图模式需要检验，而且还需要做大数量的子图同构性测试来判别图中是否蕴含一个给定的模式。传统的算法是利用近似算法计算子图模式的期望支持度，但计算开销仍然十分巨大。为此提供一个基于建立在不确定数据库上的索引的算法。算法首先根据apriori性质枚举所有可能的首选子图模式，然后利用索引对候选子图模式空间进行剪枝以减少子图同构性检验从而减少期望支持度的计算开销。通过在一个真实数据集上的实验显示本算法可以有效地在不确定图数据库中挖掘频繁子图模式。