Мне нужен совет для рендеринга неориентированного графика с 178 000 узлов и 500 000 ребер. Я пробовал Neato, Tulip и Cytoscape. Neato даже не отдаляется близко, и Tulip и Cytoscape утверждают, что могут справиться с этим, но, похоже, не в состоянии. (Тюльпан ничего не делает, и Cytoscape утверждает, что он работает, а затем просто останавливается.)
Мне просто нужен файл в формате (ps или pdf) с дистанционно разумным расположением узлов.
Graphviz сам предоставляет решение для рендеринга больших графов.
А именно, Graphviz включает в себя sfdp многомасштабную версию fdp (также в graphviz, аналогичную neato) для макета больших неориентированных графов, которая была полезна для рисования больших графов (70k узлов, 500 k краев) в моем проекте,
Вы можете найти документацию для этого программного обеспечения на самом веб-сайте graphviz по адресу http://www.graphviz.org/
Более подробную информацию можно найти в документе, описывающем основные методы и примеры: http://yifanhu.net/PUB/graph_draw_small.pdf
Я предлагаю сначала выполнить некоторую предварительную обработку данных, например, свертывание узлов в кластеры, а затем визуализацию кластеров. Свертывание уменьшит количество узлов и упростит выполнение алгоритмов, таких как Kamada-Kawai или Fruchterman-Reingold, для отображения полученного графика.
Если вам действительно нужно визуализировать 500 000 узлов, тогда вы можете рассмотреть возможность использования простой круговой компоновки. Это будет легко отображать без проблем, которые имеют силовые алгоритмы. Посмотрите на Circos: http://mkweb.bcgsc.ca/circos/
Circos - это графическая визуализация, разработанная людьми биоинформатики, которая предназначена для визуализации геномов и других чрезвычайно больших и сложных наборов данных.
Это пакет на основе PERL, я надеюсь, что это не проблематично.
У меня были хорошие результаты, используя библиотеку graph-tool в python. На приведенном ниже графике есть 1 490 узлов и 19 090 краев - для рендеринга на моем ноутбуке потребовалось около 5 минут.
Данные графика поступают из политической сети блогов, описанной Адамом и Глэнсом в Политическая блогосфера и выборы в США в 2004 году ссылка здесь. Если вы увеличиваете масштаб изображения, вы можете видеть URL-адреса блога для каждого node.
Вот код, который я использовал для его рисования (блог 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')
Попробуйте Gephi, у него есть новый плагин размещения, называемый OpenOrd, который масштабируется до миллионов узлов.
Mathematica вполне может справиться с этим, но я должен признать, что моя первая реакция была в соответствии с комментарием, в котором говорилось: "Возьмите листок бумаги и окрасьте его в черный цвет". Нет ли способа уменьшить плотность графика?
Возможная проблема заключается в том, что вы, похоже, ищете макет, а не только рендеринг. У меня нет знаний о характеристиках Big O макетов, реализованных различными инструментами, но интуитивно я предполагаю, что может потребоваться много времени, чтобы выложить много данных.
Нужно ли быть действительно точным?
В зависимости от того, что вы пытаетесь выполнить, может быть достаточно, чтобы просто набрать 10% или 1% объема данных. (конечно, это также может быть совершенно бесполезно, но все зависит от того, для чего предназначена визуализация)
Вы можете попробовать aiSee: http://www.aisee.com/manual/unix/56.htm
Я ожидаю, что краевая кластеризация (http://www.visualcomplexity.com/vc/project_details.cfm?id=679&index=679&domain=) поможет. Этот метод объединяет связанные ребра вместе, уменьшая визуальную сложность графика. Возможно, вам придется реализовать алгоритм самостоятельно.
BioFabric (www.BioFabric.org) - еще один инструмент для визуализации больших графов. Он должен иметь возможность обрабатывать описанную сеть (178 000 узлов и 500 000 ребер) в порядке, хотя первоначальный макет может занять некоторое время. Сеть показывает здесь (из Коллекции Данных Стендской Большой Сети) - Стэнфордская Сеть Сети, которая имеет 281 903 узла и 2 314 497 ребер:
Масштабируемость BioFabric обусловлена тем, что он представляет узлы не как точки, а как горизонтальные линии. Затем ребра показаны вертикальными линиями. Для некоторой интуиции о том, как это работает, существует Super-Quick BioFabric Demo, которая представляет собой небольшую сеть, которая анимируется с помощью D3.
Основное приложение написано на Java. На данный момент он может экспортировать только PNG-изображения, а не PDF файлы. Существует опция экспорта PDF из RBioFabric, хотя это очень простая реализация, которая еще не может обрабатывать действительно большие сети.
Полное раскрытие: BioFabric - это инструмент, который я написал.
Вы можете предложить санированную версию файла разработчикам этих инструментов в качестве сценария отладки, если все остальное не удается.
Проверьте GUESS на Java/Jython: http://graphexploration.cond.org/
Проект с крупным графиком (LGL) помог мне с подобным птоблемом. Он обрабатывает макет и имеет небольшое приложение java для рисования созданных макетов в 2D. Нет векторного вывода из коробки, поэтому вам придется рисовать график самостоятельно (с учетом координат node, созданных LGL)
Средство Windows, которое может визуализировать графики, pajek, оно генерирует вывод eps, однако я не знаю, может ли он прочитайте свои данные.
Здесь есть список приложений: http://www.mkbergman.com/?p=414
Walrus и LGL - два инструмента, которые, возможно, подходят для больших графиков. Тем не менее, оба, кажется, требуют, чтобы графики вводились как текстовые файлы в их собственном специальном формате, что может быть больно.
Я не думаю, что вы можете прийти удаленно близко к визуализации этого в плоском макете.
Я был заинтригован гиперболическими графами, описанными в этом исследовании в течение некоторого времени. Попробуйте программное обеспечение из SourceForge.
Другая идея - это просто графическое отображение узлов с помощью TreeMap, как показано на Panopticode.
Вы также можете попробовать NAViGaTOR (раскрытие: я являюсь одним из разработчиков этого программного обеспечения). Мы успешно визуализировали графики с целым количеством 1,7 миллиона ребер. Хотя такие большие сети трудно манипулировать (пользовательский интерфейс будет отставать). Тем не менее, он использует OpenGL для визуализации, поэтому некоторые из служебных данных переносятся на графическую карту.
Также обратите внимание, что вам нужно будет активировать параметры памяти в диалоговом окне "Файл- > Настройки", прежде чем вы сможете успешно открыть большую сеть.
Наконец, как указывает большинство других ответов, вам лучше переорганизовать свои данные на нечто меньшее и более значимое.
Во-первых, я хотел бы предложить второе предложение aliekens попробовать sfdp. Это крупномасштабная версия Neato.
Как указывает OJW, вы также можете просто построить узлы в R2. Ваши края фактически снабжают то, что он называет "естественным порядком". В частности, вы можете построить компоненты второго и третьего собственных векторов нормированного графа Лапласа. Это матрица L в этой странице wikipedia о спектральной кластеризации. Вы должны уметь записывать эту матрицу, не понимая за ней линейную алгебру. Затем вы уменьшили свою проблему до приблизительно вычисления первых нескольких собственных векторов большой разреженной матрицы. Это традиционно выполняется с помощью итерационных методов и реализуется в стандартных пакетах линейной алгебры. Этот метод должен масштабироваться до очень больших графиков.