Хороший повод вспомнить Walrus. Он как раз для графов которые в стороны быстро разрастаются. Жаль он давно заброшен
https://t.me/sv9t_channel/292

Telegram

iggisv9t channel

Вы только посмотрите, какие там картинки. https://www.caida.org/tools/visualization/walrus/gallery1/lhr-old.png

В своей работе "Теорема о невозможности кластеризации" Клейнберг доказывает что никакой алгоритм кластеризации не может удовлетворять одновременно трем названным условиям. Масштабная инвариантность нарушается когда для определения принадлежности точки к кластеру используются относительные расстояния с заданным порогом. Насыщенность нарушается, если заранее фиксируется количество кластеров. Согласованность нарушается когда для объединения точек в кластеры используются абсолютные расстояния не превышающие некоторый порог. С другой стороны указанные критерии это субъективное представление о красивом/полезном разбиении множества на группы, с которым необязательно соглашаться. Максимально понятно, без математики, теорема описана тут.

Желание разложить что-угодно по группам на основе схожести - естественная черта человека, но задача кластеризации данных, почти всегда как плохое ТЗ для дизайнера - делай красиво, а не красиво не делай. Какой алгоритм кластеризации хороший, а какой плохой если сравнивать результат их работы не с чем? Джон Клейнберг из Корнеллского университета в 2002 году сформулировал три критерия хорошего алгоритма кластеризации:

- Масштабная инвариантность. Если все расстояния между точками умножить на положительное число, это не должно менять результат работы хорошего алгоритма.
- Насыщенность/разнообразие. Хороший алгоритм способен создать любую произвольную комбинацию разбиения входных данных.
- Согласованность. Если уменьшаем внутрикластерные расстояния и/или увеличиваем межкластерные, алгоритм должен возвращать то же разбиение на кластеры.

Все кругом рекомендовали читать "задачу трёх тел" и две последующие книги. Я сдался и вот уже третью книгу читаю. И вот что интересного вспомнил.

Как проверить, что мы живём в трёхмерном пространстве, а не просто застряли на маленьком кусочке в более высокоразмерном пространстве? Вот есть в физике всякие законы взаимодействий. И там всюду в знаменателе квадрат расстояния. Вот представим себе окружность и из центра проведём до неё линии с одинаковым углом между ними. То, сколько линий пересечёт сегмент окружности будет линейно зависеть от расстояния до центра. А если проделать то же самое со сферой, то плотность точек пересекающий кусок её поверхности убывает уже с квадратом расстояния. Если взять четырёхмерную сферу, то там плотность силовых линий будет убывать ещё быстрее. Так что если мы заметим, что какие-то силы убывают быстрее, чем с квадратом расстояния, то всё. Но такого пока не наблюдается. (хотя говорят, что на очень малых масштабах такие приколы могут происходить.
На самом деле я пересказал вам вот это https://sly2m.livejournal.com/587768.html — там чуть по подробнее но таким же простым языком.

Не хотелось докапываться до книги (это же не учебник по физике всё-таки), но совсем не обращать внимания на то, что так не сможет работать не получилось. Дальше спойлеры: вот там ребята вылезли в 4д и у них зрение стало как минимум трёхмерным. Как если плоского человека вытащить из листа бумаги, он скорее всего будет видеть те же линии, просто с незнакомых ему срезов. Так же и с трёхмерными людьми. Не говоря уже о том, что если они сдвинутся по четвёртой оси от своего трёхмерного куска, им надо бы с собой свдинуть воздух, чтобы подышать, ну и отрастить четырёхмерные мышцы, чтобы двигаться по новой оси. Хотя здесь можно вообразить решение с поворотом, так чтобы на четвёртую ось были ненулевые проекции сил, ну или тело может по четвёртой оси покукожить, так что это поможет движению. Из первой части поста ещё следует, что свет тоже будет убывать сильнее и есть много ещё проблем, про которые наверное отдельную книгу надо писать. А если не докапываться, то довольно интересно написано.

Livejournal

Почему у нашего пространства три измерения на пальцах™

Эпиграф Идет математик по улице и видит афишу на столбе: "Выступает камерный хор". Покупает билет, заходит, внимательно слушает, уходит, на улице пожимает плечами и говорит: — Частный случай, k равно трём. Возможно вы задумывались, почему, собственно, многие…

http://www.datagenetics.com/blog/september32012/index.html

Datagenetics

PIN number analysis

A detailed analysis of four character PIN codes

И ещё вот такую штуку можно вспомнить

Пост про выборы, фальсификации и то, почему ДЭГ — зло (с данными!)
Через неделю выборы Путина, а результаты выборов, как известно, государство у нас любит немножко подрисовывать

Пока мы готовим большой текст про фальсификации на выборах в течение последних 24 лет (спойлер-напоминание: "дорисованный" процент растет почти с каждыми выборами, и в 2020 и 2021 докинули процентов по 15), государство заманивает или даже заставляет всех голосовать электронно через ДЭГ. Кажется, сейчас самое время вспомнить, зачем это делается. Я сегодня сама первый раз в этом систематически разобралась, и думаю, что это все еще стоит того, чтобы рассказать

Вы, наверное, помните, что в 2021 году на участках с помощью электронного голосования победили провластные кандидаты, в то время как оффлайн оппозиционеры набрали больше. Здесь возникает резонный аргумент — но ведь государство активно призывало голосовать через ДЭГ, разве не может быть так, что онлайн проголосовали искренние сторонники ЕдРа, а все оппозиционеры не доверяли ДЭГу и шли голосовать оффлайн? Логично, только вот проблема не в этом

На самом деле есть 2 ДЭГа — федеральный и Московский, это разные системы. И вот на выборах в госдуму в 2021 о Московском ДЭГе были хоть какие-то данные. В частности, это были данные о динамике голосов. Они показаны на первой картинке в следующем посте. Мы видим, что голоса за ЕР возрастают скачкообразно ночью и утром в воскресенье и активно набираются до середины дня, а потом динамика также резко возвращается к исходной. Причем эта динамика была одинаковой во всех округах

Если вы примерно представляете, как выглядят распределения чего угодно в реальной жизни, то вы понимаете, что таких резких спаданий активности в жизни не бывает — что угодно обычно затухает плавно. А значит уже отсюда очевидно, что это некоторая накрутка

Но окей, скажете вы, может, в это время просто государство активно сгоняло бюджетников голосовать? Ну и что, что в 4 ночи, всякое бывает!

Выяснилось, что эта активность — это не просто голосование за ЕР, но переголосование! В ДЭГе есть такая функция — изменить свой голос. И московский ДЭГ сам предоставил данные о том, каким были результаты до переголосования. Из них видно, что переголосовывали почему-то почти всегда с оппозиционных кандидатов на провластных (картинки 2, 3, 4)

Что на это говорит ДЭГ? ДЭГ говорит, что в такой активности ничего подозрительного не видят, и она является результатом рассылки СМСок с призывом проголосовать! Т.е. буквально половина прогосовавших за оппозиционных кандидатов получили СМСку от города Москвы, начали поддерживать ЕР и поменяли свой голос

Если это объяснение все еще кажется вам реалистичным, то и его можно опровергнуть — повышение активности на фоне СМСок найти можно, оно небольшое и к наблюдаемым аномалиям в переголосованиях отношения не имеет

В общем, тут уже не остается никаких сомнений, что в нужный момент кому надо просто поменяли голоса, буквально отобрав их у оппозиционных кандидатов и отдав провластным. Причем сама возможность это сделать противоречит тому, как, по утверждениям ДЭГ, устроена система ДЭГ — они говорят, что у них самих нет информации, какой голос за кого отдан до финального подсчета. Но при этом они знали, чей именно голос на чей нужно поменять!

Но это еще не все, можно найти и другую "особенность". В Москве можно было голосовать за партию и за кандидатов по одномандатным спискам. Обычно люди, которые голосуют за ЕР, голосуют и за одномандатников от ЕР, и данные это подтверждают. Это поведение вполне логично — если вы поддерживаете партию, вы поддерживаете и отдельного кандидата от этой партии. Но в случае с ДЭГ в течение двух часов это было не так — систематически, одновременно во всех округах, голоса набирались только у ЕР, но не у одномандатников ЕР (картинка 5). Объяснить это ничем кроме машинного вмешательства нельзя

Надеюсь, про Московский ДЭГ было убедительно. Как я уже сказала, есть еще федеральный ДЭГ, который работает в других регионах, и по нему данных сильно меньше. Но какие-то все же есть! Про это будет следующий пост

#интересный_ресерч

Помните гугол выпускал библиотеку для кластеризации графов, но было непонятно как её запустить?
Так вот, они некоторое время назад добавили пример и у меня дошли руки адаптировать пример и прогнать на сравнительно большом графе (1M вершин, 10M рёбер). Это конечно было интересное приключение, потому что я не знаю C++ и тем более не понимаю что из себя представляет bazel. Но тем не менее, всё получилось, хотя и не без сюрпризов.

Могу сказать что эта штука действительно быстрая и почти не ест память. Но пока я не смог из неё вытащить качественных кластеров, которые были бы хотя бы сравнимы с моим обычным пайплайном: графовые эмбеддинги --> снижение размерности --> hdbscan.

Ещё я зацепился за слово "иерархическая кластеризация" и ожидал, что увижу кластера нескольких уровней, а оказалось, что там просто аггломеративная кластеризация и выдаёт она не дендрограмму даже, а просто список вершин на кластер.
Прогнал ещё одну (у них там несколько алгоритмов) с параметрами по умолчанию, но результат тоже не очень.
Разбираться как это всё правильно завести и что вообще там можно сделать -- очень тяжело. Нужно идти читать исходники и статьи про сами алгоритмы. Но для графов раз в 100 больше наверное ничего другого не получится запустить.

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

Telegram

epsilon correct

На HackerNews завирусилось, что мы релизнули кусок библиотеки для анализа графов. Поскольку документации в релизе особо нет (***🤦‍♂️***), хочу быстренько рассказать, что там вообще сейчас есть и что будет. Во-первых, этот кусок библиотеки – только для анализа…

Такую же задачу с отрисовкой анимации динамического графа решал для публикации в новой. Правда до MDS я не додумался, а если бы додумался не рискнул бы. Если делать на каждый временной шаг независимую укладку, то кроме мерцаний и рывков могут быть ещё и повороты и перемешивания в зависимости от инициализации.
В Gephi есть поддержка темпоральных графов. Местами там очень неинтуитивный воркфлоу, но функционал очень большой.
В итоге я сделал укладку графа целиком на всех временных срезах одновременно. Потом фильтровал рёбра по срезам, укладывал для кажого шага отдельно и сохранял координаты. Не самый масштабируемый подход, но главное было красивенько сделать.
Для анимации просто взял и интерполировал координаты в между конечными точками. Чтобы вершины ускорялись между шагами и замедлялись около отдельных шагов интерполяцию сделал как проекцию движения по окружности, то есть просто арксинус фиганул.

Telegram

iggisv9t channel

Вот кстати тот же граф, только просто анимация по времени

Всем привет!
Этот канал вместе со мной пережил многие взлеты и падения. Посты про хакспейс сменялись постами про Флиппер. На смену Флипперу приходили выставки и современное искусство. Последнее время почти все посты посвящены синтезаторам и музыке.
Я не всегда успевал делиться, но всегда этот канал отражал то, что важно для меня.

И сейчас в моей жизни появился новый проект, о котором хочется писать, рассказывать и делиться новостями! Проект, с которым я себя связываю, который дико меня увлек, в котором переплетается все — музыка, электроника, арт.

Мы делаем микрорэк.

Маленький модульный синт, где модули — это платы, они вставляются в макетку и соединяются проводочками. И все это мигает и звучит как настоящий синтезатор!

С помощью микрорэка можно вкатиться с нуля в синтезаторы. А еще можно макетить куски синта прямо на бредборде. А еще можно собрать десять осцилляторов и экспериментировать со звуком. А еще эти модули могут пригодиться не только для звука, но и просто для электроники, потому что там есть усилители, питание, генераторы сигнала и все такое.

Короче, я могу долго рассказывать взахлеб :)

Вот вам ссылки на проект и на наш канал:

https://microrack.org
@microrack

Мы ща активно разрабатываем девайс, в канале микрорэка будет еще куча новостей, подробностей, схем и мемов :)

И мы планируем в мае запускаться, на сайте есть формочка для тех, кто хочет не пропустить старт!

Такие вот дела. Искренне ваш,
Андрей coreglitch Строков