Research And Application Of Community Discovery Based On Markov Clustering Algorithm

With the rapid development of information technology,the research of complex network has attracted the attention of different field'speople.The network is ubiquitous in both natural and human societies.A network can be formed as long as there is a connection or interaction between any object.Therefore,the study of complex networks can explore a wide varietyof complex systems,which is of great significance in many research fields.The continuous deepening of network research makes people find that complex networks have a community structure,that is,the complex network is formed by the combination of different communities,and the internal nodes of associations are close,and the connections between associations are relatively sparse.This feature can be used to analyze the topological structure of complex networks,network rules information and predictpredict the behavior of people,so so community discovery is an extremely important subject in complex network research.In this paper,the classic community discovery algorithms are studied in detail,and the simulation is realized with each algorithm,and then the four classical algorithms are compared and summarized.Each of the four classical algorithms were implemented using Matlab software,these four algorithms are fast communitydetection algorithm(FN),found that communities based on label propagation algorithm(LPA),the seed dispersal thought association algorithm based on(LFM),Markoff clustering the algorithm(MCL).By comparing the results of the four algorithms,we get the conclusion that MCL algorithm has obvious advantages in complex network discovery.Secondly,based on the study of classical modularity function,partition density and community evaluation criteria,an improved evaluation criterion is proposed,and its related properties are summarized.Through simulation comparison,it is found that the improved evaluation criteria can evaluate the quality of community division more reasonably and have higher sensitivity.Thirdly,in view of the fact that traditional community discovery algorithms ignore the irrationality of small associations and marginal communities.we use the classical community discovery algorithm as the benchmark,improve the MCL algorithm,and get the MCLp algorithm.On the basis of MCL algorithm partitioning,this algorithm analyzes whether there are small associations or an edge community,and obtains the set of nodesthat need to be re-divided by the judgment valueand the threshold,and comparing the evaluation function before and after the re-division to get the final community structure.The simulation is carried out on the classical data sets,and contrast with the classical community discovery algorithm.The results show that the MCLp algorithm obtained the structure of the community is more appropriate to the actual division,and the accuracy is as high as 92.8%.With the increase of the number of nodes and the connecting edges,the growth of the improved MCLp algorithm in terms of time complexity is not very obvious.Finally,this paper applies the improved algorithm respectively containing 1000 nodes of benchmark network and the electric power network of the States in the west of the United Statesandthe network of scientific collaboration,obtains the reasonable structure of community,and verifies the universality and stability of the improved MCLp algorithm.