Research On Overlapping Community Detection Algorithm Based On Line Graph And Label Propagation

With the rapid development of complex networks such as social networks,the community detection of complex networks has become a hotspot.As one of the branches,overlapping communities detection is closer to the real network structure,which has important research and practical significance.At present,node-based label propagation algorithms are widely used in overlapping community detection research because of simple and rapid advantages.However,these kinds of algorithms are always random,and sometimes even divide all nodes into one community.Therefore,in order to detect overlapping communities in complex networks and improve the robustness of label propagation algorithms,edges are chosen for detection instead of nodes,because overlapping community structures can be naturally obtained by edge-based detection algorithms.In this work,an overlapping community detection algorithm based on line graph and label propagation is proposed.In addition,in order to increase the effeciency of the detection algorithms on deal with large-scale networks,a merging and optimization algorithm of overlapping communities based on line graph is proposed.The main research works are as follows:(1)Because of the random updating order and the random selection of updated labels,which lead to the strong randomness of label propagation algorithm.Therefore,in order to improve the robustness and accuracy of algorithms based on label propagation in overlapping community detection,this work proposes a directed label propagation algorithm based on the edge as the research object,namely overlapping community detection algorithm based on line graph and label propagation(LLPA).LLPA proposes the concept of seed edge,and propagates the label directionally according to the similarity between the other edge and the seed edges,which can improve the robustness of the algorithm.Meanwhile,to improve the accuracy of the algorithm,the LLPA algorithm merges and optimizes the overlapping communities from the perspective of improving the modularity.Experimental results on LFR benchmark networks and real network datasets show that the LLPA algorithm is more robust and accurate than the existing algorithms based on label propagation in overlapping community detection.(2)Considering the optimization of overlapping communities based on line graph from the perspective of improving modularity,a large amount of computation makes it can't be applied to large scale networks.In this study,an algorithm for merging and optimizing overlapping communities obtained from line graph(MOOCLG)is proposed.In order to detect large scale networks,MOOCLG algorithm uses two thresholds to make it only use the overlapping communities and the overlapping nodes to merge highly overlapping communities and filter out inappropriate nodes,so as to improve the accuracy of the algorithm and greatly reduce the time complexity.Experiments on the large LFR benchmark networks and real networks show that the MOOCLG algorithm is faster than the algorithm based on modularity optimization,and it has a high accuracy.