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

徐周波; 黄文文; 刘华东; 杨健

Chinese

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-09-04

- 基于卡方统计的近似子图匹配
- Approximate subgraph matching based on Chi-squares statistics
- 微电子学与计算机 2020年37卷第11期页码：17-23
- 作者机构：
  
  1. 桂林电子科技大学广西可信软件重点实验室机构,广西,桂林,541004
  2. 桂林电子科技大学机构机电工程学院,广西,桂林,541004
- 作者简介：
- 基金信息：
  
  国家自然科学基金 61762027国家自然科学基金 U1501252广西自然科学基金 2017GXNSFAA198172
- DOI：
  中图分类号：
- 纸质出版：2020
- 稿件说明：
移动端阅览
徐周波, 黄文文, 刘华东, 杨健. 基于卡方统计的近似子图匹配[J]. 微电子学与计算机, 2020, 37(11): 17-23.

XU Zhou-bo, HUANG Wen-wen, LIU Hua-dong, et al. Approximate subgraph matching based on Chi-squares statistics[J]. 2020, 37(11): 17-23.
徐周波, 黄文文, 刘华东, 杨健. 基于卡方统计的近似子图匹配[J]. 微电子学与计算机, 2020, 37(11): 17-23. DOI：

XU Zhou-bo, HUANG Wen-wen, LIU Hua-dong, et al. Approximate subgraph matching based on Chi-squares statistics[J]. 2020, 37(11): 17-23. DOI：

摘要

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

Abstract

Graph query is more and more widely used

and approximate subgraph matching is one of the core technologies. However

the existence of noise in large-scale graph data has a great impact on the accuracy of approximate subgraph matching. In order to further improve the robustness and real-time performance of approximate subgraph matching algorithm

an improved algorithm of approximate subgraph matching based on Chi-square statistics is proposed. In the preprocessing stage

the target graph is partitioned by using the Unified Neighborhood Random Walk Distance and Gaussian Influence Function

so that the partitioned subgraph can achieve the best balance between the topological structure and label attributes.In the algorithm matching stage

the statistical significance captured by Chi-square statistics is used to characterize the subgraph similarity of approximate subgraph matching

and then the proportion of structural similarity and label similarity is adjusted by combining the weight coefficient α. The statistical significance model can takes into account the background structure and label distribution in the neighborhood of vertices

and effectively handles partial label and structural mismatches

so as to get the best matching subgraph. The experimental results in real dataset show that the algorithm is effective and efficient

and can be applied to Top-k approximate subgraph matching.

关键词

Keywords

references

TIANYY, PATELJM. TALE: atoolforapproximatelargegraphmatching[C]//Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Cancun, Mexico: IEEE, 2008: 963-972.

ARORA A, SACHAN M, BHATTACHARYA A. Miningstatis-tically significant connectedsubgraph sinvertexlabeled-graphs[C]//Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. Snowbird: ACM, 2014: 1003-1014.

GLOVER F. Tabusearch-PartI[J]. ORSA Journal on Computing, 1989, 1(3): 135-206. DOI: 135

KHAN A, LI N, YANX F, et al. Neighborhoodbased-fastgraphsearchinlargenetworks[C]//Proceedings of 2011 ACMSIGMO DInternational Conferenceon Management of Data. Athens, ACM, 2011: 901-912.

DUTTA S, NAYEK P, BHATTACHARYA A. Neighbor aware search for approximate labeled graphmatching using the chisquarestatistics[C]//Proceedings of the 26th International Conference on WorldWideWeb.Perth: ACM, 2017: 1281-1290.

SUCHANEK F M, KASNECI G, WEIKUM G. Yago: aco-reofsemantic knowledge[C]//Proceedings of the 16th International Conference on World Wide Web. Banff: ACM, 2007: 679-706.

America READT R C, CRESSIE A C. Goodess of fitstatistics for discrete multivariate data[M]. America: Springer, 1989: 4617-4578. DOI: 4617

ZHU L H, NGW K, CHENG J. Structureandattributeindexfo-rapproximategraphmatchinginlargegraphs[J]. Information-Systems, 2011, 36(6): 958-972. DOI: 958

DUTTA S, BHATTACHARY A A. Most significantsubstringmining based on chisquaremeasure[C]//Proceedings of 14th Pacific-Asia Conference Knowledge Discovery and Data Mining.Hyderabad: Springer, 2010: 21-24.

CHENG H, ZHOU Y, YU J X. Clusteringlargeattributedgraphs: a balance between structural and attribute similarities[J]. ACM Transactionson Knowledge Discovery from Data, 2015: 5(2): 12. DOI: 12

ELMSALLATI A, CLARK C, KALITA J. Globalalignmentof-protein-proteininteractionnetworks: asurvey[J]. IEEE/ACMTransactionsonComputationalBiologyandBioinformatics, 2016, 13(4): 689-705. DOI: 689

KPODJEDO S, GALINIER P, ANTONIOL G. Using loca lsimilarity measures to efficiently address approximate graph matching[J]. Discrete Applied Mathematics, 2014(164): 161-177. DOI: 161

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于监控指标关联性的微服务异常检测

基于多尺度融合与小目标增强的航拍车辆检测算法

注意力机制与改进密集卷积引导的信息隐藏模型

AlN/GaN混合缓冲层双异质结p-GaN HEMT直流特性仿真

超低功耗实时时钟电路的设计