Neste artigo damos continuidade a nosso estudo sobre as propriedades das redes complexas. Nos artigos anteriores vimos que redes complexas são esparsas, livres de escala e formadas por vários agrupamentos de nós. Estamos mostrando estas propriedades em redes complexas reais, cujos dados podem ser acessados publicamente. São elas: Facebook, Erdos, Energia e Proteína.
Geralmente, redes complexas tendem a ser conectadas, i.e., formando uma única componente conectada ou uma grande componente que se destaca entre as demais. Contudo, o levantamento de informação em uma rede complexa pode ser custoso e propenso à não incluirmos relações e indivíduos que poderiam modificar as propriedades daquela rede.
Por exemplo em redes de Proteína, a descoberta de interações entre as proteínas (que formam os enlaces desta rede) dependem de métodos experimentais ou computacionais complexos e relativamente caros que investigam as interações uma a uma (em nossa rede de proteínas isso equivale a 2.035.153 experimentos).
Já em redes sociais online, como a rede Facebook, se não tivermos acesso direto à base de dados, teremos que reconstruir a rede com base na amostragem das redes de amizades de diferentes indivíduos, o que pode nos levar a deixar de capturar uma parte significativa da rede. Note que este não foi o caso da rede em estudo que, segundo seus autores, foi fornecida pelo próprio Facebook.
Em todo caso, excetuando a rede Energia, as redes em estudo apresentam múltiplas componentes conectadas, conforme mostra a tabela abaixo. A Tabela mostra o número de componentes na rede, coluna Componentes; o tamanho da maior componente conectada em quantidade de nós (o percentual indica a fração dos nós totais que pertencem à componente conectada); e a conectividade ($\epsilon$), que mede a quantidade de caminhos existentes dentre os possíveis.
Nas redes Facebook e Erdos tratam-se de poucas componentes com poucos nós isolados, já que respectivamente mais de 99% e 97% dos nós pertencem a maior componente conectada. Isso se confirma pelo elevado índice de conectividade da rede.
Contudo, na rede Proteína temos um valor expressivo de 185 componentes que abrangem aproximadamente 19% dos nós. No entanto estas componentes, embora sejam muitas, tendem a ser muito pequenas se comparadas à maior componente conectada. A conectividade da rede aponta para isso, já que se houvesse uma outra componente grande, a conectividade tenderia a ser maior.
No histograma abaixo vemos como os nós da rede Proteína estão divididos entre as suas componentes, excluídos os nós da maior componente. Como se pode ver, uma parte considerável (52 nós) está completamente isolada e aproximadamente metade dos nós (180 deles) estão dispostos como duplas de nós conectadas entre si, mas desconectadas de todo o resto. O restante dos nós está disposto nas demais componentes que possuem 3, 4, 5 e 6 nós.
Perceba que o fato de redes complexas serem comumente conexas (ou terem uma componente conectada que se destaca muito dentre as demais) é impressionante se considerarmos a grande quantidade de nós e a esparsidade destas redes. Mas, mais interessante ainda, e se eu lhe dissesse que este resultado é conhecido desde a década de 60 do século XX?
Pois bem, este resultado faz parte dos estudos de Erdös e Rényi acerca das redes aleatórias. Ok, eu sei que estou devendo falar mais sobre as redes aleatórias. Ainda pagarei esta dívida. Por hora vamos dizer que é um método usado para construir redes fictícias com inserção aleatória de enlaces entre os nós, de forma equiprovável. Só atenção para não confundir a rede Erdos que estamos estudando, que é uma rede de co-autoria real, com os modelos fictícios aleatórios que Erdös criou.
Voltando ao resultado, Erdös e Rényi mostraram em seu trabalho On the evolution of random graphs, publicado em 1960, entre outras coisas, que
em uma rede aleatória se o grau médio da rede for maior do que 1, então teremos uma grande componente conectada contendo a maior parte dos nós da rede.
Isso quer dizer que, mesmo em uma rede onde as ligações são feitas aleatoriamente, para uma quantidade de nós, há uma certa quantidade de arestas a partir da qual os nós passam a integrar uma grande componente. Trazendo para o nosso estudo, nós já vimos que nossas redes possuem grau médio acima de 1, portanto, pelo resultado de Erdös e Rényi, era de se esperar a formação de uma única grande componente conectada.
Comentários
Postar um comentário