Research On Community Mining Algorithm In Large Scale Social Network

It is important to mine the community structure of social network to reveal the potential laws of the network and grasp the macro characteristics of the network. At present, a number of community mining algorithms have been proposed, some of which have the advantage of linear complexity, but there are still two limitations in applying to large-scale networks: the need to predict the number of community in networks and the accuracy of the algorithm is low.Therefore, the above two kinds of limitations were studied and advanced in this research respectively, aiming at applying the existing community mining algorithm to large-scale networks. The main work is as follows:(1) Discussing the existing problems of common community mining algorithms in applying to large networks, and find that the algorithms with low complexity have advantages but there are still two limitations. Therefore, making a research on the method of estimating the number of communities and the label propagation algorithm, and analyzing the advantages and disadvantages of the existing methods.(2) Aiming at the problem of low accuracy, low efficiency and limited scope of application of the existing community estimation method, this paper proposed a method based on regular non-backtracking matrix to estimate the number of community in networks. In this method, a regular non-backtracking matrix is defined in order to describe the sparse network,and the distribution of its eigenvalues is observed. Finally, the community number in networks is estimated by using the maximum position of the intrinsic gap.The method is validated on two artificial networks generated by two classical network generation models.(3) In order to solve the problem of low complexity at the expense of the accuracy and stability of the label propagation algorithm, An advanced label propagation algorithm is proposed in this research.The algorithm prioritize all nodes with a new composite weight in label propagation sequence, and screen candidate labels with the node contribution in the label propagation process. Finally, the convergence condition of the algorithm is optimized by using the newly defined balanced node filtering mechanism. The proposed algorithm is tested on two large social networks and compared with the other three algorithms.The experimental results show that the estimation method based on the non-backtracing matrix eliminated the influence of degree heterogeneous distribution on the estimation of the number of community mainly, so as to improve the accuracy of the estimation results and the scope of application is not limited. Compared with the label propagation algorithm and others two kinds of large-scale network community mining algorithm, The advanced label propagation algorithm not only has significant advantages in terms of performance and quality, but also improves community mining efficiency.