Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/8153| Título: | Controlabilidade em redes complexas |
| Autor(es): | Oliveira, Leonardo Presoto de |
| Orientador(es): | Lugo, Gustavo Alberto Giménez |
| Palavras-chave: | Teoria dos grafos Simulação (Computadores digitais) Algorítmos Graph theory Digital computer simulation Algorithms |
| Data do documento: | 9-Set-2014 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | OLIVEIRA, Leonardo Presoto de. Controlabilidade em redes complexas. 2014. 91 f. Trabalho de Conclusão de Curso (Graduação) – Universidade Tecnológica Federal do Paraná, Curitiba, 2014. |
| Resumo: | Durante os últimos 25 anos, pesquisas relacionadas a sistemas complexos trouxeram novas perspectivas e metodologias ao estudo de fenômenos sociais e naturais. Da rede econômica formada por grandes corporações, até a dinâmica de processos celulares em biologia, inúmeras são as aplicações e benefícios gerados por esses avanços. Entretanto, o não determinismo intrínseco a esses sistemas tem sido um grande empecilho na busca por sua controlabilidade (capacidade de ser controlar a rede). O desenvolvimento de um método de controle capaz de guiar uma rede complexa até uma desejada configuração, através da manipulação de poucas variáveis, traria grande contribuição na compreensão científica de alguns fenômenos emergentes da natureza e da sociedade. Sendo assim, esse trabalho tem como objetivo avaliar um algoritmo capaz de, em tempo finito, identificar um subconjunto de nós controladores(n´os que podem interferir no controle da rede) em um grafo de sistema complexo. O estudo foi fundamentado no artigo Controllability of Complex Networks, de LIU (2011), e motivado pelo artigo The Network of Global Corporate Control, de Battiston et al (2007). O desenvolvimento foi feito em linguagem Java, e os testes conduzidos com o auxilio de ferramentas de simulação de redes. Foram desenvolvidos dois algoritmos gulosos, um guloso com a heurística de escolher os nós com menor grau e outro guloso de aproximação. O resultado obtido com estes algoritmos foram comparados ao algoritmo ótimo desenvolvido no artigo Controllability of Complex Networks (LIU, 2011). Obteve-se um erro médio de 6,25% para o caso do algoritmo com a heurística de escolha do menor n´o e 73,41% para o algoritmo guloso de aproximação. A procedência das escolhas que levaram ao algoritmo proposto e os bons resultados apresentados nos testes podem justificar a continuidade da pesquisa à nível de um mestrado científico. |
| 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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/8153 |
| Aparece nas coleções: | CT - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| CT_ENGCOMP_2014_1_03.pdf | 1,15 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
