The Research Of Community Detection Algorithms In Large-scale Networks

Community structure widely exists in large-scale complex networks. Since it has highapplication value and is very helpful for analysis of networks topology, community detectionhas become a hot topic in the field of complex networks. However, how to detect thecommunities with low costs and high accuracy is still a problem. Lots of algorithms havebeen proposed, but most of them have their own disadvantages that limit them to smallnetworks and can’t be applied to large-scale complex networks.To solve the problem of existing algorithms, we researched community detectionalgorithms and the main contents and innovations are as follows:(1) We proposed a new community detection algorithm based on local information. Whenevaluate whether adding a node to community or not, we take every possible local structureinto consideration, so that the contribution of node can be evaluated precisely. The algorithmis tested in real-world network. The result shows that, compared to traditional algorithms, thenew algorithm precisely evaluates the contribution of nodes and has good stability andaccuracy, besides it can also detect some overlaps between communities.(2) We proposed an optimized Label Propagation Algorithm (LPA). The traditional LPAdetects the community structure with low costs but the result is not quite stable and reliable.So we apply the new contribution evaluation to tradition LPA to improve the performance.The algorithm is tested in real-world network. The result shows that, the optimized LPA notonly can effectively detect communities with low costs and relatively high accuracy but alsocan detect overlapping communities.(3) We proposed an optimized fitness algorithm. Since the traditional fitness algorithmunderestimates the contribution of nodes with large degrees, the result is not reliable. So weuse the idea of complete subgraph to optimize the fitness expression. The algorithm is testedin real-world network. The result shows that, the optimized fitness method can evaluatecontribution degree more precise than the traditional algorithms.