Research To Stable Detecting Overlapping Communities By Label Propagation On Social Networks

With the popularity of social networks, it has been play a more and more important role in our daily life. The study of social networks has caused people’s great interest. Social network is composed by some connected nodes, meanwhile some potential community structures are exist in the network. In the same community which the connection is relatively dense, and the connection between different communities is relatively sparse. Through the study of the community structure, we can further understand the complex relationship between different nodes. And it also helps us to understand the network’s structure and function from the point of community.Community mining can discover the potential communities in social networks. In recent years, researchers have found that in the real social network communities there were often some overlapping community structures, and from then on more and more researchers begin to study overlapping community mining algorithms. There have been some classic algorithms in that filed of research, but the amount of data in the current social network is so large that it will increases the time complexity of the algorithm, so it it urgent to propose a much quickly overlapping community mining algorithm. Among the community mining algorithms the label propagation algorithm has an obvious advantage in terms of speed, and it’s time complexity is nearly linear. There are a lot of improved algorithms based on the LPA algorithm, including the COPRA algorithm that can discover overlapping community. Although these algorithms can quickly mining community, but it also have its own disadvantages, such as the COPRA algorithm, it inherits the LPA algorithm’s original defects and unstable during the mining process.This paper will study all kinds of label propagation algorithms, and we will improve the algorithm from the aspects of label initial, label spread and label choose. In this paper, firstly we proposed label pretreatment and semi-asynchronous update policy to further enhance the efficiency of the mining community algorithm which is based on LPA. And then used a balance factor to control the stability of community mining results. Finally through comprehensive comparison of a all kinds of algorithm based on LPA, we put forward a BOCLP algorithm that can focus on the community mining’s quality, efficiency and stability at the same time.