Uncertain Community Discovery Algorithm Research Based On Increment

With the extensive application of internet, social networks developed rapidly, and a variety of social networks showed a strong community effect. Real-life networks contain close-knit communities, in different applications, these communities are also called modules, clusteres, etc. In general, the connection is closer in the inner part of the community and the connection is sparser in the external part of the communities. How to find this communities(community detection) quickly and accurately is still a critical problem.From whether to consider the uncertainty of the data, community discovery can be divided into certain community discovery and uncertain community discovery. Currently, many traditional community discovery algorithms found communities based on global information and it did not consider the uncertainty of the data. However, in real-world applications, network data were often uncertain. Data are incomplete and probabilistic and the processes of finding community structures from this networks were called uncertain community detection. We gave full consideration of local characteristics of social networks and the characteristics of the data to this paper, then gave further study from these two aspects.The main work and innovations are as follows:(1) In this paper, an improved Largest Fitness Measure algorithm based on potential energy was proposed. We researched the traditional local community discovery algorithm LFM algorithm and potential energy model, and then put forward the WLFM algorithm. The new algorithm optimized and handled initial node, simplify node fitness function and expanded community. Through two groups of experimental we validated the performance of the algorithm.(2) In this paper, we used potential energy model to improve the traditional Expectation Maximization algorithm. We introduced the EM algorithm of gaussian mixture model, and used potential method to initialize EM algorithm. By two experiments we proved that the new algorithm has lower error rate.(3) In this paper, a close subgraph discovery algorithm was proposed. In the algorithm, we calculated the connectivity index of uncertain graph, determined threshold and calculated probability of subgraphs according to threshold, then could get k relatively close subgraphs. Finally, by experiments we verified that the algorithm can discover uncertain close subgraphs efficiently and accurately.