Research On Probabilistic Motifs Mining Algorithm In Uncertain Networks

Many classical problems are expressed by graph structure, and the graph structure has stronger expressive power than relational data. The research on the Network motif is an important tool to study complex networks. Network motif are patterns of interconnections occurring in the networks at numbers that are significantly higher than that in the randomized network. Present experiments shows that the network motif is avalible to study the function module and dynamic change process of the network. Nowadays, a lot of research on network model mining in determined network have been carried out by scholars from home and abroad. However, the information in real life is inaccuracy, even absent, which is often unavoidable. What's more, the representation of the network itself is a dynamic process making the abstract graph model often have uncertain information.In this thesis, we study the probability network motif mining in uncertain network. The main content includes:(1) Based on the property of the probability distance, a concept of uncertain graph isomorphism is proposed. In addition, the probability distance between the uncertain graphs is derived. This theorem provides the theoretical basis for the realization of the subsequent algorithm and simplifies the calculation rules.(2) Then, an uncertainty graph isomorphism method is proposed. Basic on the classical graph isomorphism algorithm VF2 algorithm, the concept of uncertain graph isomorphism is incorporated into the search process, to help the algorithm find the optimal match between two uncertain networks. Experimental results show that the algorithm can quickly determine the probability graph isomorphism between uncertain graphs.(3) An uncertain network frequent probability pattern mining method is proposed. This algorithm applys the nontreelike subgraph method to search the specified size subgraph, then it cluster the subgraph with the hierarchical clustering algorithm. This algorithm is available to obtain all the frequent probability patterns in uncertain networks quickly at once in batches.(4) A statistical significance of probability motif method is proposed.The algorithm separates the topological notwork and probability weight from original network. Then it makes use of the determined random graph generation technique to achieve topological randomization, and use the EM algorithm to obtain the probability distribution of the probability value. For a given probability subgraph, it use expectation estimation to get the frequency and the variance in stochastic networks. We evaluate the quality of the parameter estimation by using the goodness-of-fit test. The experimental of biological network results show that the algorithm is available.