Algorithm For Overlapping Community Detection Based On Label Propagation

In recent years,the rise of various large-scale social networking websites has attracted more and more scholars in the research of online social network,community discovery algorithm has become a hot issue in the field.With the expanding scale of online social networks,the efficiency of community detection algorithm is increasingly being valued by researchers and overlapping community structure is more suitable for the actual situation of social networks than disjoint community structure.Community detection algorithm based on label propagation is found in a class of nearly linear time complexity of community detection algorithms,such algorithms assign a label for each node,and then to discover the community through the propagation of labels.Label propagation algorithm is first applied to the overlapping community detection in COPRA,however the updating strategy used by COPRA canse some randomness in the process of the algorithm.In this page we improve the COPRA,and propose two new algorithms with the new updating strategys,node preference label propagation algorithm(NPLPA)and community preference label propagation algorithm(CPLPA).Nodes preference updating strategy use different weights to different neighbor nodes in the calculation of the belonging coefficients which improve the stability of the algorithm and the ability to find overlapping communities.Community preference updating strategy enlarge or reduce the influence of the communities,can also achieve the purpose of improving the algorithm results.In the initial stages,new algorithms extract rough coles from network,which effectively improve the efficiency of the algorithm and the quality of the results.We compared the two new algorithms with COPRA respectively on synthetic networks and real-world networks.For synthetic networks,we change the value of parameters to generate multiple social networks to compare the experiment results on quality and stability,In order to compare the results of the algorithms,we used the mean and standard deviation of NMI to describe the quality and stability of the results,in addition,we use visualization technology to visually compare the results of the algorithms on synthetic networks.For real-world networks,we use the overlap modularity Qov to describe the results.After a number of experiments show that the new algorithm NPLPA and CPLPA results on synthetic network and real-world network are superior to COPRA,the quality and stability of the results has improved to some extent while maintaining a very high efficiency.And NPLPA has a good adaptability in the overlap nodes while CPLPA has a good adaptability in the different community structures.