Research Of Subgraph Query Method Based On Frequent Structure In Large-scale Dynamic Graph

With the continuous advancement and development of science and technology,graph as an important data structure has been widely used in various emerging fields,such as social networks,protein interaction networks,biological information networks,intelligent transportation networks and so on.In recent years,the number of internet users has increased rapidly and network technology has developed in-depth,which leads to the growing size and dynamic changes of graph.How to manage such largescale dynamic graphs effectively has become a hot issue in the field of graph data.Subgraph query is an important graph search technique and has been widely studied because it can return query results to users more specifically.It is inefficient to process subgraph query with traditional algorithms in large-scale graph.Existing subgraph query methods improve query efficiency by creating index or graph compression.Frequent structures are frequently stable in data graph and hide a lot of useful information,and many methods index them to speed up queries.However,it is difficult to meet any query requirement and adapt to any large graph query.In addition,it has been difficult to process dynamic graph queries because of ignoring the rapid update of large graph data.This paper uses the advantage of index query and proposes a subgraph query method based on frequent structure in large-scale dynamic graph(FS-DSQ).The main research work of this paper is as follows:(1)Analyze the features of frequent structures fully,propose a rotationally symmetric frequent structure,mine the structure and corresponding subgraphs in the data graph,and establish a rotationally symmetric frequent structure index(RSFS index)to facilitate the query.Propose an incremental dynamic maintenance strategy for index.Fully consider the factors such as frequent I/O and network communication overhead,and replace the real-time update with the timing update.According to different types of changes,two dynamic maintenance strategies for vertex,edge addition and deletion are proposed,which only update the changed index items to avoid the huge overhead of global update.(2)Propose a subgraph query method in large-scale dynamic graph,including query graph decomposition and dynamic query based on RSFS index.Firstly,a query graph decomposition algorithm based on maximum decomposition principle is proposed,which gradually splits the query into a collection of the largest subset structure of the RSFS index.Then,perform subgraph optimization query and connection.Use the RSFS index to optimize the query for each decomposed structure.Using the pre-structure query sequence L and common vertex to form query constraints,constrain the post-structure's query,which filter out subgraph results quickly that do not satisfy the constraint,only leaving valid connectable subgraph result sets.Using the advantages of the rotationally symmetric structure feature,connect the intermediate results quickly to form query result.Finally,using the collected graph change operations,correct the query results dynamically to obtain the final query results.(3)This paper conducts experimental verification based on real data sets and synthetic data sets.Compared with various algorithms in terms of index creation time,storage overhead,subgraph query time and index update time,the effectiveness of FSDSQ method is proved in space and time.