Research On Community Detection For Networks Based On Evolutionary Computation

Many complex systems in the real world can be modeled as the form of graph,and complex networks are effective tools for studying the universal characteristics of various systems.With the development of network science,the community structure has been proved as a common property of complex networks.Community detection aims to identify specific community structures in a network.It is not only important for analyzing complex network topologies,revealing rules in complex networks,and predicting complex network evolution,but also has wide application prospects,such as social network information diffusion analysis,protein functional prediction,recommended system optimization,etc.However,with the development of the times,the traditional community detection algorithms face new challenges: 1)due to the increase of network data scale,how to improve the efficiency of community detection algorithm in static networks is an urgent problem to be solved;2)due to the dynamic property of the network,how to efficiently and accurately capture the evolution of community structure in dynamic networks is an urgent problem to be solved;3)due to the multilayers of network,how to discover the composite community structure and understand the full view of the system is the current research hotspot.Aiming at the low efficiency of static community identification,the instability of dynamic community structure and the unreasonable division of composite community,this paper focuses on the evolutionary algorithms to solve the problem of network community detection,and we transform the community detection into optimization problems based on bionic model and multi-objective optimization theory.The main line of this paper is “how to improve the efficiency of community detection algorithms in static networks”,“how to identify a high-quality and stable community structure of dynamic networks” and “how to identify a high-level composite community structure of multi-layer networks”.For community detection in static networks,we propose an enhanced particle swarm optimization algorithm(PSO)based on Physarum model;for community detection in dynamic networks,we propose a multi-objective particle swarm optimization algorithm based on decomposition;for community detection in multi-layer networks,we investigate the current research status and application prospects of evolutionary multi-objective algorithms on multi-layer networks.The main contributions of this thesis are listed as follows:(1)We propose a discrete PSO for community detection in static networks.We use a string-based encoding for easy decoding and evaluating fitness.The updating rule of velocity and position is modified by incorporating with the information of the network neighbor and the greedy strategy of modularity increment.Besides,we introduce a Physarum model,which can identify the intracommunity or inter-community edges.Therefore,the Physarum model is used for the initialization of PSO.Finally,the proposed algorithm is verified in terms of accuracy,robustness and solution quality in synthetic and real-world datasets.(2)The evolutionary clustering framework considers the quality and stability of the community structure.In order to overcome the predefine of weight parameter and community number,and reduce the computational complexity of multi-objective optimization algorithm,we use a multi-objective particle swarm optimization algorithm based on decomposition for dynamic community detection.The algorithm uses modularity density and normalized mutual information as two objective functions.In this proposed method,the individual's fitness is calculated with the Tchebycheff approach,the initialization and status updating process are redefined.We select the solution with the highest modularity density from the Pareto front as the current community structure.Finally,the effectiveness of the algorithm is verified by experiments in four synthetic and two real-world datasets.(3)Since multi-layer network research has just started and there is no clear definition,this paper investigates the theoretical basis and research results of community detection in multi-layer networks at this stage.Two different types of multi-layer networks are introduced: multiplex networks and dependent networks.This paper summaries the community detection algorithms in multiplex networks at the present stage,including the evolutionary computation-based algorithms,which aims to explain the application prospects of evolutionary algorithm and multi-objective optimization community detection in multi-layer network.