Сказ царя Салтана о потенциале лапласиана
«Три девицы под окном пряли поздно вечерком.»
Ну как пряли. Не пряли, конечно, а лайкали друг на друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.
«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».
Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора…», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.
Вот что там было:
- Алена получила 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 меньше размерности (количества узлов) графа.
- Потенциал узла не зависит от проводимостей исходящих из него дуг.
- Каждый кортеж (путь) в выражении для потенциала узла состоит из дуг, которые исходят из всех узлов, кроме данного. В одном кортеже нет двух дуг, исходящих из одного узла, но могут быть дуги, входящие в один узел.
- В каждом кортеже (пути) обязательно присутствует дуга, входящая в узел (замкнутость).
- В выражении для потенциала отсутствуют кортежи, содержащие циклы (контуры).
- Количество кортежей в выражении для потенциала определяется известной формулой Кэли
, и быстро растет с ростом узлов графа. Для 4-х узлов имеем 4^2 = 16 слагаемых, для пяти — 5^3 = 125 и т. д.
- В симметричном графе потенциалы всех узлов равны — следствие того, что структура выражения для потенциалов всех узлов одна и та же (разница лишь в направлении).
Для определения потока через узел достаточно умножить потенциал узла на его степень:
Мы получили, что хотели.
Считаем лайки
Как считать потенциалы больших графов
Если граф большой (много узлов), то считать вектор потенциалоф через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:
- В матрице лапласиана заменяем первую строку на вектор (1, 0, 0, …).
- Считаем обратную матрицу от полученной и находим ее детерминант.
- Делим значения первой колонки полученной обратной матрицы на ее детерминант. Это и есть искомый вектор потенциалов. В первой строке — потенциал первого узла, во второй — второй и т. д.
- Если абсолютное значение потенциала неважно, то считать и делить на детерминант необязательно.
Ранжирование объектов на основе потенциалов и потоков
По итогам нашего примера получилось так, что наибольший вес голоса получила Софья, но больше всего баллов набрала Алена.
Это означает, что авторитетные и избранные — это не одно и тоже.
Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.
Результаты турниров
Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.
Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.
Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2–3, 4–7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.
Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.
А что такое потенциал применительно к игрокам?
Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.
| Сергей Карякин | Хикару Накамура | Аниш Гири | Виши Ананд | Веселин Топалов | Левон Аронян | Фабиано Каруана | Петр Свидлер | |
| 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)! Потому что вычеркнув колонку и столбец шестерки, мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.
Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
Заключение
Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.
Пришла и нам пора закругляться. Используйте потенциалы!
