Visualiser un graphique Non dirigé trop grand pour GraphViz?

Graphviz lui-même fournit une solution pour rendre de grands graphiques.

à savoir, Graphviz comprend sfdp , une version multiscale de fdp (également en graphviz, similaire à Neato) pour la mise en page de grands graphiques non dirigés qui a été utile pour dessiner de grands graphiques (70K noeuds, 500K bords) dans mon projet.

vous pouvez trouver de la documentation pour ce logiciel sur le site Web de graphviz lui-même à http://www.graphviz.org /

pour plus d'informations, Un article décrivant les techniques sous-jacentes et des exemples peut être trouvé ici: http://yifanhu.net/PUB/graph_draw_small.pdf

je suggère que vous fassiez d'abord un prétraitement des données, par exemple l'affaissement des Noeuds en clusters, puis la visualisation des clusters. L'affaissement réduira le nombre de noeuds et facilitera le rendu du graphe résultant par des algorithmes tels que Kamada-Kawai ou Fruchterman-Reingold.

si vous avez vraiment besoin de visualiser 500.000 noeuds, alors pouvez-vous envisager d'utiliser une disposition circulaire simple. Cela sera facile à rendre sans les questions qui les algorithmes. Jetez un oeil aux Circos: http://mkweb.bcgsc.ca/circos /

Circos est une visualisation graphique développée par des spécialistes de la bioinformatique et conçue pour visualiser des génomes et d'autres ensembles de données extrêmement vastes et complexes.

c'est un paquet PERL, j'espère que ce n'est pas problématique.

j'ai eu de bons résultats en utilisant la bibliothèque graph-tool en python. Le graphique ci - dessous a 1.490 noeuds et 19.090 bords-il a fallu environ 5min pour rendre sur mon ordinateur portable.

les données des graphiques proviennent du réseau de blogs politiques décrit par Adamic et coup d'oeil dans " la blogosphère politique et l'élection américaine de 2004 " lien pdf ici . Si vous zoom avant vous pouvez voir les urls de blog pour chaque noeud.

voici le code que j'ai utilisé pour le dessiner (blog http://ryancompton.net/2014/10/22/stochastic-block-model-based-edge-bundles-in-graph-tool / ):

import graph_tool.all as gt
import math

g = gt.collection.data["polblogs"] #  http://www2.scedu.unibo.it/roversi/SocioNet/AdamicGlanceBlogWWW.pdf
print(g.num_vertices(), g.num_edges())

#reduce to only connected nodes
g = gt.GraphView(g,vfilt=lambda v: (v.out_degree() > 0) and (v.in_degree() > 0) )
g.purge_vertices()

print(g.num_vertices(), g.num_edges())

#use 1->Republican, 2->Democrat
red_blue_map = {1:(1,0,0,1),0:(0,0,1,1)}
plot_color = g.new_vertex_property('vector<double>')
g.vertex_properties['plot_color'] = plot_color
for v in g.vertices():
    plot_color[v] = red_blue_map[g.vertex_properties['value'][v]]

#edge colors
alpha=0.15
edge_color = g.new_edge_property('vector<double>')
g.edge_properties['edge_color']=edge_color
for e in g.edges():
    if plot_color[e.source()] != plot_color[e.target()]:
        if plot_color[e.source()] == (0,0,1,1):
            #orange on dem -> rep
            edge_color[e] = (255.0/255.0, 102/255.0, 0/255.0, alpha)
        else:
            edge_color[e] = (102.0/255.0, 51/255.0, 153/255.0, alpha)            
    #red on rep-rep edges
    elif plot_color[e.source()] == (1,0,0,1):
        edge_color[e] = (1,0,0, alpha)
    #blue on dem-dem edges
    else:
        edge_color[e] = (0,0,1, alpha)

state = gt.minimize_nested_blockmodel_dl(g, deg_corr=True)
bstack = state.get_bstack()
t = gt.get_hierarchy_tree(bstack)[0]
tpos = pos = gt.radial_tree_layout(t, t.vertex(t.num_vertices() - 1), weighted=True)
cts = gt.get_hierarchy_control_points(g, t, tpos)
pos = g.own_property(tpos)
b = bstack[0].vp["b"]

#labels
text_rot = g.new_vertex_property('double')
g.vertex_properties['text_rot'] = text_rot
for v in g.vertices():
    if pos[v][0] >0:
        text_rot[v] = math.atan(pos[v][1]/pos[v][0])
    else:
        text_rot[v] = math.pi + math.atan(pos[v][1]/pos[v][0])

gt.graph_draw(g, pos=pos, vertex_fill_color=g.vertex_properties['plot_color'], 
            vertex_color=g.vertex_properties['plot_color'],
            edge_control_points=cts,
            vertex_size=10,
            vertex_text=g.vertex_properties['label'],
            vertex_text_rotation=g.vertex_properties['text_rot'],
            vertex_text_position=1,
            vertex_font_size=9,
            edge_color=g.edge_properties['edge_color'],
            vertex_anchor=0,
            bg_color=[0,0,0,1],
            output_size=[4024,4024],
            output='polblogs_blockmodel.png')

Try Gephi , il a un nouveau plugin de mise en page appelé OpenOrd qui se balance à des millions de noeuds.

Mathematica pourrait très probablement le gérer, mais je dois admettre que ma première réaction a été dans le sens du commentaire qui dit "prendre un morceau de papier et le colorier en noir."Il n'y a pas moyen de réduire la densité du graphe?

un problème possible est que vous semblez être à la recherche de mise en page, pas seulement le rendu. Je n'ai aucune connaissance des caractéristiques du Big O des mises en page Mises en œuvre par divers outils, mais intuitivement, je suppose que cela pourrait prendre un long temps de présenter que beaucoup de données.

doit-il être vraiment précis?

selon ce que vous essayez d'accomplir, il pourrait être assez bon de simplement graphe 10% ou 1% du volume de données. (bien sûr, cela pourrait aussi être complètement inutile, mais tout dépend de ce à quoi sert la visualisation)

vous pouvez essayer aiSee: http://www.aisee.com/manual/unix/56.htm

je m'attends à bord de clustering ( http://www.visualcomplexity.com/vc/project_details.cfm?id=679&index=679&domain= ) pourrait l'aider. Cette technique regroupe les arêtes reliées ensemble, réduisant la complexité visuelle du graphe. Vous devrez peut-être implémenter l'algorithme vous-même.

BioFabric ( www.BioFabric.org ) est un autre outil pour visualiser les grands graphiques. Il devrait être capable de gérer le réseau décrit (178 000 noeuds et 500 000 arêtes) OK, bien que la disposition initiale peut prendre un certain temps. Le réseau de montrer ici (à partir de la Stanford Grand jeu de données Réseau de Collecte) est le Stanford Réseau internet, qui a 281,903 nœuds et 2,312,497 bords:

L'évolutivité de BioFabric est due au fait que il représente les nœuds non pas comme des points, mais comme des lignes horizontales. Les bords sont alors représentés par des lignes verticales. Pour une certaine intuition sur la façon dont cela fonctionne , il y a le Démo BioFabric Super-Quick , qui est un petit réseau qui est animé en utilisant D3.

l'application principale est écrite en Java. Pour le moment, il ne peut exporter que des images PNG, pas des PDF. Il existe une option D'exportation PDF de RBioFabric , bien que ce soit un très simple mise en œuvre qui ne peut pas encore gérer de très grands réseaux.

divulgation complète: BioFabric est un outil que j'ai écrit.

vous pourriez offrir une version aseptisée du fichier aux développeurs de ces outils comme un scénario de débogage, si tout le reste échoue.

Découvrez la version Java/Jython de GUESS: http://graphexploration.cond.org/

Large Graph Layout (LGL) le projet m'a beaucoup aidé avec un ptoblème similaire. Il gère la mise en page et dispose d'une petite application java pour dessiner les mises en page produites en 2D. Aucun vecteur de sortie hors de la boîte donc vous devrez dessiner le graphe vous-même (étant donné les coordonnées de noeud produites par LGL)

un outil windows qui peut visualiser les graphiques est pajek , il génère une sortie eps, cependant je ne sais pas si elle peut lire vos données.

il y a une liste d'Applications ici: http://www.mkbergman.com/?p=414

le Morse et le LGL sont deux outils soi-disant adapté pour les grands graphes. Cependant, les deux semblent exiger que les graphiques soient entrés sous forme de fichiers texte dans leur propre format spécial, ce qui peut être pénible.

Je ne pense pas que vous puissiez vous approcher de la visualisation dans un plan plat.

J'ai été intrigué par graphiques hyperboliques, décrit dans ce document de recherche depuis un certain temps. Essayez le logiciel de SourceForge .

une autre idée est de représenter graphiquement les noeuds en utilisant un TreeMap comme vu à Panopticode .

vous pouvez également essayer NAViGaTOR (divulgation: je suis l'un des développeurs pour ce logiciel). Nous avons visualisé avec succès des graphes avec jusqu'à 1,7 million de bords. Bien que de tels grands réseaux soient difficiles à manipuler (l'interface utilisateur sera lag). Cependant, il utilise OpenGL pour la visualisation de sorte qu'une partie de la charge est transférée sur la carte graphique.

notez également que vous devrez activer les paramètres de mémoire dans le La boîte de dialogue Fichier - > Préférences avant de pouvoir ouvrir un réseau aussi grand.

enfin, comme la plupart des autres réponses le soulignent, il est préférable de réorganiser vos données en quelque chose de plus petit et plus significatif.

tout d'abord, je voudrais appuyer la suggestion d'aliekens d'essayer le sfdp. C'est la grande échelle de Neato.

comme OJW suggère que vous pourriez aussi simplement tracer les noeuds dans R2. Vos bords fournissent ce qu'il appelle une "commande naturelle"."En particulier, vous pouvez tracer les composants des deuxième et troisième vecteurs propres du graphique normalisé Laplacian. C'est la matrice L dans cette page de wikipedia sur le clustering spectral . Vous devrait être en mesure d'écrire cette matrice sans la compréhension de l'algèbre linéaire derrière elle. Ensuite, vous avez réduit votre problème au calcul approximatif des premiers vecteurs propres d'une grande matrice clairsemée. Cela est traditionnellement fait par des méthodes itératives et est mis en œuvre dans les paquets d'algèbre linéaire standard. Cette méthode devrait passer à des graphiques très grands.