Research On Graph Pattern Matching Algorithm Based On Regular Expression

In the Web2.0 era,people interact with each other through social networks,spreading information in the network structure of social networks.The network structure of social network refers to the composition of the members of the network,their interactions,the state of interaction,and the relatively stable relation mode formed by this state.As the application of social network becomes more and more popular,the complexity of the relationships among the members of the network increases exponentially.The increase of the complexity of the relationship increases the difficulty of the network data mining,on the other hand,it greatly enhances the research value of the complex relationship in the social network.In this thesis,based on the graph database storage mode,the network structure of social network is analyzed deeply,the members of the network are nodes,and the different types of connections between members are pointed to the relation side.Constructing a matching model based on regular expressions,and the corresponding algorithms are given and applied successfully in the field of population research to realize the statistical query of efficient new family classification.On the basis of theoretical research,a new idea is created for the study of large population data.In this thesis,the research content mainly includes the following aspects:(1)Constructing matching model based on regular expression.Based on the Essembly social network data stored in the graph database and the matching description of regular expressions,the definition of data graph and pattern diagram is given.Then,the conceptual matching model is constructed from the structure information between nodes and the semantic information between nodes pointing to the relation side.The corresponding application model is established with the population data of real family structure.(2)A graph pattern matching algorithm based on regular expression.Based on the idea of strong simulation algorithm,the matching model constructed by regular expression matching engine is used,and the approximate optimal solution is substituted for the approximate graph matching method of the optimal solution.A graph pattern matching algorithm based on regular expression is proposed in large-scale social network data graph,and the network structure of social network is queried.(3)The feasibility of validating the algorithm with different datasets.The thesis selects three different datasets,and the experimental data are compared from the aspects of node attributes,labels and edge categories.From two aspects of accuracy and efficiency,the feasibility of the proposed graph pattern matching algorithm based on regular expression is verified experimentally.Among them,Efficiency,in the same size query pattern diagram,the algorithm is based on three data sets of query time comparison.Accuracy,select the city-level population data,the couple of core family as an example,to calculate the proportion of households and households,the proportion of household households,The results of the algorithm query are compared with those in the Population research field.(4)Applying the algorithm to the population field,conducting the family classification query.Based on the population database of Hebei Province,it discovers the kinship relation of the latent population and constructs the Kinship Network.Based on the Kinship Network,taking the core family as an example,it is found that the population number in the family structure has a certain number of relations with the number of the relationship and the family pattern,and the family structure of the same class has a certain family pattern.Using the thesis algorithm,take the core family,the core family,the second generation core family as an example,carries on the Family classification inquiry.The query results show that the family structure is gradually becoming smaller,the core family has become the main force in the family.