Avaliação comparativa entre medidas de redes complexas para a classificação de dados

Abstract

Complex networks are networks with nontrivial connection structures, which do not follow a regular or random pattern. Their usage for data classification has become an increasingly relevant research topic in recent years, with many techniques in the literature successfully exploring complex network properties and measures. In data classification, the use of complex networks allows to interpret and model semantic relationships among data items, enabling the detection of structural and topological patterns related, for example, to the formation pattern of the input data. Several measures of complex networks have already been used in this sense. However, a systematic study capable of characterizing the behavior and performance of such measures in the context of data classification is lacking in the literature. As there are many measures of complex networks that have different characteristics, this work consists of developing an experimental environment in order to analyze and compare the behavior of some measures, revealing more adequate measures for one or another circumstance. Specifically, the computational environment involves to build up a network by applying the k-nearest neighbor criterion over the input data, and to explore complex network measures through of the classification via pattern conformation (a.k.a. high-level classification). For this purpose, six complex network measures were selected from the literature, namely: assortativity, clustering coefficient, average degree, betweenness, shortest average path and closeness. For our analyses, both artificial and real-world data sets represented as feature vectors were considered. The results show that measures such as shortest average path and clustering coefficient, besides presenting better predictive performance in data sets with higher noise level, are also more robust to the variation of the network construction parameter. In summary, this research is an important initiative to support other related works in selecting more appropriate complex network measures for data classification.