图结构聚类对管理和分析图数据来说十分重要。SCAN聚类算法作为一个有效的图聚类算法,被广泛用于许多不同的图形应用程序中以发现有意义的集群,如社交网络、信息网络、协作网络、电子商务网络、通信网络、生物蛋白质网络等。但是,由于图数据中存在一些脏数据,如图数据中缺少一些边,这使得图数据经过SCAN聚类算法后的聚类结果不能满足用户的要求,例如期望的聚类中缺少期望的结点。针对这样的现象,用户就会提出为什么现有的图结构聚类方法没有返回他们想要的结果,以及如何做才能使得期望结点出现在聚类结果中,这类问题被称为why-not问题。解决why-not问题的根本目的,就是为聚类结果中的缺失结点找到合理的解释,这不仅能够帮助用户更好地理解聚类结果,还能够提高图数据库的质量和可用性。为了解决这一问题,首先,本文提出了一种有效的溯源解释模型。溯源解释模型通过数据修改的方式,来解释为什么期望结点没有出现在期望簇中,以及如何通过修改原始图数据集的方式,使期望结点能够出现在对应的期望簇中。在此研究思路下,本文首先分析了 SCAN算法的聚类原理,并在此基础上提出了统一的why-not问题解释框架。同时,为了在新的聚类结果中最大化地保留原来的聚类结果,本文提出了一种代价模型,定义了代价函数来量化溯源解释的代价。其次,本文提出了两种解释算法,why-not问题基础解释算法和why-not问题改进解释算法。本文的解释算法通过构建剪枝策略、定义代价函数的方法,以最小的代价来修改原始图数据集,使期望结点出现在期望簇中。最后,本文在真实数据集上进行了大量实验研究,实验结果表明本文的方法可以有效地解释聚类结果的期望结点。本文通过理论分析以及实验的验证,体现了算法的高效性和稳定性。