Research On Community Detection And Graph Embedding Problems Based On Evolutionary Computation And Meta-heuristic Search

Many objects in the real world,such as power systems,social networks,and transportation networks,can be represented as complex networks composed of nodes and their connections.Community detection and network embedding are two important research directions.On the one hand,community can not only reflect interest groups in social networks,but also reflect regulatory modules in protein-protein interaction networks.Therefore,community detection plays a key role in understanding information dissemination and discovering functional modules.On the other hand,network embedding helps us overcome the difficulties of high-dimensional nonlinear data by mapping high-dimensional sparse connection relationships to low-dimensional vector space,which can help the subsequent use of machine learning algorithms on classification,recognition and prediction tasks.However,these two research directions face many difficulties: for the community detection problem,the diversified real-world situations and the nonlinearity of the graph structure pose a challenge to how to define the community objective function.The largescale networks also require efficient search method;for the network embedding problem,breaking through the traditional first-order or second-order similarity definition to introduce the community structure similarity,and retaining the community structure information in the mapping constitutes a challenge.Based on the above challenges,firstly,this paper studies and designs three key operators for the EA-based community detection algorithm,namely the initialization operator,the crossover operator and the local search operator.Secondly,an alternately optimized network embedding method based on graph autoencoder and evolutionary computation is proposed.The main contents of the paper are as follows:(1)An evolutionary algorithm for community detection based on heuristic sampling and equivalent mapping is proposed.Most community detection algorithms based on evolutionary computation do not deal with the problem of the coding difference when individuals cross and lack a good method for generating initial solutions.In response to the above problems,this paper proposes the sample operator and the learn operator.The former uses a development perspective to view the emergence of the community and constructs an effective method to adopt new solutions.The latter uses a greedy algorithm to find the equivalent mapping between two individuals in the meaning of Hamming distance.Furthermore,an evolutionary algorithm based on heuristic sampling and equivalent mapping(EAHSEM-net)is used to solve the problem of community detection.Independent comparative experiments on multiple real networks have proved the effectiveness of the two operators and the EAHSEM-net algorithm.(2)A community detection memetic algorithm based on the upper confidence bound and the large-scale neighborhood search is proposed.In most EA-based community detection algorithms,the design of local search operators often uses traditional methods such as the hill-climbing strategy and the simulated annealing method.The concept of community scoring function and move award function is established to use the control strategy based on the reinforcement learning,and the destruction operator and repair operator are constructed for the large-scale neighborhood search.They are combined under the framework of the memetic algorithm to take advantage of different community scoring functions.Experiments show that the local search operator we proposed is better than the traditional heuristic operator and the hybridization advantage brought by the recombination operator.(3)A network embedding learning algorithm based on evolutionary computation and graph autoencoder is proposed.It has always been desirable to integrate high-order structural information and community structure information into the network embedding.However,both the traditional matrix factorization method and the popular deep learning method optimize the network embedding problem from the perspective of reconstructing the loss function.Therefore,it is difficult to optimize the discrete and undifferentiated community structure function.This paper introduces a method representing overlapping community and adds the community term to the objective function of the graph autoencoder.The sample operator proposed in the first work is used to extract the effective information from the output of the graph autoencoder and construct the initial population of evolutionary optimizationan.The combination of the above two realizes the alternately optimized network embedding learning algorithm.The experimental results show that our proposed method performs better than the classic network embedding method on node classification tasks based on network embedding.