Redes complexas: Teoria e aplicações
Por Isáira Leite e Lopes
Os avanços computacionais oportunizaram uma maior viabilidade da coleta, armazenamento e processamento de algoritmos sobre dados estruturalmente complexos. Neste sentido, as redes complexas têm despontado como uma poderosa ferramenta, potencialmente utilizada na representação, caracterização, classificação, análise e modelagem de uma variedade de sistemas complexos. Os sistemas complexos abrangem um campo multidisciplinar, visto que integram diversas áreas como biologia, economia, lingüística, medicina, ciências sociais, tecnologia e transporte. Exemplos de sistemas complexos que tem sido objetos de interesse científico incluem: redes em epidemiologia, redes biológicas, redes sociais, a internet e a World Wide Web. As redes complexas representam de forma simplificada os sistemas complexos, definidos pela interação de muitos componentes. Desta forma, entende-se como uma rede, qualquer sistema passível de representação matemática abstrata na forma de um grafo, em que os nós (vértices) identificam os componentes do sistema e a presença de uma relação ou interação entre os componentes são representadas por um conjunto de elos de ligação (arestas). O padrão de interação entre os componentes de um sistema e sua dinâmica define a estrutura da rede. Assim, os pesquisadores tem investigado a estrutura das redes para responder as seguintes questões científicas, por exemplo:
i) Qual a relevância do nó no funcionamento da rede?,
ii) Qual o comportamento da rede frente a exclusão ou adição de um nó? e
iii ) Quais as propriedades das redes que influenciam determinado processo?
Estas abordagens fornecem insights sobre as regras e os processos fundamentais que governam a formação, manutenção e funcionamento de um sistema.
Fonte: Mosaico de imagens retiradas do Google.
Nos últimos anos, os avanços computacionais tem impulsionado a coleta e armazenamento de dados. Desta forma, há uma crescente demanda por ferramentas adequadas para o processamento de dados estruturalmente complexos. Neste sentido, as redes complexas têm despontado como uma poderosa ferramenta, potencialmente utilizada na representação, caracterização, classificação, análise e modelagem de uma variedade de sistemas complexos. Há uma gama de sistemas complexos que permeiam diversas áreas da ciência, como biologia, economia, lingüística, medicina, ciências sociais, tecnologia e transporte. Assim, as pesquisas em redes complexas têm ganhado relevância com um caráter multidisciplinar (COSTA et al., 2007; COSTA; RODRIGUES; CRISTINO, 2008).
Mas o que são redes complexas? Estas redes consistem em uma representação dos sistemas complexos de uma forma simplificada, sendo os sistemas complexos definidos como a interação de muitos componentes altamente interconectados. Historicamente, o estudo das redes iniciou com o desenvolvimento do ramo da matemática discreta, conhecido como teoria dos grafos. O nascimento dessa teoria é atribuído ao matemático suíço Leonhard Euler por ter solucionado, em 1736, o problema das sete pontes de Königsberg que cruzavam o rio Pregel, conectando duas ilhas. O problema consistia em encontrar uma viagem de ida e volta que atravessasse exatamente uma vez as pontes da cidade. Euler estudou o problema utilizando uma abstração matemática denominada de grafo, em que cada parte da cidade era representada por meio de pontos (vértices/nós) e as pontes da cidade eram as ligações (arestas) que conectavam esses pontos. Ele demonstrou que não existia solução para o problema. A falta de solução foi relacionada ao número ímpar de conexões (ligações) dos vértices, assim com estes vértices só seria possível iniciar ou terminar o caminho, sendo necessário passar mais de uma vez por uma mesma ligação (Figura 1) (BOCCALETTI et al., 2006; SILVA; ZHAO, 2016; NEWMAN, 2003).
Fonte: Figura 1 - O centro da cidade de Königsberg (a), o mapa esquemático do problema das pontes de Königsberg (b) e sua representação na forma de grafo (c)1. [Link]
Neste sentido, uma rede é compreendida como qualquer sistema passível de representação matemática abstrata na forma de um grafo. O grafo (Figura 2) é uma estrutura simples constituída por um conjunto de nós (vértices) que identificam os componentes do sistema e por um conjunto de elos de ligação (arestas) que denotam a presença de uma relação ou interação entre os componentes.
Fonte: Newman (2003).
Basicamente, as redes podem ser classificadas como direcionadas ou não direcionadas, em que as arestas da rede têm ou não algum sentido de orientação. Também podem ser ponderadas ou não-ponderadas, sendo as arestas da rede associadas a algum valor (custo ou distância) ou com todas as arestas assumindo os mesmos valores, representados pela presença (1) ou ausência (0) de uma relação entre seus componentes. Diferentes relações entre os componentes de uma rede podem ser exemplificadas como:
a) A relação de contato entre as pessoas na transmissão de um vírus (redes em epidemiologia).
b) A relação planta-polinizador na dinâmica de transferência de pólen e sucesso reprodutivo das plantas (redes ecológicas).
c) A relação de interação entre os usuários do Twitter baseada no uso de hashtags para interpretar ações políticas e coletivas (redes sociais).
d) A relação de voos diretos entre aeroportos na detecção da vulnerabilidade do transporte aéreo em cenários de interrupção operacional de aeroportos (redes de transporte).
e) A relação de teleconexão entre as chuvas que determinam seu padrão de frequência e intensidade numa região (redes climáticas).
A estrutura das redes, determinada por suas relações, é parte essencial do processo de extração de características e conhecimento das propriedades relevantes em um sistema, seja em nível de nós ou da rede, por completo. Portanto, o interesse científico tem sido despertado de modo a revelar o padrão de interação entre os componentes de um sistema, o impacto desses componentes em processos inerentes ao seu funcionamento e a relevância dos mesmos no comportamento e dinâmica de um sistema.
Referências:
BOCCALETTI, S. et al. Complex networks: Structure and dynamics. Physics Reports, Amsterdam, v. 424, n. 4/5, p. 175–308, 2006.
COSTA, L. D. F. et al. Characterization of complex networks: A survey of measurements. Advances in Physics, Abingdon, v. 56, n. 1, p. 167–242, 2007.
COSTA, L. DA F.; RODRIGUES, F. A.; CRISTINO, A. S. Complex networks: The key to systems biology. Genetics and Molecular Biology, Ribeirão Preto, v. 31, n. 3, p. 591–601, 2008.
NEWMAN, M. E. J. The Structure and Function of Complex Networks. SIAM Review, v. 45, n. 2, p. 167–256, 2003.
SILVA, T.C.; ZHAO, L. Machine Learning in Complex Networks. Cham: Springer International Publishing, 2016.
Para acesso a estudos complementares, leiam:
BESSON, M. et al. Complex Ecological Networks. In: FATH, B. D. (Ed.). Encyclopedia of Ecology. 2. ed. Oxford: Elsevier, 2019, p. 536–545.
LIAO, H. et al. Ranking in evolving complex networks. Physics Reports, Amsterdam, v. 689, p. 1–54, 2017.
MARIANI, M. S. et al. Nestedness in complex networks: Observation, emergence, and implications. Physics Reports, Amsterdam, v. 813, p. 1–90, 2019.