Visualisation de très gros graphiques de liens

25

Je recherche un outil pour visualiser de très gros graphes de liens directionnels. J'ai actuellement environ 2 millions de nœuds avec environ 10 millions de bords. J'ai essayé quelques choses différentes, mais la plupart prennent des heures pour même faire des graphiques de nœuds de 100k

Ce que j'ai essayé:
j'ai passé une journée avec gephi, mais 80 000 nœuds prennent environ une heure à ajouter et l'application devient pratiquement inutile.

Aucune suggestion?

Une visualisation interactive serait un plus.

visualization labyrinthe
la source
Il serait utile que vous indiquiez ce que vous avez déjà essayé. Avez-vous essayé Graphviz?
Wolfgang Bangerth
1
Graphviz est ce que j'essaierais en premier. Aucune idée si cela fonctionnera avec quelque chose de cette taille. De toute évidence, vous aurez besoin de quelque chose qui utilise une représentation clairsemée pour la matrice d'adjacence, mais il semble inimaginable qu'un progiciel ne le ferait pas.
David Ketcheson
Je donne un coup de feu à Graphviz en ce moment, cela semble un peu plus prometteur, mais je ne pense pas que cela permette une interaction
madmaze
2
Avez-vous essayé d'interpréter le graphique comme une matrice clairsemée et de le visualiser avec MATLAB ou la fonction «espion» d'Octave? 10 millions d'entrées non nulles sont bien à la portée des ordinateurs de bureau moyennement puissants. Cela vous préparerait également à une bissection spectrale (trouver des partitions de votre graphique pourrait vous permettre de le visualiser plus facilement).
Jack Poulson
1
avez-vous envisagé de visiter?
pyCthon

Réponses:

13

Graphviz devrait fonctionner. Je crois que les images associées aux matrices dans la collection de matrices clairsemées de l' Université de Floride ont été visualisées à l'aide de sfdp, un algorithme de visualisation de graphiques à force dirigée développé par Yifan Hu. La plupart des matrices de la collection ont un temps de calcul associé à la génération d'une visualisation correspondante, vous pouvez donc être en mesure de rechercher des matrices dont les graphiques ont des caractéristiques similaires à celles que vous souhaitez visualiser. Par exemple, un graphique avec environ 2,1 millions de nœuds et environ 3 millions d'arêtes a nécessité Hu ~ 36000s pour générer, soit 10 heures. Bien qu'il ne soit pas clair quel matériel a été utilisé pour générer le graphique, il est probablement raisonnable de penser qu'un ordinateur de bureau ou un ordinateur portable a été utilisé, et le temps vous donnerait au moins une idée approximative du temps de rendu du graphique. L'algorithme de Hu semble être l'un des algorithmes de visualisation de pointe (il l'a publié en 2005), mais n'étant pas un expert dans le domaine, je ne peux pas dire s'il existe ou non de meilleurs algorithmes. Cet algorithme est inclus avec Graphviz en option, et est conçu pour être utilisé sur de grands graphiques tels que celui que vous décrivez.

Geoff Oxberry
la source
Très propre. Il semble que Barnes-Hut soit utilisé pour simuler des forces entre les nœuds du graphique, donc je suppose qu'une implémentation FMM parallèle pourrait produire une accélération significative. D'un autre côté, la méthode de Hu semble avoir une structure à plusieurs niveaux similaire à MeTiS, qui a tendance à être difficile à paralléliser.
Jack Poulson
Ouais, quand j'ai regardé le papier, je pensais aussi qu'une implémentation FMM parallèle pourrait être intéressante, mais je ne savais pas comment elle serait pratique, car je n'ai pas beaucoup d'expérience avec les algorithmes parallèles.
Geoff Oxberry
3
@JackPoulson - toux
Aron Ahmadia
@GeoffOxberry - voir le lien ci
Aron Ahmadia
1
@JackPoulson - Vous constaterez que les algorithmes de mise en page dirigés de force sont assez sensibles à l'ensemencement initial, il y a eu du bon travail fait par d'autres groupes pour reformuler le problème pour des mises en page plus esthétiques.
Aron Ahmadia
5

Voir Graphinsight 1.2, peut gérer facilement des millions de nœuds et est interactif et en 3D.

Vous pouvez également disposer des graphiques avec des millions de nœuds et d'arêtes avec des méthodes algébriques à haut rendement ou des méthodes dirigées par la force. Il est disponible en version d'essai pour évaluation ( Avertissement: je suis l'un des auteurs du programme ).

www.graphinsight.com

linello
la source
1
@linelio - Merci pour votre réponse et bienvenue sur scicomp! Veuillez consulter les règles relatives à la promotion et assurez-vous de divulguer clairement tout lien personnel lorsque vous faites des recommandations.
Aron Ahmadia
5

Voici quelques recommandations et liens collectés au fil du temps:

  • Pour les nœuds 2M, il est difficile de recommander quoi que ce soit ne connaissant pas votre matériel, et peut-être qu'une certaine réduction des données est en ordre, mais en prenant des éléments librement disponibles, zGrViewer peut répondre à vos besoins de visualisation (nécessite GraphViz).
  • Suivant l 'idée de @pyCthon, vous suggérons également de consulter VisIt pour une certaine interactivité dans le traçage.
  • Je revisite le igraphpackage pour le langage statistique R , qui comprend des algorithmes de mise en page soignés ( Fruchterman-Reingold et Kamada-Kawai ), entre autres.
  • La bibliothèque Large Graph Layout est maintenant sur SourceForge.
Chasseur de cerf
la source
0

Nous avons créé http://www.github.com/graphistry/pygraphistry pour permettre de le faire à partir de la plupart des navigateurs et des ordinateurs portables. L'idée est d'utiliser WebGL pour rendre les gros graphiques (pan / zoom / etc.), Et de décharger la plupart des calculs en temps réel (mise en page, filtre, etc.) sur un nuage GPU. Il est similaire à Gephi ou Cytoscape, mais avec plus de concentration sur les grands graphiques et l'analyse des données, et sur l'intégration dans le Web et les ordinateurs portables.

Leo Meyerovich
la source
0

Vous pouvez essayer "Tulip" [1], je pense qu'il peut gérer de très gros graphiques (au moins je l'ai essayé avec 10K à 100K nœuds et cela a bien fonctionné).

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

BrunoLevy
la source