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