Research On Local Overlapping Community Discovery Algorithm Based On Directed Graph

At present,the community discovery algorithm is mainly studied by undirected graph,but in the actual complex network,the link relationship often shows asymmetry,such as Twitter's user attention relationship,the reference relationship of literature network,the hyperlink relationship between web pages,etc.So far,there are many excellent partition methods in the field of community discovery,such as modular optimization algorithm,community discovery algorithm based on tag propagation and so on.These methods only apply to non overlapping communities,that is,each node can only belong to one community.Many social networks,such as karate network and olive team network,have one node belonging to multiple communities,so the research on overlapping nodes is particularly important in the field of community discovery.The main research contents of this paper include:Firstly,the theory and technology of community discovery are introduced,and LFM(An Algorithm based on Latent Factor Model)algorithm,which is applied to overlapping community discovery,is analyzed.In view of its weak applicability in directed social networks and the lack of random selection of seed nodes,an overlapping community discovery algorithm based on weighted undirected graph,SN-LFM(A Seed Node Algorithm based on Latent Factor Model),is proposed.SN-LFM algorithm first improves the applicability of LFM algorithm to directed graph by using the weighted undirected graph model defined in this paper,and then applies the influence function to effectively improve the lack of random selection of seed nodes in LFM algorithm and optimize the results of community division.Experiments show that the improved algorithm makes the result of community partition more accurate and has better effect in the field of community discovery.Secondly,through the analysis of LFM algorithm's execution process,this paper finds that the algorithm has the shortcomings of cyclic calculation of the fitness value of duplicate nodes.After optimizing the selection of seed nodes based on SN-LFM algorithm,this paper proposes a local overlapping community discovery algorithm based on digraph,CSN-LFM(A Core Community And Seed Node Algorithm based on Latent Factor Model)algorithm,which solves the problem of low efficiency caused by repeated nodes in LFM algorithm by giving the definition of core community and closeness.CSN-LFM algorithm mainly includes initial community expansion algorithm and natural community expansion algorithm.Finally,we compare the time efficiency and community partition effect in four different scale artificial synthetic networks and five different real networks.The experimental results show that the improved algorithm has better improvement in the accuracy and efficiency of community partition.