77

178,000 個のノードと 500,000 個のエッジを持つ無向グラフをレンダリングするためのアドバイスが必要です。Neato、Tulip、Cytoscape を試しました。Neato は遠く離れたところまで来ていないし、Tulip と Cytoscape はそれを処理できると主張しているが、できないようだ. (Tulip は何もせず、Cytoscape は機能していると主張し、その後停止します。)

ノードのリモートで合理的なレイアウトを備えたベクター形式のファイル (ps または pdf) が欲しいだけです。

4

6 に答える 6

29

Graphviz自体は、大きなグラフをレンダリングするためのソリューションを提供します。

つまり、Graphvizにはsfdp、プロジェクトで大きなグラフ（70kノード、500kエッジ）を描画するのに役立つ、大きな無向グラフのレイアウト用のfdpのマルチスケールバージョン（これもgraphvizにあり、neatoに似ています）が含まれています。

このソフトウェアのドキュメントは、graphviz Webサイト自体（http://www.graphviz.org/ ）にあります。

詳細については、効率的で高品質の力指向グラフ描画をご覧ください。これは、基礎となる手法と例を説明するYifan Huによる論文です。http： //yifanhu.net/PUB/graph_draw_small.pdf

And a web archive version: 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 リンクで説明している政治的なブログ ネットワークから取得されます。ズームインすると、各ノードのブログ 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')
于 2014-10-07T21:46:08.470 に答える
4

Mathematica で処理できる可能性は非常に高いですが、私の最初の反応は、「1 枚の紙を取り、黒く塗ってください」というコメントに沿ったものだったことを認めなければなりません。グラフの密度を下げる方法はありませんか?

考えられる問題は、レンダリングだけでなく、レイアウトを探しているように見えることです。さまざまなツールによって実装されたレイアウトのビッグ オーの特性についての知識はありませんが、直観的には、それだけのデータをレイアウトするには長い時間がかかるのではないかと推測します。

于 2008-10-27T16:46:26.517 に答える
3

本当に正確である必要がありますか？

達成しようとしていることに応じて、データ量の 10% または 1% をグラフ化するだけで十分な場合があります。(もちろん、まったく役に立たないこともありますが、それは視覚化の目的によって異なります)

于 2009-05-27T16:34:39.857 に答える
0

まず、sfdp を試すという aliekens の提案に賛成したいと思います。ネイトの大型版です。

OJW が示唆するように、R2 にノードをプロットすることもできます。あなたのエッジは、彼が「自然な秩序」と呼ぶものを実際に提供します。特に、正規化されたグラフ ラプラシアンの 2 番目と 3 番目の固有ベクトルの成分をプロットできます。これは、スペクトル クラスタリングに関するこのウィキペディア ページのマトリックスLです。背後にある線形代数を理解していなくても、この行列を書き留めることができるはずです。次に、大規模なスパース行列の最初のいくつかの固有ベクトルを近似的に計算するように問題を減らしました。これは伝統的に反復法によって行われ、標準の線形代数パッケージに実装されています。この方法は、非常に大きなグラフにスケールアップする必要があります。

于 2012-06-19T00:46:32.443 に答える