Research On Core Decomposition Algorithm In Uncertain Graph

As an important dense-graph mining method,core decomposition plays an important role in describing the biological function of proteins and community discovery.In recent years,there have been a large number of research results on core decomposition algorithms in deterministic graphs,but uncertainty prevails in a large amount of graph data in real networks,such as protein interaction networks,social networks and these networks with uncertainty characteristics are called uncertain graphs.How to perform core decomposition in uncertain graphs has become a new research hotspot,therefore,this paper addresses the core decomposition problem in uncertain graphs.Firstly,to address the problems of many iterations and redundant computation in the exact algorithm of uncertain graph core decomposition,an improved core decomposition accurate algorithm is proposed.The algorithm is divided into two stages:theη-deg initial computation and update computation of vertices.In the initial computation stage,the lower bound of vertex’sη-core number is calculated using Lyapunov’s central limit theorem;in theη-deg update computation stage,the vertex set is removed at once,updating all neighbor vertices that satisfyη-deg greater than k.Secondly,to address the problem that existing uncertain graph core decomposition algorithms cannot achieve core decomposition on large-scale graph data quickly due to low time efficiency,an approximation algorithm for uncertain graph core decomposition based on probability distribution models is proposed.The error bounds of different probability distribution models are analysed and the algorithm calculatesη-deg using a combination of standard normal distribution,poisson distribution and binomial distribution according to the conditions of use of different probability distributions,and theη-core number of each vertex is obtained by iteratively removing the vertex with the smallestη-deg.Thirdly,the uncertain graph Top-K（k,η）-core dense subgraph mining algorithm TKCU is proposed to mine the top K（k,η）-cores with the largestη-core number.The algorithm is divided into two phases,mining(k_max,η)-core and Top-K（k,η）-core,by using the binary search method to find the(k_max,η)-core and using the maximum core number in the determined graph as the basis for dividing the interval.In the mining Top-K（k,η）-core phase,the remaining Top-K（k,η）-core is calculated top-down,and the（k,η）-core is calculated by using theη-deg of some of the vertices that have been obtained in the binary search.Finally,the improved uncertain core decomposition accurate algorithm,approximation algorithm and Top-K（k,η）-core mining algorithm are verified and analyzed on different real datasets.