The Research Of Real-time Community Detection Algorithm Based On Label Propagation

With the rapid development of the Internet and the rise of the Web2.0, the detection of community structures in networks has become a hot issue in network analysis. Community detection has great significance for learning the internal structures and deep properties of networks. And as most networks will evolve with time, real-time community detection also has great significance for revealing the dynamic properties of networks. Though there have been a lot of algorithms for detecting communities in static networks, most of them can’t detect communities fast and accurately simultaneously and can’t be applied to real-time community detection too.Label propagation is a simple and efficient algorithm for detecting communities in networks, but it has some flaws such as high randomness and low accuracy. However, its locality of label update can be well applied in the real-time community detection. Therefore a new novel algorithm based on community kernel and label propagation is proposed in this paper. In this algorithm the labels of nodes are updated and propagated on the basis of the weight of the labels around the node, which is associated with the community kernels of the network, and as a result, the algorithm runs fast and has higher accuracy and stability. Then the algorithm is applied to real-time community detection with some improvements. In real-time environments, weights of nodes and members of community kernel will be dynamically changed after the real-time change of the network and then labels will be updated and propagated locally on the basis of weights of nodes. Thus it is efficient and accurate at the same time.Experiments show that the algorithm proposed in this paper has good effect in terms of both efficiency and accuracy in both static community detection and real-time community detection.