Layouts Direcionados por Força e o Force-Atlas2.

Layouts direcionados por força

Os Layouts de grafos direcionados por força são uma classe de algoritmos desenvolvidos para ilustrar grafos de uma maneira esteticamente agradável. Esses algoritmos posicionam nós de um grafo em duas ou três dimensões. Eles evitam o cruzamento de ligações (crossing-free layouts) tanto quanto possível. Os grafos alvos desse Layout atribuem forças entre o conjunto exercidas pelas ligações (ou Edges) que puxam os Nós. Abaixo exibe-se uma pequena imagem para refrescar a lembrança do que são Edges (ou links, ligações) e Nós (vértices):

As forças atrativas parecidas com as de uma mola, baseadas na lei de Hooke, são usadas para atrair pares de nós um para o outro, enquanto simultaneamente forças repulsivas como as de partículas carregadas eletricamente com base na lei de Coulomb são usadas para separar todos os pares de nós. Ou seja, em outras palavras, as ligações atraem e os nós se repulsam mutuamente. Em estados de equilíbrio para este sistema de forças, as bordas tendem a ter um comprimento uniforme (devido às forças da mola), e os nós que não estão conectados por uma borda tendem a ser afastados (por causa da repulsão elétrica). A atração da borda e as forças de repulsão do vértice podem ser definidas usando funções que não se baseiam no comportamento físico das molas e partículas; Por exemplo, alguns sistemas dirigidos por força usam molas cuja força atrativa é logarítmica em vez de linear.

Abaixo uma ilustração de um sistema de molas procurando uma versão mais estável que permaneça em repouso pelo equilíbrio de forças, o que gera uma versão de visual mais "organizado":

O Layout Force-Atlas2

Force-Atlas2 é um dos layouts desenvolvidos como um plugin do Gephi e seu objetivo é desenhar um gráfico mais intelegível ao usuário. Seguindo um modelo orientado pela força, esse plugin veio para resolver algumas falhas da sua primeira versão, a qual se denominava Force-Atlas e apresentava processamento muito lento para Grafos de maior tamanho. Essas falhas foram corrigidas realizando um balanceamento entre a qualidade do layout final e a velocidade do algoritmo computacional. Para grandes redes o ForceAtlas-2 possui muito melhor desempenho do que o Force-Atlas, com tempos de resposta bem menores. O Force-Atlas continua existindo no Gephi, foi mantido como plugin apenas por continuidade, mas de fato tornou-se obsoleto após o lançamento do Force-Atlas-2. O Force-Atlas2 pode ser modificado por alguns parâmetros para variar o layout de acordo com as necessidades de análise. Abaixo a imagem exibe todos os parâmetros do Force-Atlas-2 acessíves na aba "Layout":

Abaixo um breve comentário sobre cada parâmetro de configuração do ForceAtlas-2: Threads Number – O número de threads que irá executar o algoritmo. De forma simplificada, define o número de tarefas que vão rodar em paralelo para gerar o Grafo submetido ao novo formato. O limite desse número de depende de quantos Núcleos (cores) o processador do computador possui. Dissuade Hubs – Hubs são nós que apresentam muitos “out-degrees”, ou seja, são origem de um grande número de ligações (edges) direcionadas. Os nós que apresentam alto grau de saída são considerados autoridades. Para entender o grau (degree), grau de entrada(in-degree) e grau de saída (out-degree), vejamos a imagem a seguir:

Os conceitos de Hubs e autoridades são muito utilizados nos layouts orientados por força. No layout force-atlas, usar o parâmetro Dissuade-hubs significa privilegiar as autoridades (nós que possuem muitas ligações de entrada ou in-degrees), as quais ficaram em regiões mais centrais dos Clusters. Os hubs (nós que possuem muitas ligações de saída) por sua vez serão direcionados com mais força às periferia dos clusters.

LingLog Mode – O modo LinLog (Linear-Logaritmo) possibilita que os clusters fiquem mais esticados. O modo padrão é atração linear e repulsão linear. O LinLog chaveia para atração linear e repulsão logarítmica.

Prevent Overlap – Evita sobreposição de nós.

Scaling – Define a proximidade dos nós no Grafo resultante. Um “scaling” baixo vai resultar em um grafo denso; já um scaling alto vai resultar em um grafo esparso.

Stronger Gravity – Define se a maioria dos nós deve ser também atraída para o centro do Grafo, uma espécie de maior gravidade.

Gravity – Define o valor da força de gravidade aplicada ao gráfico.

Tolerância – Similar ao parâmetro Inertia no layout Force Atlas (versão obsoleta), um valor menor resulta numa execução mais lenta mas com maior precisão no fim, valores maiores resultam em mais velocidade mas menos precisão.

Approximate Repulsion – Usa um tipo de otimização chamada Barnes-Hut para melhorar a repulsão de uma forma geral.

Além dos parâmetros ora apresentados, há um botão de Reset no "Layout" do Force Atlas-2 que permite que todos os parâmetros sejam redefinidos para valores pré-estabelecidos.

Para saber mais sobre Algoritmos de desenho de gráfico dirigido por força: https://arxiv.org/pdf/1201.3011.pdf

Para saber mais sobre o Force Atlas 2: http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098679

Na próxima postagem veremos mais alguns detalhes sobre Layouts aplicados sobre Grafos. Até lá!