本技术提供了一种单个图的频繁子图挖掘方法及装置,其中,该方法包括:根据单个图的节点标签的字典排序结果生成规范邻接矩阵,并为各图节点顺序编号;通过规范邻接矩阵生成初始次优规范邻接矩阵树,叶子节点包括第一数量的边,其CSP搜索空间为其所包含节点标签对应的图节点的编号的字典排序顺序组合;依据规范邻接矩阵对叶子节点做FFSM‑Join运算或FFSM‑Extension运算,子图增长得到扩充一条边的孩子节点;以孩子节点作为候选子图,依据子图增长方式构建其CSP搜索空间;若搜索空间的有效个数小于设定支持度阈值,则将候选子图标记为无效子图;若未完成增长,继续进行子图增长,若完成子图增长,则输出频繁子图。通过上述方案能够提高频繁子图挖掘效率。
背景技术
随着大数据技术的快速发展,用图结构刻画数据逐渐应用在海量数据中。传统的大数据分析技术通常以SQL或者类SQL的表格型分析工具为基础具有相对通用的分析引擎,而海量图数据因其关系存储的复杂性和特殊性,常需专用的计算分析引擎才能实现。
图是结构的高度抽象。频繁子图挖掘是图挖掘关键技术之一,其在社交网络、情报挖掘、生物工程、通信网络优化、文本挖掘以及知识推理等多个领域具有广泛应用,如蛋白质结构分析、链接预测、敏感群体识别、图像分类等。同时,频繁子图挖掘的结果还可以作为数据分类、聚类、检索、匹配以及相似性分析的基础。
传统的频繁子图挖掘算法的复杂度较高,且大多属于单机串行算法,主要分为Apriori(关联分析)和FFSM(Fast Frequent Subgraph Mining,快速频繁子图挖掘)两大类,分别以AGM(Apriori-based Graph Mining)和gSpan(Graph-Based SubstructurePattern Mining)算法为代表。基于FFSM的算法往往要优于基于Apriori的算法,不过同时基于FFSM算法会占用更多的内存空间。
近年来,在海量图数据挖掘领域出现了以MapReduce和BSP(Bulk SynchronousParallel)为代表的频繁子图挖掘算法,这些技术以Hadoop、Spark和Flink等通用大数据存储和计算为基础,实现了在商业集群上十亿级边规模以上的频繁子图挖掘能力。
但是,现有的海量数据频繁子图挖掘算法引擎由于不是面向图计算优化的专用引擎,极大影响了频繁子图算法的挖掘效率。
实现思路