Models And Algorithms For Multi-constrained Graph Pattern Matching

Graph pattern matching(GPM)technology is widely used in biological data analysis,network security monitoring,social network analysis,and other fields.Traditional GPM is dedicated to finding subgraphs that are isomorphic to a given pattern graph.This type of graph structure matching is an NP-complete problem,so it is difficult to apply to social networking applications that focus more on semantic matching and large-scale data graphs.Multi-constrained graph pattern matching(MC-GPM)is well adapted to the needs of social networks for semantic matching by applying multi-attribute constraints to nodes and edges in a pattern graph.MC-GPM makes GPM more flexible,and multiple constraints on the semantics of pattern graphs can better meet the needs of precise data analysis in the era of big data.Based on the above observations,several new MC-GPM models and algorithms are proposed in this thesis.The main research contrubutions are as follows.(1)To deal with the fuzziness of some attributes in large graph data,a multi-fuzzyconstrained graph pattern matching(MFC-GPM)model is proposed.Then,a breadth-first and depth-bounded multi-constrained edge matching(MCEM)algorithm based on candidate nodes and edge topological ordering matching are designed,respectively,in an ETOF-K algorithm.Finally,by adding fuzzy constraints to the ETOF-K algorithm,an Fuzzy-ETOF-K algorithm is implemented.Experimental results show that the efficiency of the ETOF-K algorithm is significantly better than that of the existing algorithm,and a comparison between the ETOF-K algorithm and the Fuzzy-ETOF-K algorithm demonstrates the effectiveness of fuzzy constraints.(2)Aiming at the problem that the existing MC-GPM model does not consider the inedge adjacency relationship of the matching node,a multi-fuzzy-constrained strong simulation(MFCSS)matching model is proposed.By matching the predecessor and successor relationships of the candidate nodes at the same time,this model effectively excludes the candidate nodes that do not satisfy the predecessor adjacency relationship.Then,an NTSS algorithm to solve the matching model is proposed.As the efficiency of the NTSS algorithm decreases when matching a pattern graph with multiple zero-entry nodes,and MCEM performs double computation because of the local matching strategy in the existing MC-GPM algorithm,two optimization strategies are designed.Finally,an NTSS＿Inv＿Edg C algorithm that adopts the above two optimization strategies for the NTSS algorithm is implemented.Experimental results show that the NTSS algorithm is superior to the existing methods,and the efficiency of NTSS＿Inv＿Edg C is 1 to 3 orders of magnitude higher than the existing algorithm when matching different pattern graphs and datasets of different sizes.(3)As the matching subgraph obtained from MFCSS matching in the previous work contains many matching nodes,and the scale of the matching subgraph is often limited in practical applications,a GPM model with a fixed number of matching nodes in the pattern graph is proposed.A TOMP algorithm to handle the model is further proposed.Aiming at the invalid combination calculation problem of the TOMP algorithm in the process of candidate node combination matching test,and the high temporal and spatial complexity problem of existing MCEM,two optimization strategies are designed,respectively.Finally,the HTOMP algorithm that adopts the above two optimization methods for the TOMP algorithm is implemented.Experimental results show the effectiveness and efficiency of the TOMP algorithm when solving the fixed pattern node matching number problem,and the superiority of HTOMP over the TOMP algorithm on various pattern graphs.