篇名 | HLMA: An Efficient Subgraph Matching Algorithm |
---|---|
卷期 | 31:6 |
作者 | Gang Dai 、 Baomin Xu 、 Hongfeng Yin |
頁次 | 182-195 |
關鍵字 | graph query 、 label propagation 、 subgraph matching 、 vertex alignment 、 EI 、 MEDLINE 、 Scopus |
出刊日期 | 202012 |
DOI | 10.3966/199115992020123106015 |
Graph mining is of great significance for social network analysis, biological research and other information applications. One interesting but challenging problem of graph mining is subgraph matching. Most of the existing subgraph matching algorithms have not considered both accuracy and efficiency. In this paper, we propose an approximation algorithm for subgraph matching in a large undirected graph. The basic idea is to convert the vertices of the graph into a data structure h-list based on label propagation. According to h-list, we can find a candidate matching set for each query vertex by searching on the target graph. To obtain optimal matching results, we present a scoring metrics to measure the similarity between a query vertex and each vertex of its candidate matching set. The whole algorithm is called HLMA (H-List Matching Algorithm). The experimental results show that HLMA has higher efficiency and matching accuracy, while computational processing of complex subgraph isomorphism can be avoided.