Two-stage Community Detection Algorithm Based On Multi-point Seed Prepartition

With the rapid development of mobile Internet technology,online social media services have been integrated into people's daily work and life.People join different interest groups according to their needs,forming a community structure with high attribute relevance.Community discovery is an important research content in online social network analysis.Its fundamental task is to group nodes with high similarity,and then discover potential connections between nodes.However,due to the sparseness of the network structure and the complexity of network data,the existing community discovery algorithms generally take a long time and cannot effectively detect low-granularity communities in a local network environment.This brings great challenges to the community discovery task Challenges.The community discovery algorithm based on seed expansion has the characteristics of low time complexity,high recognition accuracy,and freedom from the limitation of community form.In recent years,it has been widely used in the network local community discovery task.However,this method does not consider the relevance between seeds when selecting seeds,so the number of community structures identified is large and the structure is relatively loose.To solve this problem,this paper proposes a two-stage community discovery algorithm based on multi-point seed pre-division.First,in order to improve the local community detection ability of the community discovery algorithm,this paper constructs the calculation formula of social network node influence with the parameters of Jaccard coefficient,network node degree and betweenness.This method is based on the structural indicators of nodes,supplemented by the influence scores of local neighbor nodes,which reduces the possibility of low influence scores for local high-influence seed nodes.Secondly,the K-means algorithm is used to aggregate high-influence nodes to obtain a community cluster composed of high-influence nodes,as the backbone community in the social network.After this stage is executed,there are only backbone communities and nodes with low influence scores in the network.Finally,a "community-node" attractiveness measurement function is proposed,and low-impact nodes in the existing network are added to the backbone community to complete community discovery.This method is compared with LS,Chen,Clauset,LWP,VI and LCDMC algorithms in artificial synthetic networks and real networks.The experimental results show that the two-stage community discovery method of pre-divided multi-point seeds can find community structures with a larger size and a smaller number,and then capture the correlation between groups at the meso level.