可视化对 GraphViz 来说太大的无向图？

我需要建议渲染一个无向图的178,000个节点和500,000条边。我试过 Neato Tulip 和 Cytoscape。尼托甚至远远没有接近郁金香和 Cytoscape 声称他们可以处理，但似乎不能。(郁金香什么也不做，Cytoscape 声称正在工作，然后就停了下来。)

我只想要一个矢量格式的文件(ps 或 pdf)与一个远程合理的节点布局。

36281 次浏览
小开

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

一个可能的问题是，您似乎在寻找布局，而不仅仅是呈现。我对各种工具实现的布局的大 O 特征一无所知，但是凭直觉我猜测可能需要一个 很长时间来布局那么多的数据。

小开

它需要真正精确吗？

根据您试图完成的任务，可能只需要将10% 或1% 的数据量绘制成图表就足够了。(当然，它也可能完全无用，但这完全取决于可视化的目的)

小开

我建议您首先对数据进行一些预处理，例如将节点折叠为集群，然后将集群可视化。折叠将减少节点的数量，并使得诸如 Kamada-Kawai 或 Fruchterman-Reingold 之类的算法更容易呈现结果图。

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

Circos 是由生物信息学家开发的图形可视化软件，专门用于可视化基因组和其他极其庞大和复杂的数据集。

这是一个基于 PERL 的包，我希望这没有问题。

小开

Graphviz 本身提供了渲染大型图形的解决方案。

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

您可以在 Graphviz 网站本身的 http://www.graphviz.org/上找到这个软件的文档

要了解更多信息，这里是 高效和高质量的力定向图绘制，胡的一篇论文，描述了基本的技术和例子: Http://yifanhu.net/pub/graph_draw_small.pdf

还有一个网络档案版本: https://web.archive.org/web/20210812011222/http://yifanhu.net/PUB/graph_draw.pdf

小开

首先，我想附议外星人的建议，尝试 sfdp。这是大规模的 Neato 版本。

正如 OJW 建议的那样，您也可以只绘制 R2中的节点。你的边缘实际上提供了他所谓的“自然秩序”特别地，您可以绘制归一化图 Laplacian 的第二和第三特征向量的分量。这是 这个维基百科关于 SVD 的页面中的矩阵 L。您应该能够写下这个矩阵，而不需要理解其背后的线性代数。然后，将问题简化为近似计算一个大型稀疏矩阵的前几个特征向量。这通常是通过迭代方法完成的，并且在标准的线性代数包中实现。这种方法应该可以扩展到非常大的图。

小开

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

political blogging network

图表数据来自政治博客网络所描述的阿达姆和浏览在 “政治博客圈和2004年美国大选” pdf 链接 给你。如果放大，可以看到每个节点的博客 URL。

zoomed

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

提交答案