Font Size: a A A

Analysis Of The Clustering Uncertain Graph

Posted on:2013-02-21Degree:MasterType:Thesis
Country:ChinaCandidate:Y DingFull Text:PDF
GTID:2218330374968363Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
In recent years, there is an increasing number of graph data in our daily lives, such associal network, the protein-protein interaction in the field of bioinformatics, web applicationand so on. The uncertainty of uncertain graph is either edge with a certain probability exists oredge weight is the additional information of practical significance.Graph clustering is targetedto reveal the true cluster structure of graph data, which not only has very importantsignificance in analyzing the topology of the graph, finding the hidden regularity in graphstructure and predicting the behavior of graph data, but also has broad application prospects.At present, there are few works on uncertain graph data clustering. Therefore, based onLinLog energy model and Newman-Girvan modular clustering, we put forward a multi-levelmodular clustering framework to solve the problem of clustering uncertain graph data.Specifically, the main content is as follows:(1) We firstly systematically presented several state-of-art mainstream techniques forgraph data mining, and gave a comprehensive summary of characteristics, practicalsignificance, as well as real-life applications on mining graph data. Meanwhile, the relatedworks of uncertain graph research were discussed.(2) Graph data, uncertain graph data and some related uncertain graph data miningconcepts were defined. Meanwhile, we summarized and compared the various types ofcomplex network clustering methods, and tried to deal with uncertain graph clustering bymeans of the methods and ideas of complex network clustering.(3) Based on (2), we combined energy layout model and module clustering algorithm,and mapped uncertain weighted graph to multi-graph, then we put forward a multi-levelmodular clustering framework. The experimental results on certain and uncertain datasetsshowed that the presence of uncertainty has clustering influence cannot be ignored. Also itprovided a basis for researchers to recognize the importance of data uncertainty. The resultson artificial and real datasets verified that the proposed algorithm has a good result.The summarized research status quo in graph mining area and some comparative testresults in this work can provide some insight into relative research about uncertain graphmining. At the same time, It confirms that the presence of uncertainty has particular impactand value in the field of data mining research.
Keywords/Search Tags:graph mining, uncertain graph clustering, energy models, modularityclustering
PDF Full Text Request
Related items