Particionamento ou Clusterização- Parte 01.
Obrigado por ter chegado (ou tolerado?) até aqui. Você possivelmente você já leu os meus posts anteriores. Vou listá-los abaixo para o caso de haver interesse (ou saco?) em revê-los e iniciar a leitura em ordem crono(lógica). Assim você poderá acompanhar desde o começo as minhas divagações, as quais podem parecer um pouco desconexas quando lidas fora de ordem:
Vamos falar hoje um pouco sobre Particionamento ou Clusterização.
Particionamento
Clusterização é um processo frequentemente usado na análise exploratória dos Grafos. Refere-se ao processo de classificar os nós ou os links (edges ou ligações) de forma que aqueles com determinados atributos ou propriedades similares fiquem no mesmo "conglomerado". Clusterização, na análise de grafos, é sinônimo de Particionamento. Vamos ver como realizar particionamento (ou clusterização) de grafos usando alguns parâmetros no Gephi. A imagem abaixo mostra um grafo antes e depois de um particionamento.
E daí?...para que serve essa coisa inútil? Para fazer bolinhas coloridas agrupadas? Não, essa função já está ocupada pelo cara que enche balões em festas de aniversários infantis! :-)
Particionamento pode parecer inútil, mas não o é. Clique aqui e veja as coisas preciosas (parabéns, FGV!) que estão descobrindo por aí misturando um pouco de Gephi e Redes Sociais da Internet como o Twitter...E, se você não gosta muito dessas redes sociais cibernéticas e faz o perfil mais científico, que tal dar uma olhada num estudo de transtornos de saúde baseado em rede de Genes Humanos aqui. Pense em quaisquer "coisas" conectadas...ali você achará uma aplicação útil para Análise de Grafos.
Ei, psiu, clique nos links acima se desejar, mas não deixe de voltar para terminar de ler minhas viagens na maionese!
Particionando Grafos tomando como base atributos dos Nós
O Gephi, software já tratado em nosso primeiro post e cujo download você pode efetuar aqui, vem com alguns grafos prontos e pré-instalados que podem ser explorados para fins de aprendizado inicial, mas acredito que um outro grafo (que pode ser baixado da internet) é mais adequado ao objetivo desta postagem. Esse grafo é o "Jazz", o qual pode ser baixado aqui. O formato do download é ".zip", então por favor descompacte-o em uma pasta de fácil acesso antes de prosseguir (você vai precisar abrir o arquivo dentro em pouco). Após a descompactação você obterá o arquivo "Jazz.net". Como o próprio nome diz, esse é um grafo que contém relações entre cantores de Jazz. E o que sua vida tem a ver com cantores de Jazz? Provavelmente nada, não é? Muito menos a minha :-). Essa é a mágica da análise de grafos: aplica-se a quase tudo, desde linhas de metrô, estudo de bactérias, genes, rotas, sociologia, etc. Pense e você achará uma aplicação útil...eu estou estudando a análise de grafos na minha área atualmente, e definitivamente nada tem a ver com Jazz.
Essa rede - a Jazz - foi descrita pelos seus criadores da seguinte forma:
"Usando uma base de dados de gravações de jazz, estudamos a rede de colaboração de músicos. Definimos a rede em dois níveis diferentes. Primeiro, estudamos a rede de colaboração entre indivíduos, onde dois músicos estão conectados se tocaram na mesma banda. Então, consideramos a colaboração entre bandas, onde duas bandas estão conectadas se tiverem um músico em comum. A análise da estrutura da comunidade revela que essas construções captam ingredientes essenciais das interações sociais entre músicos de jazz. Observamos correlações entre locais de gravação, segregação racial e estrutura da comunidade. Uma análise quantitativa da distribuição do tamanho da comunidade revela uma semelhança surpreendente com uma rede social baseada em e-mail recentemente estudada."
Para saber mais sobre a rede Jazz, clique aqui.
Agora vamos descobrir, usando a modularidade previamente explicada, quantas comunidades de cantores de jazz existem na rede referenciada. E lembre-se: eu não conheço nada de Jazz, mas o Gephi vai me ajudar a descobrir algo sobre os músicos desse ritmo.
Quando o Gephi é iniciado, podemos ver a seguinte tela:
Selecione, "Open Graph File", navegue até a pasta onde você salvou o arquivo jazz.net recém baixado e o abra.
O seguinte Grafo será aberto:
Após abrir o Grafo, parto do pressuposto que você sabe usar as ferramentas básicas da barra de ferramentas do Gephi. Caso ainda não tenha essa familiaridade, don't worry, estou preparando um post sobre essas ferramentas (zoom, seleção, etc), em alguns dias estará no ar.
Vamos agora aprender como particionar o Grafo com base em atributos de nós, e, em seguida, atribuir as cores desejadas a esses nós para visualizarmos claramente essas comunidades particionadas. Antes disso vamos entender o conceito de Modularidade.
Modularidade - Cálculo que detecta comunidades. Mede o quão bem uma rede se decompõe em comunidades menores e modulares. Um alto índice de modularidade indica estrutura interna sofisticada. Essa estrutura, muitas vezes chamada de estrutura da comunidade, descreve como a rede é compartimentada em sub-redes. Essas sub-redes (ou comunidades) podem ter significado importante no mundo real.
Vamos calcular a modularidade da rede Jazz, partindo do pressuposto que você esteja usando o Gephi versão 0.9.1:
Procure na Interface do Gephi a aba "Statistics" (caso ela não esteja aparecendo, vá até Window=>Statistics e a faça aparecer!).
Após abrir a aba Statistics, selecione clique na opção "Modularity=>Run", conforme abaixo:
Antes do cálculo da Modularidade do Grafo, dois parâmetros devem ser configurados, conforme a tela abaixo:
O parâmetro "Randomize" produz resultados mais precisos em termos de decomposição de comunidades, no entanto ele aumenta o tempo computacional do cálculo. O parâmetro "Use weights" implica que a força (ou peso) da ligação (edge) será levada em consideração no cálculo da Modularidade. Clique Ok.
Após o cálculo da Modularidade, um relatório será mostrado apresentado o número de nós por Classe de Modularidade (cada classe = uma comunidade), conforme abaixo:
Veja que o relatório informou haver encontrado 4 (quatro) comunidades. Agora vamos aplicar aos nós uma propriedade relacionada à sua cor a partir da modularidade previamente calculada, ou seja cada comunidade terá nós da mesma cor. Vamos colorir os nós de acordo com a comunidade a qual pertencem.
Vá até o painel Appearance. Caso esse painel não esteja visível, vá até o menu superior "Window" e marque a opção "Appearance". Após isso, selecione a opção "Nodes" e depois "Partition". Na caixa de seleção logo abaixo, selecione "Modularity Class", ou seja, a estatística que você acabou de calcular.
Depois de seguir essas etapas, clique em "Apply" para aplicar as quatro diferentes cores (uma cor para cada das quatro comunidades encontradas pela modularidade). Note antes de aplicar as cores, você poderá alterá-las usando a opção "Palette" (parte de baixo da aba "Appearance").
Você vai obter algo semelhante à figura abaixo (perceba os nós, agora coloridos):
Ainda que ter tornado os nós coloridos seja bem animador, nosso grafo ainda não parece com comunidades de Jazz...em verdade mais assemelha-se ao samba do crioulo doido. Quem poderá nos ajudar a separar essas comunidades geradas - mas ainda misturadas? A resposta já foi estudada em post anterior - os algoritmos direcionados por força. Ora, vamos aplicar o Layout Force Atlas no Grafo colorido. Caso queira conhecer mais sobre os algoritmos direcionados por força, veja meu post a respeito aqui.
Para aplicar o Force Atlas, vá até a aba Layout, selecione a opção correspondente ao citado Layout e clique em Run, você obterá um resultado conforme abaixo:
Ora, ora, se não são as quatro comunidades de cantores de Jazz encontradas no cálculo da modularidade, separadas no espaço por cores, cada nó no seu Cluster (ou Partição) adequado? E não foi necessário chamar o rapaz que enche os balões das festas infantis :-).
Obrigado por chegar ao fim, sua paciência é notável!
Novidade: Você pode ver o passo a passo desse post sendo executado em um vídeo clicando AQUI.
Na próxima postagem veremos mais alguns detalhes sobre Particionamento. Até lá!
