Research On Community Detection Algorithms For Large Complex Network

With the rapid development of Web 2.0 and the rise of online social networks,computational efficiency of community detection in large-scale social networks has become a major problem.Although research achievements are numerous at present such as the Louvain method,Clustering-based method etc,most of these achievements cannot be adopted in large-scale social networks because of the heavy computation and the decrease of accuracy.The main content is as follows:(1)We introduced some mainstream community detection algorithms and some algorithms which were suitable for the large-scale complex networks in time and accuracy.(2)We proposed a community detection algorithm based on sampling and label propagation.In particular,the proposed algorithm firstly generated some subgraphs via random walk sampling and computed the weight of each edge,then detected communities on these subgraphs.In the end,we partitioned the unsampled nodes into the communities according to subgraphs ' structures.The experiments were conducted in comparison with widely used state-of-the art community detection algorithms on several real networks.The results showed that the proposed algorithm can provide computational efficiency,while maintaining the effectiveness.(3)We proposed an algorithm based on folding and label propagation.The proposed algorithm folded the large-scale complex networks according to long tail characteristics of complex networks,and then chose some core nodes on folded networks.In the end,we partitioned remain nodes into the communities.After experimental comparison,the results showed that the algorithm can efficiently and effectively find the community structure.The proposed two algorithms can provide computational efficiency,while maintaining the effectiveness of community detection,which make the community detection algorithm study well adapt to the current situation of the rapid increasing scale of complex network.