可视化GraphViz太大的无向图？

Question

我需要建议来渲染具有178,000个节点和500,000个边缘的无向图.我尝试过Neato,Tulip和Cytoscape.Neato甚至没有近距离接触,Tulip和Cytoscape声称他们可以处理它,但似乎无法做到.(郁金香什么也没做,Cytoscape声称工作,然后停止.)

我只是喜欢一个矢量格式文件(ps或pdf),它具有远程合理的节点布局.

Answer 1

Graphviz本身提供了渲染大图的解决方案.

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

您可以在graphviz网站上找到该软件的文档,网址为http://www.graphviz.org/

更多信息,描述基础技术和示例的论文可以在这里找到:http: //yifanhu.net/PUB/graph_draw_small.pdf

Answer 2

我建议您首先对数据进行一些预处理,例如将节点折叠到群集,然后可视化群集.折叠将减少节点数量,并使诸如Kamada-Kawai或Fruchterman-Reingold等算法更容易渲染结果图.

如果您确实需要可视化500.000个节点,那么您可以考虑使用简单的圆形布局.这将很容易渲染,而不会出现基于强制算法的问题.看看Circos:http://mkweb.bcgsc.ca/circos/

Circos是由生物信息学人员开发的图形可视化,专门用于可视化基因组和其他极大且复杂的数据集.

这是一个基于PERL的软件包,我希望这不会有问题.

Answer 3

我在python中使用图形工具库得到了很好的结果.下图有1,490个节点和19,090个边缘 - 在我的笔记本电脑上渲染大约需要5分钟.

图表数据来自亚当和概览中描述的政治博客网"的政治博客和2004年的美国大选" PDF链接在这里.如果放大,您可以看到每个节点的博客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')

Answer 4

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

Answer 5

Mathematica 很可能可以处理它，但我不得不承认我的第一反应是沿着评论说的“拿一张纸并将其涂成黑色”。有没有办法降低图的密度？

一个可能的问题是您似乎正在寻找布局，而不仅仅是渲染。我对各种工具实现的布局的 Big O 特性一无所知，但直觉上我猜想布局这么多数据可能需要很长时间。