A Study Of Complex Network Community Discovery Based On Multi-objective Biogeography-based Optimization Algorithm

There are a large number of complex systems in nature and human society,most of which can be abstractly described as complex networks,such as biological networks,social networks,transportation networks,neural networks,etc.Numerous studies have shown that complex networks are commonly characterized by community structures,which are highly interconnected groups of nodes in complex networks,and these groups usually have specific functions or behaviors.By identifying the real existing community structures in complex networks,not only the functions and structures of complex networks can be understood and analyzed,but also the important information latent in complex networks can be further explored.Therefore,it is of great theoretical significance and practical value to study the community structure of complex networks.In recent years,many scholars have successively proposed a large number of community discovery algorithms,among which intelligent optimization algorithms have gradually become one of the important methods to solve the community discovery problem of complex networks due to their advantages of good parallelism,strong global search capability,and availability for any function.In this paper,we take community discovery as the research content and biogeography-based optimization algorithm as the method to carry out the research.The related research work is as follows:(1)To solve the multi-objective optimization community discovery problem for complex networks,a multi-objective biogeography-based non-overlapping community discovery algorithm(MOBBO-CD)is proposed in this paper.For the mechanism of the biogeography-based optimization algorithm(BBO)itself,a BBO model applicable to multi-objective optimization is established by combining non-dominated ranking and congestion distance,and community discovery is established as a multi-objective optimization problem based on two objective functions,namely,internal community connection ratio(NRA)and external community connection ratio(RC),to alleviate the modularity resolution limitation;in terms of migration method,the original unidimensional In the migration method,the original unidimensional migration method is improved and a one-way crossover method is introduced,and secondly,in order to avoid destroying the original relatively correctly divided community in the migration process,the local modularity density is used to determine whether the community structure is shared or not;using the information of the number of connected edges in the community,a mutation strategy based on the number of connected edges is proposed to ensure that the mutation produces a better solution;for the nodes that may be incorrectly divided in the community,a node similarity-based optimization strategy is proposed to identify the nodes that may be incorrectly divided by The node neighborhood information identifies nodes that may be misclassified as well as fixes misclassified nodes based on node similarity to ensure that the population evolves in a better direction.By comparing the MOBBO-CD algorithm with the remaining five algorithms,the experimental results on synthetic and real networks show that the MOBBO-CD algorithm effectively compensates for the shortcomings of the traditional single-objective community structure division and improves the accuracy in community discovery.(2)In order to detect overlapping communities more effectively,a multi-objective biogeography-based overlapping community discovery algorithm(MOBBO-OCD)is proposed in this paper.A two-population evolutionary strategy is proposed for the biogeography algorithm to easily fall into local optimum problem,and the habitat population is divided into two-way migration sub-population and one-way migration sub-population.The two-way migration subpopulation introduces a two-way crossover approach to increase the exploration performance of the algorithm by making the individuals in the group learn from each other through crossover;the one-way migration subpopulation introduces a one-way crossover approach to accelerate the convergence of the poorer individuals to the better ones by sharing their superior traits through migration operations.In order to improve the overlapping community discovery accuracy,the two-way migration subpopulation turns some boundary nodes into candidate overlapping nodes by mutation strategy during the population evolution process,and further searches for possible missing overlapping nodes.Meanwhile,in order to speed up the population convergence,a multi-individual-based mutation strategy is proposed for the unidirectional migration subpopulation,in which the mutation direction of nodes is decided by voting on the information of multiple outstanding habitat individuals.By comparing with other overlapping community discovery algorithms on real network datasets,the experimental results show that the MOBBO-OCD algorithm can identify the overlapping community structure well.