Research And Implementation Of Structural Clustering On Probabilistic Graphs

With the rapid development of science and technology,the data structure graph is more and more extensively applied in the mining and analysis of various industries.Graph abstracts the relationships and connections among different objects,offering convenience for researches and analyses.As a fundamental graph mining and analyzing operator,structural clustering is not only able to find densely-connected clusters,but it can also identify hub vertices and outliers in the graph,which may help to the better understanding of the roles of different nodes and also the relationships among them.Previous structural clustering algorithms are tailored to deterministic graphs,where all the nodes and edges exist determinately.However,for a variety of reasons,many real-world graphs in scientific researches and daily lives are not deterministic,but are probabilistic in nature.Examples include the uncertain relationships affected by privacy-preserving reasons in social networks,the uncertain connections affected by experimental factors in biological networks and the uncertain links affected by environmental influences in ad-hoc networks.Usually,the uncertainty should be represented by uncertain(probabilistic)graphs.Hence,the structural clustering problem on probabilistic graphs need to be considered.However,previous structural clustering algorithms for deterministic graphs are not able to represent the linking relationships in probabilistic graphs.Hence,in this thesis,the problem of structural clustering on probabilistic graphs is proposed and formulated,with the aim of finding reliable clusters in a given probabilistic graph.Based on this,a structural clustering algorithm on probabilistic graphs is designed and implemented.Specifically,in this thesis,the definitions of structural clustering algorithms on probabilistic graphs is first researched.We analyze and summarize the previous structural clustering model on deterministic graphs,and then generalize to the definitions of structural clustering on probabilistic graphs.Unlike the traditional structural clustering problem on deterministic graphs,our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph.Therefore,a probability to measure the similarity between vertices can be used.But unfortunately,the calculation of reliable structural similarity is a hard problem,almost intractable due to its high time complexity.Hence,we thoroughly analyze the calculation of reliable structural similarity.And based on this,a dynamic programming algorithm is developed.This algorithm can rapidly solve the calculation problem of reliable structural similarity.With the reliable structural similarities,a structural clustering algorithm framework on probabilistic graphs is devised based on a state-of-the-art solution on deterministic graphs.For further optimization,several powerful pruning and optimizing strategies are devised and applied.Finally,comprehensive experiments on five real-life datasets are conducted.With the comparison to existing clustering algorithms,our approach shows better results on probabilistic graphs.Meanwhile,with the efficiency analysis,the effectiveness of our optimizations is validated.According to the experimental results,our proposed algorithm can solve the structural clustering problem on probabilistic graphs effectively and efficiently.