Hiển thị đồ thị vô hướng quá lớn so với GraphViz?

Question

Tôi cần lời khuyên để hiển thị biểu đồ không được chiếu với 178.000 nút và 500.000 cạnh. Tôi đã thử Neato, Tulip và Cytoscape. Neato thậm chí không đến từ xa, và Tulip và Cytoscape tuyên bố rằng họ có thể xử lý nó nhưng dường như không thể. (Tulip không làm gì và Cytoscape tuyên bố sẽ hoạt động, và sau đó chỉ dừng lại.)

Tôi muốn một tệp định dạng vector (ps hoặc pdf) với bố cục hợp lý từ xa của các nút.

Answer 1

Công cụ cửa sổ có thể trực quan hóa đồ thị là pajek, nó tạo ra đầu ra eps, tuy nhiên tôi không biết liệu nó có thể đọc dữ liệu của bạn hay không.

Answer 2

Bạn có thể cung cấp một phiên bản đã được vệ sinh của tệp cho nhà phát triển các công cụ đó dưới dạng một tình huống gỡ lỗi, nếu tất cả đều thất bại.

Answer 3

Mathematica rất có khả năng xử lý nó, nhưng tôi phải thừa nhận phản ứng đầu tiên của tôi là dọc theo dòng bình luận cho biết "lấy một mảnh giấy và tô màu đen." Không có cách nào để giảm mật độ của đồ thị?

Một vấn đề có thể xảy ra là dường như bạn đang tìm kiếm bố cục chứ không chỉ hiển thị. Tôi không có kiến ​​thức về đặc điểm Big O của bố cục được triển khai bởi nhiều công cụ khác nhau, nhưng theo trực giác tôi đoán rằng có thể mất thời gian dài để bố trí nhiều dữ liệu đó.

Answer 4

Có một danh sách các ứng dụng ở đây: http://www.mkbergman.com/?p=414

Walrus và LGL là hai công cụ được cho là phù hợp với đồ thị lớn. Tuy nhiên, cả hai dường như yêu cầu đồ thị được nhập dưới dạng tệp văn bản theo định dạng đặc biệt của riêng chúng, điều này có thể là một nỗi đau.

Answer 5

Bạn có thể thử aiSee: http://www.aisee.com/manual/unix/56.htm

Answer 6

Tôi không nghĩ rằng bạn có thể đến từ xa gần với hình dung rằng trong một bố cục phẳng.

Tôi đã bị hấp dẫn bởi Hyperbolic Graphs, described in this research paper trong một thời gian. Dùng thử phần mềm từ SourceForge.

Một ý tưởng khác chỉ là vẽ đồ thị các nút bằng cách sử dụng TreeMap như được thấy tại Panopticode.

Answer 7

Kiểm tra Java/Jython dựa GUESS: http://graphexploration.cond.org/

Answer 8

Có cần phải thật sự chính xác không?

Tùy thuộc vào những gì bạn đang cố gắng thực hiện nó có thể đủ tốt để chỉ đồ thị 10% hoặc 1% khối lượng dữ liệu. (tất nhiên, nó có thể hoàn toàn vô dụng, nhưng tất cả phụ thuộc vào những gì trực quan hóa)

Answer 9

Tôi đề nghị trước tiên bạn nên thực hiện một số tiền xử lý dữ liệu, ví dụ thu hẹp các nút thành cụm và sau đó hiển thị các cụm. Việc thu gọn sẽ làm giảm số lượng nút và giúp các thuật toán như Kamada-Kawai hoặc Fruchterman-Reingold dễ dàng hơn để hiển thị biểu đồ kết quả.

Nếu bạn thực sự cần hình dung 500.000 nút thì bạn có thể cân nhắc sử dụng bố cục hình tròn đơn giản. Điều này sẽ dễ dàng hiển thị mà không có các vấn đề mà các thuật toán dựa trên lực lượng có.Hãy xem Circos: http://mkweb.bcgsc.ca/circos/

Circos là hình ảnh hóa đồ thị được phát triển bởi những người tin học sinh học, được thiết kế để hình dung bộ gen và các bộ dữ liệu cực kỳ lớn và phức tạp khác.

Đây là gói dựa trên PERL, tôi hy vọng điều đó không có vấn đề.

Answer 10

Tôi mong đợi phân cụm cạnh (http://www.visualcomplexity.com/vc/project_details.cfm?id=679&index=679&domain=) sẽ hữu ích. Kỹ thuật này bao gồm các cạnh liên quan với nhau, làm giảm độ phức tạp của biểu đồ. Bạn có thể phải thực hiện các thuật toán cho mình mặc dù.

Answer 11

Large Graph Layout (LGL) dự án đã giúp tôi rất nhiều với một biểu tượng tương tự. Nó xử lý bố cục và có một ứng dụng java nhỏ để vẽ các bố cục được sản xuất theo dạng 2D. Không có đầu ra vector ra khỏi hộp, do đó bạn sẽ phải tự vẽ đồ thị (cho các tọa độ nút do LGL sản xuất)

Answer 12

Bạn cũng có thể thử NAViGaTOR (tiết lộ: Tôi là một trong những nhà phát triển cho phần mềm đó) . Chúng tôi đã hình dung thành công các đồ thị có tới 1,7 triệu cạnh với đồ thị. Mặc dù các mạng lớn như vậy khó có thể thao tác được (giao diện người dùng sẽ bị lag). Tuy nhiên, nó sử dụng OpenGL để hiển thị nên một số chi phí trên được chuyển sang card đồ họa.

Cũng lưu ý rằng bạn sẽ phải quay lên cài đặt bộ nhớ trong hộp thoại Tệp-> Tùy chọn trước khi bạn có thể mở thành công mạng lớn.

Cuối cùng, như hầu hết các câu trả lời khác chỉ ra, bạn nên tổ chức lại dữ liệu của mình thành một thứ nhỏ hơn và có ý nghĩa hơn.

Answer 13

Hãy thử Gephi, plugin có bố cục mới được gọi là OpenOrd có quy mô đến hàng triệu nút.

Answer 14

Bản thân Graphviz cung cấp giải pháp để hiển thị biểu đồ lớn.

Cụ thể, Graphviz bao gồm sfdp, phiên bản đa chiều của fdp (cũng có trong graphviz, tương tự như neato) để bố trí đồ thị vô hướng lớn hữu ích cho việc vẽ đồ thị lớn (70k nút, cạnh 500k) trong dự án của tôi.

Bạn có thể tìm thấy tài liệu cho phần mềm này trên trang web graphviz tự tại http://www.graphviz.org/

biết thêm thông tin, một bài báo mô tả các kỹ thuật cơ bản và các ví dụ có thể được tìm thấy ở đây: http://yifanhu.net/PUB/graph_draw_small.pdf

Answer 15

Trước tiên, tôi muốn để đề nghị của aliekens thứ hai để thử sfdp. Đây là phiên bản quy mô lớn của Neato.

Khi OJW đề xuất bạn cũng có thể vẽ các nút trong R2. Các cạnh của bạn thực sự cung cấp cái mà anh ta gọi là "thứ tự tự nhiên". Đặc biệt, bạn có thể vẽ các thành phần của các thành phần thứ hai và thứ ba của đồ thị chuẩn hóa Laplacian. Đây là ma trận L trong this wikipedia page about spectral clustering. Bạn sẽ có thể viết ra ma trận này mà không hiểu đại số tuyến tính đằng sau nó. Sau đó, bạn đã giảm bớt vấn đề của bạn để tính toán gần một số eigenvectors đầu tiên của một ma trận thưa thớt lớn. Điều này thường được thực hiện bằng các phương thức lặp và được thực hiện trong các gói đại số tuyến tính chuẩn. Phương pháp này nên mở rộng lên các đồ thị rất lớn.

Answer 16

Tôi đã có kết quả tốt bằng cách sử dụng thư viện graph-tool trong python. Biểu đồ dưới đây có 1.490 nút và 19.090 cạnh - mất khoảng 5 phút để hiển thị trên máy tính xách tay của tôi.

Đồ thị dữ liệu đến từ các mạng blog chính trị được mô tả bởi A-đam và nháy mắt trong liên kết “The political blogosphere and the 2004 US Election” pdf here. Nếu bạn phóng to, bạn có thể xem các url blog cho mỗi nút.

Dưới đây là đoạn code tôi sử dụng để vẽ nó (blog 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 17

BioFabric (www.BioFabric.org) là một công cụ cho phép biểu diễn đồ thị lớn. Nó có thể xử lý mạng được mô tả (178.000 nút và 500.000 cạnh) OK, mặc dù bố cục ban đầu có thể mất một lúc. Mạng hiển thị ở đây (từ Bộ sưu tập dữ liệu mạng lớn của Stanford) là Mạng lưới Stanford, có 281,903 nút và 2,312,497 cạnh:

Khả năng mở rộng của BioFabric là do nó đại diện cho các nút không phải là điểm, nhưng đường ngang. Các cạnh được hiển thị dưới dạng các đường thẳng đứng. Đối với một số trực giác về cách thức hoạt động, có Super-Quick BioFabric Demo, là một mạng nhỏ được làm động bằng D3.

Ứng dụng chính được viết bằng Java. Hiện tại, nó chỉ có thể xuất các hình ảnh PNG chứ không phải các tệp PDF. Có một tùy chọn xuất PDF từ RBioFabric, mặc dù đó là triển khai rất đơn giản nhưng không thể xử lý các mạng thực sự lớn.

Tiết lộ đầy đủ: BioFabric là công cụ mà tôi đã viết.