Algorithms and Applications in Complex Network Representation, Classification and Manipulation

Abstract

A complex network is a useful model for many real-world systems. Recently, much effort has been put into studying the insights of the complex network. This thesis is all about the study of complex networks. Based on the study, this thesis can be broadly divided into three parts: The first one involves analysing a complex network to find a crucial network structure called constant community by extracting and applying some features called graph representations. The second part involves the study of the quality of the graph representations on a downstream task, i.e., the node classification task. In the third part, we tried to apply the handcrafted and automatically learned graph features to some real-world scenarios, i.e., in brain networks. While detecting the constant community, we developed two strategies to construct and use the graph representations: semi-supervised and unsupervised. In the semi-supervised approach, we converted the original graph to its corresponding line graph, where a node in the line graph represents an edge in the original graph. We then applied a graph neural network (GNN) as a graph representation learning tool to classify the nodes in the line graph, which in turn was used to capture the constant communities in the original graph. In the unsupervised approach, using some hand-crafted features for each edge in the original network, we developed some novel algorithms inspired by image threshold algorithms to filter out the non-constant community edges and hence find the constant communities. In the semi-supervised approach, we noticed that when we reduced the number of training nodes, the representational capability of GNN decreased, and as a result, the classification accuracy of GNN drastically dropped. This phenomenon led us to develop input and output intervention methods to improve the accuracy of the GNN. In the input intervention, we extend the training nodes’ set using random walk and some machine learning methods to agnostically capture similar nodes from various non-contiguous sub-networks in a whole network. In the output intervention, we used random walk methods to correctly relabel the possibly misclassified nodes by the GNN as its output. The last part of the thesis deals with applications of network representation, classification, and finally manipulation in dealing with complex human brain networks. The brain regions and their interrelationships can be modelled using complex network. Utilising the complex network and its representation, in this part we contributed to neuroscience in two ways: first, we devised a methodology to diagnose a neurodevelopmental disease called Attention Deficit Hyperactivity Disorder (ADHD) using some extracted network features and applied them to various deep learning-based models. Then in the second work, we built a probabilistic model using anatomical and topological similarities to generate synthetic brain networks and track down the progression of a neurodegenerative disease called Alzheimer’s disease (AD) in human brains. The results are promising enough to establish the use of complex network analysis in computational neurology