Uncertain Graph Data Mining Algorithms

With the rapid development of computer technology industry and the Internet,massive data have been accumulated in more and more real-world applications. As oneof the most general data structures, graphs have significant advantages when they areused to model property and structure features of knowledge. On one side, graphs can bedirectly used to represent patterns and property information in biology, chemistry, andso on. On the other hand, more and more applications in the Internet and real life suchas the relationships between people can modeled as graphs. The data described bygraphs are called the graph data.Due to the limitations of data sources, data description methods and dataacquisition techniques, graph data that are imprecise and incompletely exists in practice.Graphs with uncertainties are called uncertain graphs. Large amount of valuable andrich knowledge are contained in uncertain graphs, and thus discovering knowledge fromuncertain graphs is of practical significance.We focus on the techniques for mining uncertain graphs. The main contributions ofthis thesis are as follows:This thesis proposes a maximal frequent pattern mining algorithms on uncertaingraph set. The algorithm is developed based on random walk. It considers therelationship between uncertain graphs and deterministic graphs, thus avoidingcomputing the exponential number of possible worlds. The algorithm is able to findK-maximal frequent patterns efficiently.The problem of finding close subgraphs in an uncertain graph is also investigatedin this thesis. We prove that the problem is NP-Hard, and propose a search-tree basedexact algorithm and an approximation algorithm that is more efficient on large-scaledataset. Both of two algorithms can find close subgraphs from a large uncertain graphefficiently.We also propose an algorithm to solve the problem of finding k most close regionsin a wireless sensor network. The algorithm represents wireless sensor networks by uncertain graphs in a distributed manner, and uses tree searching and branch-and-boundstrategy to discover the sensor nodes that communicate well in practical. This algorithmlays foundations for other algorithms and applications in wireless sensor networks.