Research On Proximity Query And Proximity Pattern Mining Algorithms On Uncertain Graphs

The uncertainty of graph data is widely existed in practice, researching on efficient query processing algorithms and mining interesting patterns on uncertain graphs have significant meanings. An uncertain graph is a graph that whose edges attach with existence probability. Existing work on uncertain graph query and mining mainly focus on precise structure, e.g. , subgraph query and subgraph pattern mining. However, there are two issues in practical applications: 1. User don't limit the structure of query result so strictly. 2. Some important graph pattern do not always connect in the same way.For issue 1, this paper proposed a new kind of query——proximity query. Given a query label set R and a distance constrainζ, conducting proximity query on an uncertain graph G is to find some vertex subsets of G that whose label set contains R and for any two vertices in it, the distance between them can not exceedζ. To solve the proximity query on uncertain graphs, we proposed―Reliable Expectation Distance‖, and an efficient proximity relations graphs index is designed. Hence, the proximity query on uncertain graphs is converted to the clique finding on proximity relations graphs. Finally, a tree-based searching algorithm was used to solve the clique finding on proximity relations graphs. A two-phase preprocessing algorithm can reduce the searching space efficiently. Branch and bound approach can further improve the efficiency of clique finding algorithm.For issue 2, this paper proposed proximity pattern mining on uncertain graph. Proximity pattern is a vertex label set which is both tight and frequent. Given an uncertain graph G and a support threshold min_sup, proximity pattern mining on G is to find all the label sets whose support exceed min_sup. This paper defined the support of proximity pattern of uncertain graphs based on reliable expected distance, and proposed the concept of―proximity pattern cover tree‖. Finally, we developed two pruning algorithms to compute all of the proximity pattern.The experiments on real data and synthetic data showed that the proposed query processing algorithm and mining algorithm are both efficient and effective.