Visualizando Gráficos de Link Muito Grandes

25

Estou procurando uma ferramenta para visualizar gráficos de links direcionais muito grandes. Atualmente, tenho ~ 2 milhões de nós com bordas de ~ 10 milhões. Eu tentei algumas coisas diferentes, mas a maioria leva horas para fazer gráficos de 100k nós

O que eu tentei:
passei um dia com gephi, mas os nós de 80K levam cerca de uma hora para adicionar e o aplicativo se torna praticamente inútil.

Alguma sugestão?

Uma visualização interativa seria uma vantagem.

visualization madmaze
fonte
Seria bom se você declarasse o que já tentou. Você deu uma chance ao Graphviz?
Wolfgang Bangerth
1
Graphviz é o que eu tentaria primeiro. Não faço ideia se funcionará com algo desse tamanho. Obviamente, você precisará de algo que use uma representação esparsa para a matriz de adjacência, mas parece inimaginável que um pacote de software não o faria.
David Ketcheson 19/09/12
Im dando Graphviz um tiro agora, parece um pouco mais promissor, mas eu não acho que permite a interação
madmaze
2
Você já tentou interpretar o gráfico como uma matriz esparsa e visualizá-lo com a função "espião" do MATLAB ou Octave? 10 milhões de entradas diferentes de zero estão ao alcance de desktops moderadamente poderosos. Isso também o configuraria para a bissecção espectral (encontrar partições do seu gráfico pode facilitar a visualização).
precisa saber é o seguinte
1
você olhou para visitar?
PyCthon #

Respostas:

13

Graphviz deve funcionar. Acredito que as imagens associadas às matrizes na coleção de matrizes esparsas da Universidade da Flórida foram visualizadas usando o sfdp, um algoritmo de visualização de gráficos dirigido por força desenvolvido por Yifan Hu. A maioria das matrizes na coleção tem um tempo computacional associado à geração de uma visualização correspondente; portanto, você pode procurar matrizes cujos gráficos tenham características semelhantes às que você deseja visualizar. Por exemplo, um gráfico com ~ 2,1 milhões de nós e ~ 3 milhões de bordas levou Hu ~ 36000s para gerar, ou 10 horas. Embora não esteja claro qual hardware foi usado para gerar o gráfico, é provável que seja um palpite razoável de que um desktop ou laptop foi usado, e os horários forneceriam pelo menos uma idéia aproximada de quanto tempo a renderização do gráfico pode levar. O algoritmo de Hu parece ser um dos algoritmos de visualização de última geração (ele o publicou em 2005), mas não sendo um especialista na área, não posso falar se existem ou não algoritmos melhores. Esse algoritmo está incluído no Graphviz como uma opção e foi projetado para ser usado em gráficos grandes, como o que você descreve.

Geoff Oxberry
fonte
Muito arrumado. Parece que Barnes-Hut está sendo usado para simular forças entre os nós do gráfico, então eu suponho que uma implementação paralela do FMM possa produzir uma aceleração significativa. Por outro lado, o método de Hu parece ter uma estrutura multinível semelhante ao MeTiS, que tende a ser difícil de paralelizar.
22812 Jack Poulson
Sim, quando olhei para o jornal, também pensei que uma implementação paralela do FMM poderia ser interessante, mas não tinha certeza de quão prático seria, pois não tenho muita experiência com algoritmos paralelos.
22612 Geoff Oxberry
3
@JackPoulson - tosse
Aron Ahmadia
@GeoffOxberry - veja o link acima
Aron Ahmadia
1
@JackPoulson - Você verá que os algoritmos de layout direcionados à força são bastante sensíveis à propagação inicial; houve um bom trabalho feito por outros grupos para reformular o problema para obter layouts mais estéticos.
Aron Ahmadia
5

Veja Graphinsight 1.2, pode lidar com milhões de nós facilmente e é interativo e em 3D.

Você também pode criar gráficos de layout com milhões de nós e arestas com métodos algébricos de alta eficiência ou métodos direcionados por força. Está disponível na versão de avaliação para avaliação ( Isenção de responsabilidade: sou um dos autores do programa ).

www.graphinsight.com

linello
fonte
1
@linelio - Obrigado pela resposta e seja bem-vindo ao scicomp! Consulte as regras sobre promoção e não se esqueça de divulgar claramente qualquer conexão pessoal ao fazer recomendações.
Aron Ahmadia 21/10/12
5

Aqui estão algumas recomendações e links coletados ao longo do tempo:

  • Para nós da 2M, é difícil recomendar qualquer coisa que não conheça o seu hardware e, possivelmente, alguma redução de dados esteja em ordem, mas, levando material disponível gratuitamente, o zGrViewer pode atender às suas necessidades de visualização (requer o GraphViz).
  • Seguindo a ideia do @pyCthon, sugira que você também dê uma olhada no VisIt para obter alguma interatividade na plotagem.
  • Estou revisitando o igraphpacote para a linguagem estatística R , que inclui algoritmos de layout simples ( Fruchterman-Reingold e Kamada-Kawai ), entre outros.
  • A biblioteca de layout de gráfico grande agora está no SourceForge.
Deer Hunter
fonte
0

Criamos http://www.github.com/graphistry/pygraphistry para permitir isso na maioria dos navegadores e notebooks. A idéia é usar o WebGL para renderizar grandes gráficos (panorâmica / zoom / etc.) E descarregar a maior parte da computação em tempo real (layout, filtro etc.) para uma nuvem de GPU. É semelhante ao Gephi ou Cytoscape, mas com um foco maior em grandes gráficos e análise de dados, além de integrar-se à Web e notebooks.

Leo Meyerovich
fonte
0

Você pode tentar o "Tulip" [1], acho que ele pode lidar com gráficos muito grandes (pelo menos eu tentei com 10K a 100K nós e funcionou bem).

[1] http://tulip.labri.fr/TulipDrupal/

BrunoLevy
fonte