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

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

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

For more information, here is Efficient and high quality force-directed graph drawing, a paper by Yifan Hu describing the underlying techniques and examples: http://yifanhu.net/PUB/graph_draw_small.pdf

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

我建议您首先对数据进行一些预处理，例如将节点合并成簇，然后可视化这些簇。合并将减少节点数量，并使像Kamada-Kawai或Fruchterman-Reingold这样的算法更容易渲染生成的图形。

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

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

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

我使用Python中的 graph-tool 库取得了良好的结果。以下图形有1,490个节点和19,090条边-在我的笔记本上花了约5分钟才能呈现出来。

将此翻译成中文：

图表数据来自Adamic和Glance在《政治博客网络与2004年美国选举》中描述的政治博客网络。如果你放大，你可以看到每个节点的博客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 )

数学家可能很可能处理它，但我不得不承认我的第一反应是在评论中说“拿一张纸，涂黑它。”有没有办法减少图表的密度？

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

需要真正准确吗？

根据你想要实现的目标，仅绘制10％或1％的数据量可能足够好。 （当然，这也可能完全没有用处，但一切都取决于可视化的目的）

首先，我想支持aliekens的建议，尝试使用sfdp。它是Neato的大规模版本。

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