mayton2019
@mayton2019
Bigdata Engineer

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

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

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.
  • Вопрос задан
  • 91 просмотр
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы