Research On Community Detection Algorithm Based On Local Optimization

Community detection aims to discover the most prominent structural features in the network.It is widely used in computer science,biology,medicine and other fields,and provides important theoretical basis for humans to explore the nature of the network and deal with the challenges of the network society.Heuristic community detection algorithms mainly include algorithms based on global optimization and algorithms based on local optimization.Algorithms based on local optimization have received widespread attention due to their good time efficiency.To further improve the accuracy and stability of such algorithms,this thesis analyses the shortcomings of current community detection algorithms and proposes two community detection algorithms based on local optimization.The main research work is as follows:(1)A local optimization algorithm LOSG based on seed nodes and node gravity is proposed.In the seed selection stage,the local importance and global importance indicators are combined to select seed nodes to avoid the problem of lack of stability in community division results caused by random selection of seed nodes.In the community expansion stage,the attributes of the node are combined with the law of universal gravitation,and the node gravity is defined to guide the neighboring nodes to expand into the community,so as to avoid the problem of low accuracy caused by the direct expansion of neighbor nodes into the community.In the post-processing stage,the accuracy of the algorithm is improved by reallocating boundary nodes and merging each small community with its neighboring large community which has the largest number of connected edges with the small community.Currently,some community detection algorithms are required to set the number of community divisions in advance,but this parameter is difficult to be determined.The LOSG algorithm does not need to specify the number of community divisions,which improves the applicability of the algorithm in different network scenarios.(2)A local optimization algorithm LONS based on the similarity of nodes and seed nodes is proposed.In the seed node selection stage,the influence of the node itself and neighbor nodes are combined,the LH-index algorithm is used to measure the importance of nodes,seed nodes are selected by node filtering,and the algorithm has good stability.In the community expansion stage,the seed node is used as the initial community,and the node-pair similarity sequence is constructed.The community expansion is completed according to the node similarity.In the post-processing stage,LONS inherits the boundary node assignment and small community merging method of LOSG algorithm,and the algorithm has high accuracy.In addition,the LONS algorithm does not need to set any parameters,and has good adaptability to a variety of network scenarios.(3)Comparing and analyzing the LOSG algorithm and LONS algorithm with the classic community detection algorithm on multiple artificial data sets and four real data sets respectively,experimental results verify the stability and accuracy of this algorithm using standardized information NMI and modularity Q.