Как работает релаксация плоского графа?

Question

[mayton2019]

Есть марковская сеть. Такого вида.

scala> spark.sql("select v1,v2,frequency from graph order by crc32(concat(v1,v2))").show(false)
+---+---+---------+
|v1 |v2 |frequency|
+---+---+---------+
|SO8|O87|1        |
|wkf|kfu|1        |
|93a|3aj|5        |
|9gr|gr8|1        |
|USY|SY4|2        |
|23x|3xD|1        |
|am1|m1o|4        |
|tff|ff5|1        |
|*ro|ro)|1        |
|mr1|r19|107      |
|kh9|h93|3        |
|k8d|8do|3        |
|xyf|yfc|2        |
|HQU|QUA|2        |
|he9|e9s|2        |
|S4u|4u)|1        |
|bds|dsn|2        |
|(SY|SYJ|1        |
|hag|agi|161      |
|HQE|QEU|1        |
+---+---+---------+

Это триграммы из парольных фраз. Например HQE -> QEU это переход с узла HQE в другой
узел с частотой 1 на всю обучающую выборку. Далее по алгоритму я буду нормализовывать
частоты и приводить их к вероятностям.

Мне надо нарисовать ее на плоскости. Проблема в том что узлов очень много (21 млн)
и все графические инструменты (graphiz, twopi, neato, dot просто зависают и вешают намертво
мне ноутбук на рендеринге картинки с графом). Я пробовал разные комбинации ключей
но все без толку. Видимо такой алгоритм.

И я задумался о том что я сам создам получше алгоритм основываясь на своем понимании
критерием.

Есть у меня критерии.

- граф должен быть максимально планарным насколько это возможно.
- у графа всегда есть точка входа (это узел с триграммой "(((" три скобочки (признак СТАРТА)
- у графа всегда есть точка завершения ( узел ")))")

такой я сделал дизайн для старт-стопных комбинаций. И эти две вершины
(СТАРТ и СТОП по идее будут иметь максимальную мощность а все остальные вершины
- эээ пока не знаю вобщем).

Возможен вариант что я сделаю прореживание графа. Тоесть выкину из него узлы с малой мощностью
просто ради визуализации.

Визуализация мне важна чтобы выбирать например би-граммы или три-граммы и просто на глазок
посмотреть некоторые свойства. Смотреть числовые метрики я тоже буду ... но чуть позже.
А пока это proof-of-concept.

Comments

[Wataru]

Что вы там в графе на 21 миллионов вершин вообще заметить собираетесь? Там у каждой вершины несколько дюжен ребер исходящих будет. Это такая мешанина будет, что фиг вы там чего найдете вообще.

[alexalexes]

Если вручную хотите работать с таким графом, то можно для начального состояния выбирать любую вершину, какую вам удобно по критериям и визаулизировать эту вершину и ее смежных соседей. Потом по клику на смежную вершину подгружать ее соседей и так далее. По аналогии с деревом каталогов по кнопке "Обзор..." в проводнике файлов.
PS: Можете написать какой-нибудь поиск в ширину/глубину, чтобы не одно поколение вершин открывал, а несколько, пока соблюдается критерий и не достигнута глубина проброса до следующих крайних вершин.

[mayton2019]

Wataru, я думал об этом. Я предполагал что есть особо нагруженные вешины и хотел визуально осмотреть
эту клику. Короче интерес такой. Познавательный. Сделать helicopter-view для всех своих данных.

И что в 21 веке мы не можем на листе А3 или А2 просто увидеть все данные? Я считал что это не такая
сложная задача. Осбенно в эпоху нейросетей с миллиардом синапсов.

[mayton2019]

alexalexes, это все понятно. Но у меня нет софта. У меня есть пока есть

1) Консольное приложение на Scala которое читает csv файл с 21 миллином строк.
2) Генерирует таблички марковских цепочек
3) Генерирует такие-же таблички в формате Graphviz
4) Есть spark script который просто визуализирует на экране некоторые проекции (как в тексте вопроса).

И скорее всего софта у меня не будет. По крайней мере покупать ничего не не собирался.
Поэтому вот.... Дешево и сердито. Еще попробую PyPlot но пока не нашел убедительных
примеров что Python способен переварить релаксацию 1.3 млн вершин.

[Wataru]

mayton2019, 21 миллион вершин - это будет 3000 на 7000 точек на листе A2. Расстояние между точками будет меньше 0.1 мм. К этому добавьте ребра туда-сюда, и ваш helicopter view будет равномерно черный лист.

У вас слишком большой граф для визуализации.

[mayton2019]

Wataru, ну А2 я сказал условно. Разумеется нет у меня такого принтера.

Вобщем для такого толстого графа мне надо глянуть клику. Треугольники. Остов. Короче
все что может быть интересно для такого себе предварительного обзора.

[mayton2019]

Небольшая ошибочка в расчетах. У меня 1.3 миллиона ребер. А вершин - порядка 160 тыщ.

scala> spark.sql("select count(*) from(select distinct v1,v2 from graph_df)").show()
+--------+
|count(1)|
+--------+
| 1343124|
+--------+

scala> spark.sql("select count(*) from (select v1 from graph_df union select v2 from graph_df)").show()
+--------+
|count(1)|
+--------+
|  166061|
+--------+

Я прикидывая на глазок совсем забыл про комбинации.

[d'Ivan]

А если сильно проредить данные, чтобы вместо миллионов были сотни?

[mayton2019]

Everything_is_not_so_bad, по какому принципу? Если-бы это была таблица я мог бы удалить 9 строк из десяти.
И таблица была бы такой-же однордной.

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