Methods for the approximation of network centrality measures

Abstract

Centrality measures are an important analysis mechanism to uncover vital information about complex networks. However, these metrics have high computational costs that hinder their applications in large real-world networks. I propose and explain the use of artificial neural learning algorithms can render the application of such metrics in networks of arbitrary size. Moreover, I identified the best configuration and methodology for neural learning to optimize its accuracy, besides presenting an easy way to acquire and generate plentiful and meaningful training data via the use of a complex networks model that is adaptable for any application. In addition, I compared my prosed technique based on neural learning with different centrality approximation methods proposed in the literature, consisting of sampling and other artificial learning methodologies, and, I also tested the neural learning model in real case scenarios. I show in my results that the regression model generated by the neural network successfully approximates the metric values and is an effective alternative in real-world applications. The methodology and machine learning model that I propose use only a fraction of computing time with respect to other commonly applied approximation algorithms and is more robust than the other tested machine learning techniques.

Medidas de centralidades são um mecanismo importante para revelar informações vitais sobre redes complexas. No entanto, essas métricas exigem um alto custo computacional que prejudica a sua aplicação em grandes redes do mundo real. Em nosso estudo propomos e explicamos que através do uso de redes neurais artificiais podemos aplicar essas métricas em redes de tamanho arbitrário. Além disso, identificamos a melhor configuração e metodologia para otimizar a acurácia do aprendizado neural, além de apresentar uma maneira fácil de obter e gerar um número suficiente de dados de treinamento substanciais através do uso de um modelo de redes complexas que é adaptável a qualquer aplicação. Também realizamos um comparativo da técnica proposta com diferentes metodologias de aproximação de centralidade da literatura, incluindo métodos de amostragem e outros algoritmos de aprendizagem, e, testamos o modelo gerado pela rede neural em casos reais. Mostramos com os resultados obtidos em nossos experimentos que o modelo de regressão gerado pela rede neural aproxima com sucesso as métricas é uma alternativa eficiente para aplicações do mundo real. A metodologia e o modelo de aprendizagem de máquina que foi proposto usa apenas uma fração do tempo de computação necessário para os algoritmos de aproximação baseados em amostragem e é mais robusto que as técnicas de aprendizagem de máquina testadas