Identificação de Nós Influentes em Redes Complexas

Resumo

Redes complexas são sistemas formados por elementos interconectados que exibem interações não triviais. Tradicionalmente, a teoria dos grafos provê o formalismo matemático para o estudo das relações entre objetos de um determinado conjunto, que são representados através de vértices (nós) e arestas [1]. No mundo real, convivemos a todo momento com sistemas que podem ser representados e estudados por redes complexas como: sistemas de cooperação social, infraestruturas de comunicação e sistemas de transporte. No contexto das redes complexas, os fenômenos de disseminação são cruciais, pois podem ser aplicados em problemas reais como interromper doenças contagiosas e melhorar a propagação de informações. Esses dois exemplos mostram direções opostas onde o processo de disseminação pode ser afetado. Remover uma fração de nós estruturais, ou seja, nós vitais, quebraria uma rede e impediria a disseminação de uma epidemia em grande escala. Em contraste, difundir informações de um conjunto de nós de origem, ou seja, nós influentes, maximizaria a escala de influência em uma rede. Logo, identificar e agir sobre os nós influentes permite uma mudança na estrutura e na função da rede de forma mais eficiente [3]. Existem diversos trabalhos na literatura relacionados com a identificação de nós influentes em redes complexas [2, 4, 5]. As métricas denominadas centralidades estruturais buscam estabelecer valores reais a cada nó na rede, onde se espera que os valores produzidos forneçam uma classificação de nós sujeitos à sua importância. Dentre as centralidades destacam-se: as centralidades de grau (CG), intermediação (CI) e proximidade (CP). Outras métricas valoram a importância dos nós mensurando, também, a influência de seus vizinhos, em uma espécie de efeito de aprimoramento mútuo. Nesse contexto, têm-se como exemplos a centralidade de auto vetor (CA) e alguns algoritmos de ranqueamento como o PageRank e HITS (Hyperlink-Induced Topic Search). Este último, classifica os nós com base em dois conceitos principais: hubs e autoridades. A ideia central é que hubs são nós que distribuem conexões para autoridades relevantes, enquanto autoridades são nós que recebem muitas conexões de hubs confiáveis. De fato, toda métrica ou algoritmo para identificação de nós influentes possuem prós e contras e o desempenho do método utilizado pode ser altamente diferente para diferentes redes ou sob diferentes parâmetros. Neste trabalho investigou-se a identificação de nós influentes em redes do tipo direcionadas. Uma rede direcionada não ponderada é representada por G = (V, E), onde V = {v₁, v₂, ..., v_n} e |V| é o número de nós (vértices) na rede. E = {e₁, e₂, ..., e_m} e |E| é o número de arestas na rede. A matriz de adjacência A = (a_ij) de um grafo G é uma matriz quadrada de dimensões |V| x |V| com i linhas e j colunas, sendo que a_ij será 1 se (i, j) ∈ E, caso contrário, será 0. Logo, o bit 1 demarca a existência de uma conexão (a, b) e o bit 0 demarca a inexistência dessa conexão e, para o caso de uma rede direcionada a_ij pode ser diferente de a_ji. O objetivo do trabalho é comparar métricas de centralidade clássicas (grau, intermediação, proximidade e autovalor) e o algoritmo HITS, realizando uma análise comparativa para investigar como cada métrica define os "nós influentes" e avaliar os impactos conforme a topologia e a função da rede (redes sociais, biológicas ou de infraestrutura). Para a análise, foram conduzidos experimentos computacionais utilizando a biblioteca NetworkX, permitindo a modelagem de redes complexas e a aplicação das diferentes métricas. Os experimentos foram realizados através de uma adaptação para redes direcionadas de redes clássicas como: Watts-Strogatz, Erdős-Rényi, e Barabási-Albert. Para comparar a precisão do ranqueamento dos nós influentes das métricas selecionadas, foi calculando o tamanho de maior caminho e a proporção de partes independentes das redes após a remoção de um percentual de nós melhores ranqueados. Obviamente, quanto maior a proporção de partes independentes, mais seriamente a rede é destruída e maior a precisão na identificação dos nós influentes. A análise, até o presente momento, demonstra que a maneira de avaliar os nós influentes de uma rede varia, significativamente, quando se adotam abordagens topológicas distintas. Portanto, a integração de diferentes métricas de centralidade revela que a influência dos nós em redes complexas não deve ser resumida a um único indicador. As diferentes topologia das redes e, também, as dinâmicas adotadas nelas, podem apresentar resultados distintos, refletindo a diversidade de papéis que os nós desempenham na transmissão de informações. Tal entendimento é vital para aprimorar a forma como se interpreta e gerencia os sistemas interconectados. [...]