可视化无向图对GraphViz来说太大了?

我需要build议使用178,000个节点和500,000条边来渲染无向图。 我试过Neato,郁金香和Cytoscape。 Neato甚至都不是很靠近,而Tulip和Cytoscape声称他们可以处理它,但似乎没有办法。 (郁金香什么都不做,Cytoscape声称工作,然后停下来。)

我只是喜欢一个vector格式文件(PS或PDF)与节点的远程合理的布局。

Graphviz本身提供了一个渲染大图的解决scheme。

也就是说,Graphviz包含sfdp ,这是一个多尺度版本的fdp(也在graphviz中,类似于neato),用于大型无向图的布局,对于在我的项目中绘制大图(70k节点,500k边)非常有用。

您可以在graphviz网站上find此软件的文档,url是http://www.graphviz.org/

更多的信息,一篇描述底层技术和例子的文章可以在这里find:http: //yifanhu.net/PUB/graph_draw_small.pdf

我build议您先对数据进行一些预处理,例如将节点折叠为群集,然后对群集进行可视化。 折叠将减less节点的数量,使诸如Kamada-Kawai或Fruchterman-Reingold等algorithm更容易渲染结果图。

如果你真的需要可视化500.000节点,那么你可以考虑使用简单的圆形布局。 这将很容易呈现没有基于力量的algorithm的问题。 看看Circos: http ://mkweb.bcgsc.ca/circos/

Circos是由生物信息学人员开发的graphics可视化工具,专为可视化基因组和其他极其庞大而复杂的数据集而量身定制。

这是基于PERL的包,我希望这不是问题。

我在Python中使用graphics工具库获得了很好的结果。 下面的图表有1,490个节点和19,090个边缘 – 大约需要5分钟在我的笔记本电脑上进行渲染。

政治博客网络

图表数据来自Adamic和Glance在“政治博客圈和2004年美国大选”中描述的政治博客networking。 如果放大,您可以看到每个节点的博客url。

放大

这是我用来绘制它的代码(博客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') 

试试Gephi ,它有一个名为OpenOrd的新布局插件,可以扩展到数百万个节点。

Mathematica很可能会处理这个问题,但是我不得不承认,我的第一个反应是按照“拿一张纸,把它染成黑色”的评论。 有没有办法减less图的密度?

一个可能的问题是,你似乎在寻找布局,而不仅仅是渲染。 我不了解各种工具所实现的布局的大O特点,但直觉上我猜可能需要长时间来布置这么多的数据。

它是否需要真正准确?

取决于你想要完成的事情,它可能足以描绘10%或1%的数据量。 (当然,这也可能是完全无用的,但这一切都取决于可视化的目的)

你可以试试aiSee: http ://www.aisee.com/manual/unix/56.htm

我期望边缘群集( http://www.visualcomplexity.com/vc/project_details.cfm?id=679&index=679&domain= )将有所帮助。 这种技术将相关的边缘捆绑在一起,减less了graphics的视觉复杂度。 你可能不得不自己实现这个algorithm。

BioFabric( http://www.BioFabric.org )是另一种可视化大图的工具。 它应该能够处理所描述的networking(178,000个节点和50万个边缘),虽然初始布局可能需要一些时间。 这里的networking展示(来自斯坦福大型networking数据集合)是斯坦福networkingnetworking,其具有281,903个节点和2,312,497个边缘:

斯坦福网络网络 BioFabric的可扩展性是由于它代表节点不是点而是水平线。 然后边缘显示为垂直线。 有关这个工作原理的一些直觉,有Super-Quick BioFabric演示 ,这是一个使用D3animation的小型networking。

主要的应用程序是用Java编写的。 目前,它只能导出PNG图像,而不是PDF。 有一个来自RBioFabric的PDF导出选项,虽然这是一个非常简单的实现,但无法处理真正的大型networking。

充分披露:BioFabric是我写的一个工具。

如果一切都失败了,你可以把这个文件的清理版本作为debugging场景提供给这些工具的开发者。

查看基于Java / Jython的GUESS: http : //graphexploration.cond.org/

大图布局(LGL)项目帮助了我很多与类似的问题。 它处理布局,并有一个小型的Java应用程序来绘制2D生成的布局。 没有vector输出框,所以你必须自己绘制图(给定由LGL生成的节点坐标)

一个窗口工具,可以可视化graphics是pajek ,它会产生一个eps输出,但我不知道它是否可以读取您的数据。

这里有一个应用程序列表: http ://www.mkbergman.com/?p= 414

Walrus和LGL是被认为适合大型图表的两种工具。 然而,这两个似乎都需要graphics作为文本文件input自己的特殊格式,这可能是一个痛苦。

我不认为你可以在一个平面布局中远程接近可视化。

我一直对这个研究报告中描述的双曲线图感兴趣。 尝试从SourceForge软件。

另一个想法是使用在Panopticode中看到的TreeMap来绘制节点。

您也可以尝试NAViGaTOR (披露:我是该软件的开发人员之一)。 我们已经成功地用多达170万个边缘可视化graphics。 虽然这样的大型networking很难操纵(用户界面会变得迟缓)。 但是,它确实使用OpenGL来实现可视化,因此一些开销被转移到了graphics卡上。

另外请注意,在成功打开一个很大的networking之前,您必须在文件 – >首选项对话框中调整内存设置。

最后,正如大多数其他答复指出的那样,最好将数据重新组织为更小更有意义的内容。

首先,我想第二个aliekens的build议尝试sfdp。 这是Neato的大规模版本。

正如OJW所build议的,你也可以在R2中绘制节点。 你的边缘实际上提供了他所说的“自然sorting”。 特别是可以绘制归一化graphics拉普拉斯算子的第二和第三特征向量的分量。 这是维基百科页面中有关谱聚类的matrixL 你应该能够写下这个matrix,而不理解它后面的线性代数。 然后,你已经减less了你的问题来近似计算一个大型稀疏matrix的前几个特征向量。 这是传统上通过迭代方法完成的,并且在标准线性代数包中实现。 这种方法应该扩大到非常大的图。

Interesting Posts