Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 30

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

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

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

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

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

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

Отличная статья. Спасибо.

Всего голосов 1: ↑1 и ↓0+1
Вот такое современное искусство мне по душе)
p.s.
ничего не понял, но было очень интересно. (с)
Всего голосов 3: ↑3 и ↓0+3

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


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

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

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

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

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

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


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


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


Иллюстрация


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


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

Комментарий пока не оценивали0
Для начала можно уменьшить размер кружков. В gephi есть noverlap укладка (и не только в gephi) она специально раздвигает узлы, так чтобы они перестали накладываться. То есть сначала делается та, которая удобна, потом noverlap. Мне ещё нравится, как с этим справляется Yifan Hu, но с таким плотным комком, он скорее всего не поможет. В Force Atlas тоже есть параметр prevent overlap. А так, если степени вершин распределены примерно равномерно, то Fruchterman and Reingold неплохой выбор — он просто стремится всё расположить равномерно. А вообще устранение наложений во многих укладках решается просто масштабированием. Просто растягивают холст, но это эквивалентно уменьшению диаметра. То есть решение просто за счёт настроек отображения.
Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr