Study Of Network Community Detection Based On Chemical Reaction Algorithm To Optimize Modularity Density

With the rapid development of social science and technology,complex systems have spread all over our lives.The complex network exists as an abstract representation of a complex system.It can usually be abstracted as the form of a graph.That is,the nodes are represented as objects,and the lines between the nodes represent a certain connection between the nodes.Community structure is also an important feature of complex networks.Under normal circumstances,the nodes within the community are relatively closely connected and the nodes between the communities are sparse.Therefore,discovering the community structure within a complex network is of great significance for understanding the topology and role of the network.The algorithm of complex network community structure division is mainly to discover the real existence of community structure in complex networks.Researchers have proposed a series of algorithms to detect the potential community structure in complex networks in order to better analyze complex networks.The traditional association discovery algorithm mostly selects the modularity degree as the evaluation function of the community structure.In recent years,the relevant research shows that the modularity degree has a certain resolution problem.In order to solve the problem,the researchers put forward the modularity density as a new community evaluation function.In this thesis,we choose modularity density as the evaluation function of community structure,and propose a new community structure detection algorithm based on chemical reaction algorithm.The main work and innovation of this thesis are as follows:(1)The evaluation function of complex network communities and related community structure discovery algorithms are studied.As an important aspect of complex network research,community structure has proposed many discovery algorithms,and finding the best partition method has always been the focus of research.This thesis studies the advantages and disadvantages of the related algorithm and algorithm.(2)The optimization algorithm of chemical reaction is studied.Chemical reaction optimization algorithm is a combination of computer and chemistry.It is a meta heuristic algorithm.The algorithm simulates the interaction between molecules and molecules in chemical reactions,and obtains the optimal solution by finding the minimum molecular potential energy of the entire molecule.(3)A complex network community detection algorithm based on chemical reaction algorithm to optimize modularity density is proposed.In this thesis,using the modularity density as the fitness function and using the chemical reaction optimization algorithm,the single molecule wall reaction operator,the single molecule decomposition reaction operator,the multi molecule exchange reaction operator and the multi molecule synthesis reaction operator are designed and realized.Experimental results show that compared with several classical algorithms,the proposed algorithm is more accurate and efficient.(4)The elitist reservation strategy is introduced to improve the convergence speed of the algorithm.In the chemical reaction algorithm,due to the existence of molecular kinetic energy,the molecules with better structure are changed into relatively poorly structured molecules in the reaction process.This phenomenon makes the molecular population rich,but it is possible that the optimal solution can not be found in the limited number of iterations,so that the algorithm convergence rate is relatively slow.The elite retention strategy searches for the lowest potential molecules before the reaction,and remains,replacing the highest potential energy with the lowest potential molecule before the next iteration.(5)The local search operator is introduced to improve the local search ability of the algorithm.The optimization algorithm of chemical reaction has good global search ability.In order to improve its local search ability,the local search method of mountain climbing method is added to the algorithm as a local search operator.The algorithm is more accurate and efficient.