Structure Analysis And Representation Learning Of Complex Networks Based On Computational Intelligence

Network-structured(or graph-structured)data which can capture rich information about individual entities and their relations via nodes and edges connecting two nodes has become an essential data type in many research fields including social sciences(friendship networks),cognitive sciences(knowledge graphs),biology(protein-protein interaction networks),chemistry(molecular/compound graphs),and many other research areas.Networks are not only useful as structured information repositories but also play a key role in modern machine learning tasks.Structure analysis and representation learning of network-structured data can promote the developments of academic research and practical applications.Community structure is identified as an intrinsic and important one for reflecting the functionality of complex systems.Generally,the connections within communities of a network are denser than those among communities,and nodes belonging to the same community probably have same or similar properties.Analyzing the community structure of complex networks can help understand and analyze the behavior characteristics of complex systems.Robustness is another important property which reflects the potential functionality of complex networks.The robustness of networks can reflect the stability and integrity of the functional modules of the complex system when suffering from random failures or malicious attacks.Therefore,researches on network robustness are of great importance for analyzing the security of the functional modules of complex systems and the ability to resist attacks.Recently,with the development of machine learning technology,learning representations for nodes in the network or the whole network has become an emerging research direction.Network representation learning(or network embedding)aims to map the nodes in the network or the entire network to a low-dimensional and continuous vector space.The learned representations can be fed to the follow-up classifiers(e.g.,support vector machine)according to downstream tasks,such as node classification,link prediction,graph clustering,graph classification,recommendation system,etc.This dissertation mainly focuses on the challenges on community detection,network robustness,network representation learning,and graph neural network and employ the approaches in the field of computational intelligence(i.e.heuristic evolutionary algorithms and deep learning methods)to resolve the problems.More specifically,the main works of the dissertation are summarized as follows:Community structure is a natural and inherent property of complex networks which can reflect their potential functionality.When the robustness of a network is improved,its community structure should be preserved as much as possible.However,most earlier studies only considered enhancing the network robustness and ignored the analysis of the community structure,which may alter the original topological structure and functionality of networks.In this dissertation,we propose a new memetic algorithm with a two-level learning strategy to enhance the community robustness of networks,while maintaining the degree distribution and community structure.The proposed memetic algorithm is a hybrid globallocal heuristic search methodology which adopts genetic algorithm as the global search and the proposed two-level learning strategy as the local search.The two-level learning strategy is designed based on the potential characteristics of the node structure and community structure of networks,which aims at mitigating two-level targeted attacks.Experiments on synthetic scale-free networks as well as real-world networks demonstrate the effectiveness and stability of the proposed algorithm as compared with several state-of-the-art algorithms.The detection of shared community structure in multilayer network is an interesting and important issue.Traditional methods for community detection of single-layer networks are not suitable for that of multilayer networks.In this dissertation,we formulate the detection of community structure in multilayer networks as a multiobjective optimization problem and propose an improved multiobjective evolutionary approach to optimize it.The proposed approach MOEA-Multi Net is based on the framework of NSGA-II,which employs the string-based representation scheme and synthesizes the genetic operation and local search to perform individual refinement.Experimental results on two real-world networks both demonstrate the capacity and efficiency of the proposed MOEA-Multi Net in uncovering community structure in multilayer networks.Network embedding has been widely used to solve the network analytics problem.Existing methods mainly focus on single-layered homogeneous or heterogeneous networks.However,many real-world complex systems can be naturally represented by multilayer networks,which is another term of heterogeneous networks with multiple edge/relation types.The problem of how to capture and utilize rich interaction information of multi-type relations causes a major challenge of multilayer network embedding.In this dissertation,we propose a fast and scalable multilayer network embedding model to efficiently preserve and learn information of multi-type relations into a unified embedding space.We develop a heuristic3 D interactive walk technique dedicated for multilayer networks,which can leverage rich interactions among distinct layers and effectively capture important information contained in the layered structure.We evaluate our proposed model HMNE on two downstream analytic applications: node classification and link prediction.Experimental results on seven social and biological multilayer network datasets demonstrate that the proposed model outperforms existing competitive baselines with reduced time and memory occupations.Graph neural networks(GNNs)have been widely used for representation learning on graph data,wherein graph convolutional networks(GCNs)are inarguably the dominant category of GNNs.Modern GCNs exploit common local and global structural patterns on graphs through designing various convolution operations and readout functions,and there are a variety of approaches based on GCNs developed for graph-level representation learning and classification applications recently.However,current GCN approaches are inefficient to preserve locality of graphs — a limitation that is especially problematic for graph classification,whose goal is to distinguish various graph structures based on their learned graph-level representations.To release this limitation,in this dissertation,we propose a locality preserving dense graph convolutional network architecture.Specifically,our model constructs an extra local node-feature reconstruction loss to help preserve initial node features into node representations.The reconstruction module is realized by designing a simple but effective encoder-decoder mechanism.Besides,to flexibly leverage information from neighborhoods of differing locality,we explore a dense connectivity pattern that connects each convolutional layer and its readout of the network with all earlier hidden convolutional layers.Experiments on benchmark datasets demonstrate the superiority of the proposed model over state-of-the-art methods in terms of classification accuracy.Aiming to enhance node representativeness,our architecture further connects each convolutional layer with the previous layer's readout to form a global context-aware node representation.Besides,through adding such direct connections from lower readouts to higher-up convolutional layers,each readout can receive additional supervision from the local feature reconstruction loss,which equivalently imposes regularization on the model to reduce the risk of losing local representational ability and hence improve the model's generalization capacity.Moreover,to effectively extract all depths of global information,we introduce a self-attention mechanism to aggregate global feature information across different layers to obtain a final graph-level output.Analytical and experimental evaluations on a number of benchmark datasets show that the proposed model yields significant improvement of classification accuracies compared to state-of-the-art baselines.