Сказ царя Салтана о потенциале лапласиана

    «Три девицы под окном пряли поздно вечерком.»

    image

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

    «Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
    «Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».

    Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
    «Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
    Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.

    Вот что там было:
    • Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
    • Варвара получила по лайку от Алены и Софьи.
    • А Софья получила 2 лайка от Алены и 1 от Варвары.

    Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.

    Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).

    Подробнее о матрице лайков
    Для матрицы


    вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).

    После объявления результатов девицы бросились обратились к царю с просьбой рассказать,- откуда взялись эти странные цифры?


    1. Уравнение баланса


    В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.

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

    У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.

    Запишем это множество слов формулой:



    Здесь обозначает количество входящего потока в i-й узел, — количество исходящего из узла потока, — изменение остатка в узле.

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

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

    В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра с нулевой стоимостью нулевым остатком. Для таких систем уравнение упрощается:



    Круто. Но пока малополезно.

    Баланс потенциалов


    Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через . Применительно к потокам матрицу смежности также называют матрицей проводимости. Ее элементы отражают пропускную способность ребер графа.

    Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
    Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?

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

    Связь потока с потенциалами и проводимостью выражается простой формулой:



    Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:



    В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
    Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.

    В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:



    Рейтинги и самооценки


    «Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»

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

    Связываем с потоками. Когда i-й участник с весом голоса оценивает j-го участника с оценкой (количеством лайков) то он делится с ним своим потоком . Копить остатки тут ни к чему, поэтому каждый участник делится с остальными всем, что получил.

    Вес голоса участника — это потенциал , матрица лайков — это матрица смежности (связности), а итоговая оценка — суммарный полученный (он же отданный) поток .

    Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.

    2. Лапласианы


    Когда я был молодым и глупым впервые столкнулся с уравнением баланса (1.4), я уже умел программировать и знал про циклы. Поэтому решал его как программист — методом последовательных итераций. Задаем начальный вектор потенциалов, умножаем его на матрицу смежности, делим на степени узлов, получаем новый вектор потенциалов и т. д. Как правило, процесс сходится. А вспомнил я про молодость, прочитав статью о ценностях пьяницы, которая в общем и побудила меня «расчехлить формулы».

    Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали еще наши деды Лаплас и Кирхгоф. Способ основывается на свойствах матриц-лапласианов. Тут уже недавно вспоминали лапласианы в непрерывных средах. Дискретные лапласианы не менее интересны и важны.

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



    Тут можно посмотреть лапласиан от наших лайков



    Примем, что проводимость исходящих из узла i дуг задается в i-м столбце матрицы. Соответственно в i-й строке матрицы – проводимость входящих в узел дуг. Тогда сумма элементов каждого столбца лапласиана равна нулю.

    Вообще говоря, матрицы данного вида образуют отдельный класс, — лапласианы. Определитель лапласианов всегда равен нулю, поэтому, например, для них не существует обычной обратной матрицы. Но зато есть другая (псевдо)обратная, есть и своя единичная матрица. Получить лапласиан можно не только приведенным выше преобразованием. Например, преобразование девиации тоже дает лапласиан на выходе.

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

    Матрица Кирхгофа относится к классу лапласианов.

    Потенциалы лапласианов


    В линейной алгебре есть понятие дополнительного минора (кофактора) матрицы — это определитель матрицы, полученной из исходной вычеркиванием строк и столбцов (с учетом знака). Кофакторы играют большую роль в лапласианах.

    Потенциалом 1-го порядка лапласиана называется определитель матрицы, полученный вычеркиванием из исходного лапласиана одной строки и одного столбца.

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

    Итак, если обозначить через дополнительный минор матрицы, то определение потенциала лапласиана можно записать как



    Так вот эти потенциалы 1-го порядка от матрицы Кирхгофа и являются искомым решением уравнения (1.4).
    Удивительно. Не нужны никакие циклы, начальные присваивания, произведение матриц и пр. Удалил строку/колонку, посчитал определитель — получил ответ.

    Свойства потенциалов 1-го порядка
    • Потенциал узла представляет собой сумму произведений (кортежей) проводимостей ребер графа по всем возможным путям в данный узел, исключая контуры (циклы).
    • Количество множителей в произведении на 1 меньше размерности (количества узлов) графа.
    • Потенциал узла не зависит от проводимостей исходящих из него дуг.
    • Каждый кортеж (путь) в выражении для потенциала узла состоит из дуг, которые исходят из всех узлов, кроме данного. В одном кортеже нет двух дуг, исходящих из одного узла, но могут быть дуги, входящие в один узел.
    • В каждом кортеже (пути) обязательно присутствует дуга, входящая в узел (замкнутость).
    • В выражении для потенциала отсутствуют кортежи, содержащие циклы (контуры).
    • Количество кортежей в выражении для потенциала определяется известной формулой Кэли , и быстро растет с ростом узлов графа. Для 4-х узлов имеем 4^2 = 16 слагаемых, для пяти — 5^3 = 125 и т. д.
    • В симметричном графе потенциалы всех узлов равны – следствие того, что структура выражения для потенциалов всех узлов одна и та же (разница лишь в направлении).

    Графическая структура потенциала графа из 4-х узлов
    Демонстрирует комбинаторную сущность выражения для потенциала.



    Для определения потока через узел достаточно умножить потенциал узла на его степень:



    Мы получили, что хотели.

    Считаем лайки
    Для расчета веса голоса (потенциала) участника вычеркиваем соответствующую строку и столбец и считаем определитель. Получаем 3 потенциала:




    Это вес голоса каждого участника. Теперь считаем потоки и определяем, кто сколько голосов набрал:




    Алена набрала больше всех голосов.


    Как считать потенциалы больших графов


    Если граф большой (много узлов), то считать вектор потенциалоф через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:
    • В матрице лапласиана заменяем первую строку на вектор (1, 0, 0, ...).
    • Считаем обратную матрицу от полученной и находим ее детерминант.
    • Делим значения первой колонки полученной обратной матрицы на ее детерминант. Это и есть искомый вектор потенциалов. В первой строке — потенциал первого узла, во второй — второй и т. д.
    • Если абсолютное значение потенциала неважно, то считать и делить на детерминант необязательно.


    Ранжирование объектов на основе потенциалов и потоков


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

    Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.

    Результаты турниров


    Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
    Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.

    Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.

    Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2-3, 4-7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.

    Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.

    А что такое потенциал применительно к игрокам?
    Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
    Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.

    Для интересующихся подробностями
    Мы нормировали потенциалы и потоки так, чтобы их сумма была равна 100.
    Сергей Карякин Хикару Накамура Аниш Гири Виши Ананд Веселин Топалов Левон Аронян Фабиано Каруана Петр Свидлер
    U 17,8 11,4 12,5 13,7 6,4 12,0 13,8 12,4
    J 14,5 11,8 13,0 13,2 9,0 12,4 13,3 12,8
    М 1 7 4 3 8 6 2 5

    Каруана все-таки второй, а Гири — 4-й.

    Потенциалы пьяницы


    Последний пример, который мы рассмотрим в данной статье — это расчет ценности карт в народной игре «Пьяница».
    Спасибо за данный пример astgtciv. Без его статьи, возможно, не было бы и этой.

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

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



    Ключевая особенность — в левом нижнем (и/или правом верхнем) углу — «шестерка бьет туза».
    Тогда матрица Кирхгофа будет иметь вид:



    Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и строку, соответствующие «шестерке» (это крайние ряды справа и снизу), мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
    То же самое справедливо и для туза (1-я строка и колонка) с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.

    Сводка формул
    Выражения для потенциалов от туза до шестерки:


    Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:



    Заключение



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

    Пришла и нам пора закругляться. Используйте потенциалы!
    Поделиться публикацией
    Комментарии 34
      +20
      Я тупой… :(
        0
        Более корректно: Я не понял это… :(
          +2
          Это ж математика! Вооружаемся листком бумаги и карандашиком.
          Прочитали абзац — пописали формулки — перешли к следующему абзацу.
            0
            От таких статей хочется фундаментального понимания, потому что в школе это не было интересно. Мне вот, в общих чертах — всё ясно, но если копнуть глубже, то я из статьи получил конкретный ремесленный способ, а в понимании: немного теории + магия. Всё эти дискриминанты и обращённые матрицы не имеют для меня никакого смысла, хотя я их легко вычислю и применю формулы. Фактически, очень часто можно применять мощные и простые математические инструменты, которых лучше не касаться, потому что для большинства они являются барьером, за которым начинается чистая магия, а если не дунуть. как известно — никакой магии не получится.
            +1
            Я вот тоже понял только общую идею. С формулами беда. Может есть какой-то дополнительный материал?
            +1
            Потенциалы — это аналог взвешенного PageRank без телепортации?
              +2
              PageRank это частный случай использования потенциалов для ранжирования. Принцип тот же.
              0
              А возможно применить потенциалы для оценки статей и комментов на хабре, например?
                +1
                В статье описан принцип самооценки объектов. То есть скорее можно говорить о его использовании для оценки участниками хабра друг друга. С другой стороны, полученный таким образом вес может быть применим к оценке статей.
                0
                А кто мешал решить систему методом Гаусса и не мучаться со всякими лапласианами?
                  0
                  Гаусс, конечно, крутой, но даже он не смог придумать метод, который решал бы все системы. Обычный Гаусс тут неприменим, но, возможно, вы имеете ввиду какой-то другой неизвестный мне метод.
                    +2
                    А уточните, почему? Неужели ваши матрицы настолько плохо определены? Все остальные системы Гаусс вполне решает, и вряд ли система уравнений 3x3 из небольших случайных целых чисел настолько плохо определена.
                    Конечно, у нее определитель ноль, но с коих пор это было помехой Гауссу? Это просто обозначает, что ваши потенциалы определены с точностью до произвольного множителя (а чего еще вы хотели от однородной системы?), но тогда просто полагаете последний (или какой надо будет) потенциал равным единице, например, и вполне себе находите остальные потенциалы.
                    Вот я сейчас проделал это для вашей системы 3x3, приведенной в начале поста (добавив на диагональ что надо), и вполне получил потенциалы 5/7, 4/7, 1 — что и следовало ожидать.
                      0
                      Да, я был неточен насчет Гаусса. В статье приведен способ определения потенциалов через обращение матрицы. Перед этим матрицу надо немного модифицировать, примерно так же, как вы и указали. Ну а обращать матрицы можно и Гауссом, конечно.
                      Но то, что мы таким образом делаем, — это и есть "мучение с лапласианами" ) — с Гауссом или без — не особо принципиально.
                        0
                        Задаем начальный вектор потенциалов, умножаем его на матрицу смежности, делим на степени узлов, получаем новый вектор потенциалов и т. д.


                        А вот-это называется методом Гаусса-Ньютона :)
                  +3
                  Спасибо за статью. Офигеть, как круто. А если добавить еще участника, все надо будет заново полностью пересчитать? Или есть вариант побыстрее?
                    0
                    Хороший вопрос насчет нового участника. Навскидку не скажу, надо смотреть.
                    Но знаю, что при изменении элемента матрицы смежности пересчитывать все по новой необязательно. Производная потенциала 1-го порядка (по Cij) определяется потенциалом 2-го порядка. В статью не стал включать, чтоб не раздувать.
                    +1
                    Но ведь при таком способе расчёта важен порядок проставления лайков участниками. Поскольку с каждым прилетевшим в твою сторону лайком увеличивается твой вес и, соответственно, твой вклад в вес остальных участников.
                      +2
                      Если я правильно понял ваше замечание, то вы говорите о системе, при которой учитываются остатки в узле. То есть используется уравнение (1.1), а не (1.2). Что-то подобное учету текущего рейтинга спортсменов (шахматистов, например). (Можно назвать такие системы открытыми). Там да, порядок (историчность) лайков имеет значение.
                      +2
                      Потрясающая статья. Ещё раз убедился что пора вспоминать чему учился в университете, а то вот так сидишь, учишь 3-й яп или новый framework, а матрицы уже забыл. Недавно ужаснулся, когда осознал что забыл как решать СЛАУ и квадратные уравнения...
                        0
                        Статья очень интересная! Скажите, а какие методы оценки можно использовать для систем с двумя, тремя параметрами?
                        В качестве примера можно привести «лайки» и «репосты».
                          0
                          Хм, я не знаю, честно говоря,- надо думать. И еще насчет учета дислайков надо бы определиться.
                            +1
                            Наверное, проще всего будет установить какое-нибудь соответствие между параметрами, 1 репост = 1,5 лайка например.
                            +3
                            По причине некоторых запретов в правилах Хабра я не могу воспользоваться всеми словами русского языка, чтобы сказать, насколько хорошая статья получилась, и насколько правильное дело вы делаете; поэтому просто знайте, что статья получилась очень хорошая, и дело вы делаете очень правильное.
                              +1
                              Спасибо )
                              0
                              Очень интересно! Напоминает математическое рассмотрение рефлексии у Лефевра из серии "я знаю, что ты знаешь, что я знаю, что ты знаешь...." => "ты поставил мне лайк, поэтому мой лайк тебе будет более ценным для тебя, но тогда и твой изначальный лайк мне стал ценнее, увеличив в свою очередь ценность ответного лайка...".
                              Интересен сам подход, внедрение понятия потоков по узлам. Уравнение 1.4, как тут заметили в комментариях, действительно простая однородная система линейных уравнений, которая элементарно решается с точностью до общего множителя, и поэтому я не сильно понял зачем лапласианы тут, как и упоминание о сходимости и итерациях. Хотя этот програмистский метод сходимостей и итераций, возможно, базируется на подсознательном воплощении в программе рассуждений из первого абзаца данного комментария.
                                0
                                ) Думаю, что источником недоумения насчет "метода итераций" является фраза "когда я впервые столкнулся с уравнением...". На самом деле я столкнулся не с уравнением, конечно же, а с конкретной прикладной задачей,- как и автор упоминаемой статьи о ценности карт (читали?). А про уравнение и прочее это я уже потом выяснил.
                                И еще соглашусь, пожалуй, что в приведенных примерах можно было бы обойтись и без понятия "потенциал лапласиана" (просто вектор решения уравнения баланса). Но если мы копнем чуть глубже, то столкнемся с потенциалами 2-го и более высоких порядков. Там уравнение баланса уже особой роли не играет.
                                0
                                исходящий поток — кредит, входящий — дебет

                                Для точности стоит отметить, что как раз наоборот:
                                Входящий поток — кредит, исходящий — дебет, остаток — сальдо.

                                Кредит является источником средств, а дебет — куда они были потрачены.
                                Уставный капитал, целевое финансирование учитывается на пассивных счетах (счетах с кредитовым сальдо).
                                Пассивная часть баланса говорит откуда средства пришли, активная — куда ушли.
                                  0
                                  Вы точно не путаете остатки с оборотами? Про пассивы и активы вы правильно пишите, но дебетовые обороты счета (того же, например, 51-го), — это, извиняюсь, все-таки приход.
                                    0
                                    Как думаете, почему всё-таки в учёте используются дебет/кредит, а не приход/расход? Хотя попытки были и не раз (например Ф.В. Езерским)
                                    Наверное, потому что это не одно и то же :)

                                    Например, оприходование излишков:
                                    Дебет "Товары" Кредит "Прибылей и убытков"

                                    заменилось бы на:
                                    Приход "Товары" Расход "Прибыли и убытки"

                                    хотя прибыль-то как раз появилась :)

                                    Дебет/Кредит в зависимости от типа счёта (активный/пассивный) могут как уменьшать, так и увеличивать сальдо.
                                    51 — активный счёт. А 80, 84 и остальные? ;)))

                                    Как и любая абстракция — эта протекла.
                                      0
                                      Соглашусь с замечанием в том плане, что для пассивных счетов (типа капитала), входящий поток действительно уменьшает капитал (кредитовый остаток). Но при этом остается дебетовым.
                                      В статье, кстати, все примеры — активные счета.
                                  0
                                  Статья про потоки, потенциалы, схемы, графы — без единого рисунка графа. Хм. Автор явно высокого мнения о способностях аудитории к абстрактному мышлению :)
                                    0
                                    А как быть с нулями? Если A и B проигнорировали С (поставили 0 лайков), то их потенциалы вырождаются в 0 и потоки в свою очередь тоже.
                                      0
                                      Вот из ЛС с Автором:

                                      Два игрока играют в шахматы и один выиграл у другого все партии. Можно ли на основании данной информации определить их относительную силу? Очевидно, что нет. Хотя мы и можем сказать, что 1-й сильнее, но не знаем, насколько именно.

                                      Это важное уточнение к статье — для определения относительных потенциалов надо исключить узлы, из которых ничего не вытекает (стоки) и узлы, в которые ничего не втекает (источники). Нулевые потенциалы — это признак наличия таких узлов.
                                        0
                                        Если подробнее вдаваться в эту тему, то нулевые (вырожденные) потенциалы можно сравнивать между собой, но нельзя (не имеет смысла) сравнивать с остальными.
                                        Для сравнения нулевых потенциалов можно слегка возмутить диагональ лапласиана (прибавить всем диагональным элементам малое возмущение). В этом случае вырожденные потенциалы будут расщеплены, при этом величина отношения потенциалов не зависит от величины возмущения. Что-то типа раскрытия неопределенностей.

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

                                    Самое читаемое