Research On Community Detection Based On Label Propagation Algorithm

With the development of Internet technology, online social network is increasingly popular. Traditional communities detection algorithms have been far behind the fast growth of various complex systems. How to efficiently and effectively discover community structures from large-scale complex networks is a huge challenge. Deep understanding of community structures in complex networks is helpful for decision-making problems in real applications. At present, a class of label propagation algorithms (LPAs) is widely used for community structures detection in large-scale complex networks due to its simple linear time complexity and fast convergence advantages. However, these algorithms are usually with poor stability on account of propagation randomness.In this paper, through in-depth research and analysis of label propagation algorithms, we find that node selection, order update and label initialization of traditional label propagation algorithms are based on random strategies, as severely impairs algorithm stability, and neighbor selection rules are so simple that singular solutions that each node has the same label occur frequently. To address these issues, we put forward three novel strategies as below:1) In order to improve the performance of label propagation method, we propose a semi-synchronous label propagation algorithm based on node influence (ISLPA). ISLPA avoids propagation oscillation using a novel label update strategy, and achieve better stability by integrating node influence into label initialization, neighbor selection and update order determination. Experimental results from the real-world and artificial networks indicate that, in terms of validity and stability of generated communities from the networks, ISLPA outperforms the currently typical LPAs used in community detection algorithms.2) In order to meet the needs of complex network in real life, we propose a Voting-based Label Propagation algorithm for Non-Overlapping communities detection (VLPNO).The rule of label propagation algorithm was improved by the electoral model in life,the node participate in elections with the rules of the electoral model. Through the election, groups are form as a leader and lots of followers. In each iteration of the election, voters are separated by the strategy, updating synchronously, so that the iteration of the algorithm is faster,and the result is more stable.3) In order to make the algorithm adapt to complex network of overlapping, the recommendated rule model is extended, we propose a Voting-based Label Propagation algorithm for Overlapping communities detection (VLPO).Through a sequence of labels to each node, the labels in the propagation process are stored and disseminated. The propagation distance was limited to prevent the generation of the global community. The parameters in the algorithm are calculated in terms of the specific circumstances.In result, the robustness of the algorithm improved.