基于卡方统计的近似子图匹配

作者：徐周波; 黄文文; 刘华东^*; 杨健

来源：微电子学与计算机, 2020, 37(11): 17-23.

DOI：10.19304/j.cnki.issn1000-7180.2020.11.004

• 图结构
• 近似子图匹配
• 统计显著性
• 卡方统计
• 图划分

图查询的应用越来越广泛,其中近似子图匹配是核心技术之一.但是大规模图数据中噪音的存在对近似子图匹配精确度影响较大,为进一步提高近似子图匹配算法的鲁棒性和实时性,提出一种基于卡方统计的近似子图匹配改进算法.在算法预处理阶段,利用统一邻居随机游走距离和高斯影响函数将目标图划分,使得划分后的子图在拓扑结构和标签属性之间达到最佳平衡.在算法匹配阶段,使用卡方统计量捕获的统计显著性来表征近似子图匹配结构相似度,再结合权重系数α调整结构相似度和标签相似度所占比重,其中统计显著性模型能够充分考虑背景结构和顶点邻域中的标签分布,有效处理部分标签和结构失配,从而得到最佳匹配子图.真实数据集中的实验结果表明,该算法效果较好,运算效率较高,可以应用于Top-k近似子图匹配.

• 单位
  机电工程学院; 桂林电子科技大学