Controlabilidade em redes complexas

Abstract

During the last 25 years, research related to complex systems brought new perspectives and methodologies to the study of social and natural phenomena. From the economic network formed by large corporations, to the dynamics of cellular processes in biology, there are countless applications and benefits of these advances. However, the non-determinism inherent to these systems has been a major impediment in the search for its controllability. The development of a control method capable of guiding a complex network to a desired configuration, through the manipulation of a few variables, would bring great contribution to the scientific understanding of some nature and society phenomena. Therefore, this study aims to evaluate an algorithm that, in a finite time, identify a subset of driver nodes in a graph of complex system. The study was based on the paper Controllability of Complex Network, of Liu et al. (2011), and motivated by the paper The Network of Global Corporate Control, of Battiston et al. The development was done in Java language, and the tests conducted with the aid of network simulation tools. Two greedy algorithms were developed, one with the heuristic of choosing the driver nodes with lesser degree, and another approximation one. The results of these algorithms were compared to the optimal algorithm as developed in paper Controllability of Complex Networks (LIU, 2011). There was obtained an average error of 6.25% in the case of the algorithm with heuristics choice to the smaller node and 73.41% for the greedy approximation algorithm. The origin of the choices that led to the proposed algorithm and the good results in tests justify continuing research to a MSc level.