Top-k Subgraph Similarity Queries Over Uncertain Graphs

In recent years, the graph structure is widely used in the field of bio-informatics and social networks and all kinds of external factors interfere with the obtained data, so researchers have great interests in the uncertain graphs. At the meantime, as one of the fundamental research problems in graphs, subgraph similarity query has attracted significant research attention for all applications. Researchers have designed and implemented a number of algorithms to process the subgraph similarity search in which a query graph is given to certain graphs. However, if the query graphs are uncertain or the query results are Top-k, people didn’t have enough attention to them and it has become a great challenge.In view of the above problems, this paper focuses on the studies of Top-k subgraph similarity search over uncertain graph.First, this paper considers the case that data graph is a large uncertain graph in which all edges are independent. The query graph is also an uncertain graph which is an induced subgraph of data graph. After that, this paper defines the problem of Top-k subgraph similarity searching over a large uncertain data graph and proposes an efficient algorithm to solve this problem based on possible world model. Efficient pruning methods are developed to further improve the efficiency of our algorithm, such as creating optimized indexes for vertices according to the probability relationship between vertex and the vertex structure properties, preprocessing the database to narrow down the subgraph matching range based on the clustering partition. According to the relationship of each matching edge and edit distance, the evaluation model is improved to avoid numerating all possible world for calculating the probability. It poses the pruning process based on threshold and pruning according to the requirement of the Top-k. Extensive experimental evaluation proves that our algorithm and pruning methods have high efficiency.Besides, this paper considers the case that data graph and query graph are all uncertain in which all edges are correlated. Therefore, this paper improve the issues raised above and define the problem of Top-k subgraph similarity search over uncertain graph with correlated edges. Considering the relationship between the edges, a new indexing method has been further proposed. Also, this paper dynamically generates substructures and prunes the search space by the new upper-bound of probability. The experiments based on real and synthetic datasets to evaluate the efficiency of our algorithm and pruning methods.In summary, considering the uncertainty of the data graph in real application, this paper raises problems of Top-k subgraph similarity search over uncertain graphs or uncertain graph with correlated edges. This paper makes a research about how to solve these problems based on dynamic subgraph queries. It paves the way for the future works about Top-k subgraph similarity search problem.