Feeds:
Posts
Comentários

Archive for the ‘redes complexas’ Category

Assume-se que em redes existe a formação de comunidades que são definidas como grupo de vértices que tem uma grande densidade de arestas entre eles e com pouca densidade de arestas entre groupos (Newman, The structure and function of complex networks).

É possível visualizar e identificar as comunidades com o R e o pacote igraph. O código abaixo (criado com uma força do pessoal do LEB-USP, que tem familiaridade com o assunto) é uma função bem simples, com a qual se pode criar uma rede com atração preferencial e depois visualizar as comunidades, separadas por cor e letra- é usado o algorítmo walktrap para identificar as comunidades. Ainda, adota-se a terminologia pequena, moderada e grande, para atração preferencial dos vértices.

# Loads the tibrary
library(igraph)
communityD<-function(nodes,alpha){

  # it creates a network
  g<-barabasi.game(n=nodes,power=alpha,m=2,directed=FALSE);

  # it tries to identify densily connected vertices
  gWT<-walktrap.community(g,steps=5);

  # adding colours & labels to community members
  indices<-gWT$membership+1;
  col<-rainbow(max(indices));
  V(g)$color<-col[indices];
  V(g)$label<-intToUtf8((indices+64),multiple=TRUE);

  # it creates layout and plots the graph
  gLayout<-layout.fruchterman.reingold(g);
  plot(g,layout=gLayout,vertex.size=16);
  title('Barabási game/ Comunidades');
}

Este slideshow necessita de JavaScript.

Anúncios

Read Full Post »

Uma rede é  constutuída de vértices e arestas. Com estes elementos é possível descrever redes reais, por exemplo, redes genéticas na qual os vértices representam genes, proteínas e as arestas representam as interações químicas, ou ainda, nas ciências sociais, os vértices representam  indivíduos e as arestas a intereção entre eles. Uma vez que a rede é construída, é possível estudar o seu comportamento e suas características.

Muitas redes reais apresentam uma característica em comum, a sua topologia é livre de escala, que pode ser traduzida da seguinte maneira: a probabilidade de um vértice estar ligado a outro vértice decai exponencialmente, ou melhor, muitos vértices estão ligados com poucos vértices e poucos vértices interagem com um número muito grande de vértices. Em termos matemáticos, isso é modelado por uma lei de potência negativa com o expoente entre 1 e 3. Só para se ter uma idéia do que isso significa, é como se a maioria das pessoas tivessem por volta de 30 amigos e algumas pessoas (os mais populares) terem dezenas de milhares de amigos (é só uma exemplo fictício).

Não se tem muitas pistas a respeito do motivo que leva redes reais a ter essa característica. Entretanto, em um report na science de 1999, Barabási sugere que isso pode ser atribuído ao preferential attachment. A idéia é mais ou menos a seguinte, suponha que poucas pessoas morem num bairro qualquer e são amigas entre si. Novos moradores chegam ao bairro, então, de acordo com a teoria da atração preferencial, esses novos moradores tem uma maior probabilidade de fazer contato com os mais antigos no bairro, seja porque eles conhecem mais detalhes da vida no bairro ou por qualquer outro motivo.

A atração preferêncial rendeu 9000 citações (mais ou menos) e um livro (Linked , fala mais sobre o assunto sem uma linguagem técnica), pois é capaz de construir redes com características de redes reais livres de escala. Mas, ainda assim, não explica alguns fenômenos.

De qualquer maneira, é possível, com o pacote igraph no R, gerar grafos (redes) usando um algorítmo baseado nessa teoria, lá vai um exemplo (no final, o código gera uma visualização, com histograma e rede no mesmo plot, um subplot, com sugestão do pessoal do LEB-USP):

# Carrega o pacote igraph
library(igraph)
# cria a rede: n= número de nós, power= "poder de atração", m=número de links cada nó faz quando entra na rede
g<-barabasi.game(n=50,power=1,m=2,directed=FALSE);
# it creates layout and plots the graph
gLayout<-layout.fruchterman.reingold(g);
X11() # evita problemas no RStudio criando uma nova janela
plot(g,layout=gLayout,vertex.size=16);
title('Barabási game');
par(fig=c(2/3,1,2/3,1), new=T)
hist(degree(g), main="")
title('Histograma');

As imagens são geradas para um mesmo número de vértices (50) e  de arestas (98), mudando apenas o alpha, relacionado com a atração preferencial (adota-se a terminologia pequena, moderada e grande, relativo aos próprios alfas).

Este slideshow necessita de JavaScript.

Note, que os histogramas mostram a distribuição do degree (grau, número de links que cada nó tem). Não fiz a as contas para mostra se são realmente livres de escala ou não, mas dá para perceber que com o aumento da atração preferencial, há nós com muito mais links que os outros.

Read Full Post »

Com o Cairo é possível produzir imagens alta qualidade em diferentes formatos. Instalar esse pacote para o R no Ubuntu foi pode ser um pouco problemático, considerando que eu nunca tive problemas com esse tipo de coisa. A soluçõa para esse problema foi bem simples, no terminal, instalar as bibliotecas:

sudo apt-get install libcairo2-dev
sudo apt-get install libxt-dev

E pronto!

(Fonte: http://groups.google.com/group/rapache/browse_thread/thread/df9958ec1e96c2b9/7226805f11e94b14?pli=1)

Só para dar um exemplo da utilização do Cario, eu criei uma rede direcional com o pacote igraph e simulei um modelo epidêmico SI (suscetível/infectado) bem simples. Com as imagens, eu animei com o imageMagick. Abaixo, o resultado.


Resumidamente, o código é o seguinte:

# indicar o caminho da pasta do onde serão armazenados as imagens, necessário para rodar o comando system(), abaixo
setwd("caminho do diretório");

# carregando o pacote
library(“Cairo”);
for(i in 1:tempo){

#rotina dentro do loop…

# produção das imagens
CairoPNG(paste("caminho do diretório", "/", sprintf("nome%04d.png", i), sep=""), width=400, height=400);
plot(...);
title(main="título", font=2);
dev.off();
}
# convertendo as imagens num gif animado, esse comando é executado fora do R
system("convert -delay 20 *.png gif_animado.gif");
# agora, excluindo as imagens da pasta (opcional, é claro)
file.remove(list.files(pattern=".png"));

Eu sei que é possível criar animações com o pacote animate, sem precisar executar o imageMagick, mas decidi pelo imageMagick só por praticidade.

Read Full Post »