基于归并聚类的并行化频繁概率子图搜索方法

摘要

本发明公开了一种基于归并聚类的并行化频繁概率子图搜索方法。本发明针对现有频繁子图搜索方法中时空消耗大、无法满足大数据环境要求等问题，首先采用节点电压法将概率子图映射为电路拓扑进行处理；然后利用归并聚类对概率子图进行聚类，有效降低时间开销；最后基于Spark框架对方法进行实现，进一步提升计算速度及可扩展性。

主权项

一种基于归并聚类的并行化频繁概率子图搜索方法，其特征在于，包括以下步骤：步骤1：预处理概率子图；首先将待处理的概率网络(概率图)，进行概率子图划分，得到指定节点个数的概率子图集，然后将这些概率子图对应的邻接矩阵存储为HDFS文件，并将所有概率子图集加载到弹性分布式数据集(Resilient Distributed Datasets,RDD)；步骤2：对每个Spark计算节点中的概率子图，将其邻接矩阵转换成对应的伴随电路，通过添加一个参考节点，并根据节点电压法，得到概率子图的节点电压序列；步骤3：对每个Spark计算节点中的概率子图均进行归并聚类计算，得到若干概率子图同构类，直到每个计算节点均收敛，将结果汇总，对汇总的概率子图同构类再进行一次归并聚类；步骤4：计算每个概率子图同构类的概率子图数量，得出频率，进而得到频繁概率子图。