Efficient Algorithm For Mining Dense Subgraphs In Uncertain Graph

In recent years, graph modeled data ware accumulated in every field of the society, which including social networks, intelligent traffic system, the field of bioinformatics etc. These areas contains a large number information with rich semantics and potential value, therefore to discover useful knowledge in the graph data has become an important research topic, and this technology is called graph mining. Because the explosive growth of the modern Internet information makes effective drawing on traditional computers mining become a difficult problem, a detailed study and research ware carried out on dense graphs mining in uncertain graph and large-scale graph mining parallelism.First of all, this paper is based on the weighted uncertain graph data model. In order to solve the problems of the uncertain graph dense subgraphs mining in uncertain graph, the boundary existence probability, the expected degree of vertexes and expected density of subgraphs are considered to calculate the density of graphs. At the same time, the expected density peak is put forward according to the characteristics of expected density of graph mining, which improves the algorithm execution with 2- approximation result and an efficient execution. The algorithm is proved to guarantee the correctness of the final mining result.Secondly, in order to break through the bottleneck of large-scale graph data mining, this paper improved a dense subgraphs mining algorithm parallelization in the platform of Spark. The existing cluster technology is suitable for processing data with no dependences, while not for the data with complex dependency relationship between elements. In order to solve this problem, we design the programming model and graph computation strategy suitable for large-scale dense subgraphs mining.Finally, we use several datasets to verify that the improved algorithm dense subgraphs mining and parallel processing is effective, feasible and of practical significance.