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

发布时间：2023-05-13 19:04

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

【文章页数】：7 页

【文章目录】：
1 引言
2 知识背景
3 IMVELSET算法
    3.1 预处理
        3.1.1 图分区算法
        3.1.2 创建索引列表
    3.2 统计显著性计算
        3.2.1 节点对的构建
        3.2.2 统计显著性计算
            (1)标签元组的产生
            (2)标签重叠度的计算
            (3)期望标签重叠度
            (4)卡方值的计算
    3.3 近似匹配结果的产生
4 实验结果及分析
    4.1 实验准备
    4.2 精确度和运算效率指标的评测实验及分析
    4.3 参数的影响
5 结束语



本文编号：3816327