Design And Application Of Adaptive Subgraph Matching Algorithm Based On Data Set Characteristics

In the era of big data,with the rapid development of common data networks such as social networks,a large amount of multi-source heterogeneous data will be generated every day.As a unique nonlinear data structure,graph model is very suitable for modeling massive data,and can well describe the complex internal correlation between massive data.How to analyze and mine the valuable information in the graph has become a research hotspot.Subgraph matching technology is used to search all subgraphs that can match a given query graph from a given data graph,which is a key technology to analyze and mine valuable information in the graph and has been widely used in the fields of bioinformatics,social network analysis and so on.With the continuous expansion of the scale of data graph,how to accelerate the subgraph matching process has become the main research problem.The existing subgraph matching algorithms can be divided into three steps: filtering,ordering,and enumeration.A recent study pointed out that the performance of existing algorithms in each step is closely related to the characteristics of data graph.However,the existing algorithms do not consider the impact of the characteristics of the data graph on the performance of the algorithm.To solve the above problems,this paper designs an efficient subgraph matching algorithm based on the characteristics of data set to speed up the subgraph matching process.At the same time,this paper designs a subgraph matching system,which can be applied in social network analysis,biological analysis and other scenarios,and provide convenience for users to efficiently query the subgraph matching results based on different data graphs.In addition,this system also has the functions of displaying the structure of graphs and comparing the query efficiency of different algorithms.Specifically,the research contents of this paper are summarized as follows:(1)This paper researches and analyzes the representative algorithms of subgraph matching.Through the research of existing algorithms,this paper analyzes which characteristics of data graph will affect the performance in each step of the algorithm.(2)This paper proposes a data graph preprocessing method according to the characteristic influencing factors.In the preprocessing method,the label density is defined to distinguish whether a data graph contains a large number of duplicate labels.Secondly,combined with the average degree,community structure and edge density of the graph,the graph density is defined to distinguish the sparsity of a data graph.(3)A new subgraph matching algorithm AC-Match is proposed,which can be adjusted adaptively according to the characteristics of data set.Firstly,AC-Match preprocess the data graph to obtain the label density and graph density.Secondly,according to the label density and graph density,the filtering,ordering and enumeration methods suitable for the characteristics of the data set are combined to form a new subgraph matching algorithm AC-Match which can be adjusted adaptively according to the characteristics of the data set.(4)In this paper,a large number of experiments are carried out on eight real data sets,mainly comparing the performance of AC-Match algorithm with five other representative subgraph matching algorithms in terms of matching query time and memory space.Experimental results show that the performance of AC-Match algorithm is better than other five algorithms.(5)A subgraph matching system is designed and developed in this paper.In this system,ACMatch algorithm and some other representative subgraph matching algorithms are integrated.In addition,this system realizes the functions of graph file upload,graph visualization,execution subgraph matching,matching result visualization,relevant information display and so on,so as to meet the needs of users in various fields.