77

我需要有关渲染具有 178,000 个节点和 500,000 条边的无向图的建议。我尝试过 Neato、Tulip 和 Cytoscape。Neato 甚至都无法接近，Tulip 和 Cytoscape 声称他们可以处理它，但似乎无法处理。（Tulip 什么都不做，Cytoscape 声称正在工作，然后就停止了。）

我只是想要一个具有远程合理布局的节点的矢量格式文件（ps 或 pdf）。

4

6 回答 6

29

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

即，Graphviz 包括sfdp一个多尺度版本的 fdp（也在 graphviz 中，类似于neato），用于布局大型无向图，这对于在我的项目中绘制大型图（70k 节点，500k 边）很有用。

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

欲了解更多信息，这里是Efficient and high quality force-directed graph drawing，由 Yifan Hu 撰写的描述底层技术和示例的论文：http: //yifanhu.net/PUB/graph_draw_small.pdf

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

于 2011-02-23T16:07:34.577 回答
21

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

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

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

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

于 2009-06-02T01:36:11.917 回答
20

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

政治博客网络

图表数据来自 Adamic 和 Glance 在“政治博客圈和 2004 年美国大选”中描述的政治博客网络</a>此处的 pdf 链接。如果放大，您可以看到每个节点的博客网址。

放大

这是我用来绘制它的代码（博客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')
于 2014-10-07T21:46:08.470 回答
4

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

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

于 2008-10-27T16:46:26.517 回答
3

它需要真正准确吗？

根据您要完成的工作，仅绘制 10% 或 1% 的数据量可能就足够了。（当然，它也可能完全没用，但这完全取决于可视化的用途）

于 2009-05-27T16:34:39.857 回答
0

首先，我想第二个 aliekens 的建议尝试 sfdp。它是 Neato 的大型版本。

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

于 2012-06-19T00:46:32.443 回答