How to become an author
Search
Write a publication
Pull to refresh

Comments 30

Есть хороший инструментарий работы с графами yEd, но как у него с масштабируемостью на очень большие данные не знаю.
Total votes 2: ↑2 and ↓0+2

yEd, как мне показалось, больше не для графов, а для диаграмм, блок-схем и т.д.

Total votes 1: ↑1 and ↓0+1
Красивая работа проделана, во множестве смыслов.
Total votes 4: ↑4 and ↓0+4

graphviz — стандарт, но я так и не мог дождаться завершения ни одного из его укладчиков на графе 10 тысячами связей. Плюс, они не умеют работать инкрементально — приостанавливать и продолжать работу.

Total votes 3: ↑3 and ↓0+3
Я, бывало, ждал дни пока досчитается sfdp, когда ещё не знал о других инстрментах.
В gephi можно поставить graphviz как плагин и пробовать уложить сначала им, а потом какой-то другой укладкой. Но для больших графов это будет бесполезно. Я пользуюсь укладкой dot для мелких графов, тоже через плагин. Удобно, что уложено как дерево, а возможности для анализа из gephi.
Total votes 1: ↑1 and ↓0+1
Напишите хотя бы для graphviz свои параметры. У меня 146к вершин, где-то х3 ребер — или вылетает по памяти или создает черный комок нечитаемый.
Gephi не смог запустить на таком же графе.
Total votes 1: ↑1 and ↓0+1
Я graphviz для таких размеров не использую. А gephi с openOrd и Multigravity ForceAtlas 2 вывозит до миллиона. Вы ведь поменяли в конфиге максимальный размер памяти доступный gephi? Чёрный комок можно размазать, если поставить в force atlas режим linlog, но скорее всего он его упрёт в квадратик. Хотя в статье есть иллюстрация, где gephi уложил 173К. И в одной из предыдущих статей я ещё из этого интерактивный сайт делал.

С читаемостью можно поработать ещё если настроить отображения. Убрать отрисовку рёбер, потому что их слишком много, уменьшить размер отображения вершин.
Или можно сразу переходить на LargeViz.
Total votes 1: ↑1 and ↓0+1
Не пробовали cytoscape? на 1М связей при использование укладок с поддержкой OpenCL очень резво работает
Total votes 1: ↑1 and ↓0+1
Пробовал года два назад. Может быть сейчас что-то поменялось, но тогда он вешал систему ещё при загрузке графа.
Total votes 1: ↑1 and ↓0+1
Грузит он бывает не шустро, но при этом проблема даже не в скорости загрузки, а в том что после загрузки он сразу применяет дефолтную укладку, а так как она не умеет в opencl это смерть, после этого можно уходить на обед.
Смена дефолтной укладкой на Perforce с OpenCL либо другой аппаратно ускоряемой разительно меняет ситуацию. То что укладывалось на CPU час, стало укладываться за секунды :)
Пока не просек в чем суть проблемы, потерял по сути день, на попытки хоть как то работать с этим графом.
Ну и конечно нужно увеличить дефолтное количество выделяемой памяти, потому что на выделенном 1GB большие графы просто не помещаются при укладке.
Total votes 1: ↑1 and ↓0+1
Спасибо. Обязательно попробую теперь. Cytoscape выглядел приятнее, чем gephi, может быть получится на него перейти.
This comment wasn’t rated yet0
Очень познавательная статья! Спасибо.
Total votes 4: ↑3 and ↓1+2
Я даже находил эту штуку раньше. Кажется, что для деревьев это лучше всего будет работать.
Total votes 1: ↑1 and ↓0+1
Вот такое современное искусство мне по душе)
p.s.
ничего не понял, но было очень интересно. (с)
Total votes 3: ↑3 and ↓0+3

А вы случайно не пробовали новый фреймворк PyTorch-BigGraph от FAIR на эту тему?
Там вроде питорчик и нормальная документация как у всех продуктов FAIR


Я пользовался похожищи вещами от FAIR (FastText + FAISS) и был в восторге, все работает, понятно и запускается из коробки.

Total votes 1: ↑1 and ↓0+1
Он больше для извлечения признаков. Документация, на момент, когда я пробовал, больше пересказывала статью о том, как они это придумали, а более менее толковые инструкции были на гитхабе в ридми. Но там всё равно нужно было много всего выяснять методом проб и ошибок. Понравилось, что требует относительно немного ресурсов. А вот эмбеддинги посмотреть я так и не смог.
Total votes 1: ↑1 and ↓0+1
Картинки интересные. Пока кажется, что для больших графов оно не подойдёт, потому что, например, хордовая диаграмма уже на тысячах объектов совсем перестаёт читаться.
Total votes 1: ↑1 and ↓0+1
Спасибо за статью, было интересно почитать как дела сейчас обстоят.
В своё время, в конце 2011 тоже столкнулся с этими проблемами когда делал карту Интернета internet-map.net (на мобилке лучше не смотреть — испортите впечатление) Поэтому пришлось писать своё решение чтобы обсчитать 350к вершин.

От отображения рёбер тоже пришлось отказатся иначе каша получалась.
Total votes 2: ↑2 and ↓0+2
О, шикарная штука! У меня товарищ недавно делал карту интернета через LargeViz только без интерактива. Там 2.5М вершин было. Я находил для таких интерактивных демо shingle.js — рассказывал об этом в одной из предыдущих своих статей. Вот тут демо iggisv9t.xyz/imdb/index.html — оно подгружает вершины и рёбра по зуму. А сама статья тут habr.com/ru/company/ods/blog/348110
Total votes 2: ↑2 and ↓0+2
Да, статью видел — интересная.

Вообще мне кажется настала пора сделать веб сервис который будет на сервере на видяхах все обсчитывать, прикрутить нейронную сеть чтобы она оценивала и подгоняла «под красоту», еще красивую интерактивную веб-морду и можно продавать (:

Такой сервис оставил бы все другие из вашей статьи далеко позади.
Total votes 1: ↑1 and ↓0+1
Вот graphistry как раз подобный веб-сервис. Но там ограничение на размеры, и дорого.
This comment wasn’t rated yet0
Спасибо, очень классный обзор! В одном проекте много работаю с графами, написал визуализацию с переводом в dot GraphViz, но возможно понадобится что-то помощнее. Жаль только что нет информации по совместимости существующих программ с разными ОС, что весьма актуально.
This comment wasn’t rated yet0
Ну тут всё просто. GraphViz и Gephi кросс-платформенные, igraph — просто библиотека, тоже везде ставится, graphistry — веб-сервис, а всё остальное надо самому собирать из исходников, а потом городить поверх что-то, что будет рисовать результат по координатам.
This comment wasn’t rated yet0

Немного оффтоп.


Я пилю утилиту для (в то числе) интерактивной визуализации классифицированных элементов (элемент может относится к одному или более классам). Объемы данных небольшие, не думаю, что они превысят и нескольких сотен. Один класс фактически представляет собой плотный граф, который в каждый элемент связан с каждым. Пытался для лейоута применить банально force-based алгоритм, вариации на тему Fruchterman and Reingold.


Проблема, с которой я столкнулся, заключается в том, что при увеличении количества вершин кластер "сплющивается", потому что силы отталкивания действуют на ближайших соседей, а притягивания — на весь граф, в итоге крайние вершины "сплющивают" середину.


Иллюстрация


Случайно не знаете, есть какой-то подход к решению таких проблем?


З.Ы. Пробовал сделать примитивный импульсный физический движок с коллизиями, чтобы узлы не проваливались друг в друга, но при большой "силе сжатия" начинаются артефакты вычислений, приходится поднимать количество итераций разрешения столкновений на кадр расчета физики.

This comment wasn’t rated yet0
Для начала можно уменьшить размер кружков. В gephi есть noverlap укладка (и не только в gephi) она специально раздвигает узлы, так чтобы они перестали накладываться. То есть сначала делается та, которая удобна, потом noverlap. Мне ещё нравится, как с этим справляется Yifan Hu, но с таким плотным комком, он скорее всего не поможет. В Force Atlas тоже есть параметр prevent overlap. А так, если степени вершин распределены примерно равномерно, то Fruchterman and Reingold неплохой выбор — он просто стремится всё расположить равномерно. А вообще устранение наложений во многих укладках решается просто масштабированием. Просто растягивают холст, но это эквивалентно уменьшению диаметра. То есть решение просто за счёт настроек отображения.
This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr