Network optimization based on Genetic Algorithms for high-level classification via complex networks

Abstract

Network-based classification has demonstrated its value especially due to its inherent capacity to capture the properties of networked data (e.g., structural and dynamical). However, its performance depends heavily on the network architecture. In this sense, we present a method for optimizing network architecture using genetic algorithms (GAs) for the classification via characterization of importance. The importance based classification is a recent network classification technique that employs the pagerank measure to capture the underlying data relationship. In particular, we hypothesize that the prominent characteristics of GAs, such as their robust search mechanism and binary representation, may provide a more effective network architecture. Further, in an effort to capture the relationships between the networked data, we also analyze, despite pagerank, other network measures, namely degree, betweenness, closeness, and shortest path length. In summary, experimental findings using real data sets demonstrated that the proposed algorithm outperforms the widely used k-nearest neighbors graph method in terms of classification accuracy. They also show competitive results against a state-of-the-art network optimization technique based on swarm intelligence. Meanwhile, for the network measures, results revealed that pagerank and degree produced the best outcomes and statistically outperformed all other network measures in terms of predictive capability and robustness. Our technique was also applied to the detection of autism spectrum disorder from salivary data processed by the attenuated total reflectance Fourier-transform infrared (ATR-FTIR) spectroscopy. In the experiments, GA outperformed both linear discriminant analysis, a widely adopted technique in ATR-FTIR analysis, and support vector machine, a state-of-the art technique for such problems. Moreover, these results give evidence about the potential of our approach in dealing with such a difficult problem, characterized by high-dimensional data and arbitrary distributions.